2022-06-23, 20:03 | #1 |
"Matthew Anderson"
Dec 2010
Oregon, USA
3·17·23 Posts |
10^a+1 is prime at least twice
Hi again everybody,
I'm curiouse about positibe integers of the form 10^a + 1 where a is a positive integer. see my code. > print("prime factorization of numbers of the form 10^a + 1"); for a to 20 do b := 10^a+1; c := ifactor(10^a+1); print(b, " factors as ", c) end do; <begin Maple output> "prime factorization of numbers of the form 10^a + 1" 11, " factors as ", (11) 101, " factors as ", (101) <note 11 and 101 are prime numbers> </note> <Maple output> 1001, " factors as ", (7) (11) (13) 10001, " factors as ", (73) (137) 100001, " factors as ", (11) (9091) 1000001, " factors as ", (101) (9901) 10000001, " factors as ", (11) (909091) 100000001, " factors as ", (17) (5882353) 1000000001, " factors as ", (7) (11) (13) (19) (52579) <one billion> </Maple output> <joke> Now that you know that One Billion has prime factorization of 7*11*13*19*52579, your life is complete. <smile> </joke> <note> Another calculation shows that. 10^a + 1 is a composite number for integers 3<a<86. The pattern seems to suggest that 10^a + 1 is always composite for integers a>3. But a pattern does not make a theorem. Anyone care to take the calculation furthur? Regards, Matt PS Has someone else already done this calculation? Can we look this up somewhere? Cheers, Matt P.S. After nearly a 5 hour calculation, and I trust my computer for accurate results, I can say with certainty that the positive integers of the form 10^a+1 are composite for integers 'a' with 3 <= a <= 97. This I am sure of. I'm sure someone else could extend the dataset. Regards, Matthew Charles Anderson PPS Here is my raw Maple code > restart*print("prime factorization of numbers of the form 10^a + 1"); for a to 1000 do b := 10^a+1; c := ifactor(10^a+1); if isprime(b) then print(b, " factors as ", c) end if end do; <Maple outuput> "prime factorization of numbers of the form 10^a + 1" restart () 11, " factors as ", (11) 101, " factors as ", (101) Warning, computation interrupted <check to see how far it calculated in 4.7 hours>(a checkpoint) a 97 #interesting_mathematical_trivia So to reiterate, 11 is prime, 101 is prime, and 10^a + 1 is not prime for a= 3,4,5,...,97. Have a nice day. |
2022-06-23, 20:34 | #2 |
Sep 2002
Database er0rr
2^{2}·3^{2}·7·17 Posts |
10^2^k+1 is a Generalized Fermat Number. There are very few Fermat Numbers that are prime. There will be fewer base 10 GFN primes is my guess.
Last fiddled with by paulunderwood on 2022-06-23 at 20:47 |
2022-06-23, 20:49 | #3 |
Einyen
Dec 2003
Denmark
5·677 Posts |
All odd a>=3 is divisible by 11: a=2n+1
10^{2n+1} + 1 = 100^{n} * 10 + 1 = 1^{n} * 10 + 1 = 0 (mod 11) All a=4n+2 >=6 is divisible by 101: 10^{4n+2} + 1 = 10000^{n} * 100 + 1 = 1^{n} * 100 + 1 = 0 (mod 101) All a=8n+4 >=4 is divisible by 73: 10^{8n+4} + 1 =100000000^{n} * 10000 + 1 = 1^{n} * 10000 + 1 = 0 (mod 73) There are probably several more of these. Last fiddled with by ATH on 2022-06-23 at 20:51 |
2022-06-23, 21:03 | #4 |
Mar 2006
Germany
101110100001_{2} Posts |
5 hours of energy which could be saved by searching a well known database of such formats of number, see Studio Kamada for factors of 10^n+1 for n=1 to 150,000.
FactorDB also contains those factorizations already. |
2022-06-23, 21:52 | #5 |
Apr 2020
857 Posts |
If k is odd, then x^k+1 factorizes as (x+1)(x^(k-1)-x^(k-2)+...-x+1). Substituting 10^m for x, we see that 10^km+1 is divisible by 10^m+1 if k is odd. In other words, 10^n+1 cannot be prime if n has an odd factor greater than 1.
The only values of n for which this is not the case are powers of 2, so these are the only exponents for which it is possible for 10^n+1 to be prime. They are Generalized Fermat numbers as Paul says. See Wilfrid Keller's page for the status of the base 10 GFNs. No primes are known apart from 11, and it is almost certain that no more exist. 10^(2^31)+1 is the smallest with unknown status. |
2022-06-24, 00:45 | #6 |
"Matthew Anderson"
Dec 2010
Oregon, USA
2225_{8} Posts |
Thank you for all the insightful replies.
Learning is an ongoing process. I try to summarize I never fully understood the term Generalized Fermat Number, until now. I will accept the definition a^(2^k) + 1 is defined as a Generalized Fermat Number 10^(2^k) + 1 as a Generalized Fermat Number with a=10. see mathworld.Wolfram.com reference https://mathworld.wolfram.com/GeneralizedFermatNumber.html Here are some (somewhat new to me) identities that are related. x^3 + 1 = (x+1)*(x^2 - x + 1). x^5 + 1 = (x+1)*(x^4 - x^3 + x^2 - x + 1). similarly with x^7 + 1 and bigger odd exponents. If we let x=10, then we have cases when divisibility by 11 happens. for example, as I was shown 10^3+1 = 11*91 10^5+1 = 11*9091 10^7+1 = 11*909091 10^9+1 = 11*90909091 there is a (somewhat more clear now) pattern here. Let's call it an exercise in learning, or an exploration. Time for a YouTube.com song See "The Best of Johnny Nash" https://www.youtube.com/watch?v=g_rB4v75jqU On a personal note, Okay, I do not have my textbooks any more, because I have communal living. Over the years, some of my things have been stolen. All my remaining textbooks are in my back shed, and that is my space, only my wife has partially filled it with toilet paper and supplies. I will find a way to continue my academic journey. and have fun... and love life. Matt PS No matter what happens, it is worth it. Here is the second part. This is some very good learning for me. To call out the helpful replies one by one, ATH, you make some good points, There are several general cases when we have divisibility by 11, 101, and 73. These patterns are often difficult to flesh out, if you don't know about them. 'nearly hidden gems' if you will. I looked at Studio Kamada and downloaded some of the data also, the positive integer factorizations are worked out, and presented clearly. Surely, I am not the first person who has considered numbers of this type. (to be specific 10^a + 1 = S) where S is for Special number. I looked at https://stdkmd.net/ (Studio Kamada) Specifically stdkmd.net/nrr/ Then scroll to section 9.1 and look at second link specifically https://stdkmd.net/nrr/repunit/10001.htm requires some scrolling okay too many links In this exploration, I did not need to 're-invent the wheel' but to 'look up a reference'. I feel enlightened about this number theory now. However, tomorrow I will be onto other things. Last fiddled with by MattcAnderson on 2022-06-24 at 01:04 Reason: a second block of text copied from notepad #grateful now grammer errors |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Can a (decimal) repunit prime (other than 11) be a member of twin prime pair? | sweety439 | And now for something completely different | 22 | 2022-03-23 00:22 |
Prime residues of near-prime modulo a prime | robert44444uk | Math | 27 | 2021-11-21 11:00 |
How to get to a prime from the previous prime number (sieve of Eratosthenes rediscovered) | AddieJ | Miscellaneous Math | 15 | 2021-05-11 14:57 |
Congruent prime numbers that preserves the modulo as the largest prime factor of the sum | Hugo1177 | Miscellaneous Math | 5 | 2021-02-11 07:40 |
Primes of the form prime(a)+prime(b)+1=prime(c) and prime(b)-prime(a)-1=prime (c) | Hugo1177 | Miscellaneous Math | 1 | 2021-01-05 08:09 |