mersenneforum.org > Math Has this been proven? ... 10^n + 1
 Register FAQ Search Today's Posts Mark Forums Read

 2007-08-01, 18:04 #1 monst     Mar 2007 2638 Posts Has this been proven? ... 10^n + 1 Has it been proven that 10^n + 1 is composite for all n > 2 ? If so, can someone point me to it? It is composite for n odd, since 11 is a factor. But what about n even?
2007-08-01, 18:42   #2
maxal

Feb 2005

11·23 Posts

Quote:
 Originally Posted by monst Has it been proven that 10^n + 1 is composite for all n > 2 ? If so, can someone point me to it? It is composite for n odd, since 11 is a factor. But what about n even?
If n has an odd factor m>1, then 10^n + 1 has a non-trivial factor 10^(n/m)+1.
Therefore, the only possibility for 10^n + 1 being prime is n = 2^k (similarly to Fermat primes).

2007-08-01, 19:11   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by maxal If n has an odd factor m>1, then 10^n + 1 has a non-trivial factor 10^(n/m)+1. Therefore, the only possibility for 10^n + 1 being prime is n = 2^k (similarly to Fermat primes).
And as with Fermat primes, we expect that there are only finitely many
primes of the form 10^2^n + 1.

2007-08-01, 19:37   #4
monst

Mar 2007

B316 Posts

Quote:
 Originally Posted by maxal If n has an odd factor m>1, then 10^n + 1 has a non-trivial factor 10^(n/m)+1. Therefore, the only possibility for 10^n + 1 being prime is n = 2^k (similarly to Fermat primes).
Thanks for the clarity here. Your response has prompted another question in my mind.

I believe my original post can be genralized a bit to...
For any even base b, b^n + 1 is composite for all n odd, since b + 1 is a factor.

My question is... What generalizations to your response can be made for even bases, b? Do all even bases behave "similar to Fermat primes" as you have proven for b = 10?

 2007-08-01, 20:10 #5 wblipp     "William" May 2003 New Haven 2,371 Posts Google "Generalized Fermat Numbers" to find more information. I especially liked the list of factors in Table 1 of Bjorn and Reisel's 1998 paper Factors of Generalized Fermat Numbers
2007-08-01, 20:11   #6
maxal

Feb 2005

FD16 Posts

Quote:
 Originally Posted by monst I believe my original post can be genralized a bit to... For any even base b, b^n + 1 is composite for all n odd, since b + 1 is a factor.
This is true for all bases b>1, evenness of b is not required.
Quote:
 Originally Posted by monst What generalizations to your response can be made for even bases, b?
Generalization is straightforward:
If n has an odd factor m>1, then b^n + 1 has a non-trivial factor b^(n/m)+1.
In particular, for odd n we can take m=n and obtain the property you mentioned.

2007-08-01, 20:14   #7
ewmayer
2ω=0

Sep 2002
República de California

267178 Posts

Quote:
 Originally Posted by R.D. Silverman And as with Fermat primes, we expect that there are only finitely many primes of the form 10^2^n + 1.
And since the 102[sup]n[/sup]+1 grow much faster with n than the 22[sup]n[/sup]+1, we heuristically expect fewer primes below any bound n.

By way of example:

22[sup]n[/sup]+1 is prime for n=0,1,2,3,4 and likely for no other known values [and certainly not for n < 33];

102[sup]n[/sup]+1 is prime for n=0,1 and for no other values n < 13. [As high as I tested using PARI just now - there is likely a larger known bound]

2007-08-02, 03:43   #8
Jens K Andersen

Feb 2006
Denmark

E616 Posts

Quote:
 Originally Posted by ewmayer And since the 102[sup]n[/sup]+1 grow much faster with n than the 22[sup]n[/sup]+1, we heuristically expect fewer primes below any bound n.
Of course, some numbers scoff at heuristics. 20720059254662[sup]n[/sup]+1 is prime for n = 0,1,2,3,4,5,6. It's the smallest such base and was computed for http://primepuzzles.net/puzzles/puzz_399.htm.

2007-08-02, 16:32   #9
ewmayer
2ω=0

Sep 2002
República de California

32×1,303 Posts

Quote:
 Originally Posted by Jens K Andersen Of course, some numbers scoff at heuristics.
"I am Hassan, the rebellious data point ... I scoff at your means and probability distribution functions. I and my fellow rebel outliers wage jihad against the 95%-confidence-interval infidel crusaders. The streets shall flow with the blood of the 3-SD jackals and their lackeys! All praise be unto Allah, the Unstatistical."

2007-08-03, 13:52   #10
m_f_h

Feb 2007

24×33 Posts

Quote:
 Originally Posted by ewmayer "I am Hassan, the rebellious data point ... I scoff at your means and probability distribution functions. I and my fellow rebel outliers wage jihad against the 95%-confidence-interval infidel crusaders.
on that token, what's the practical use of knowing a sequence is finite if one does not know anything about the last term?
e.g. suppose we know that Fermat primes are finite, but the next and last one is 2072005925466 or larger than 2,365,100,000,000 (cf A090875) or 10^10^7 ? and/or, to what extend can heuristics which tell us that a sequence is "most probably" finite, also tell us something about the magnitude of the last term ?

2007-08-03, 14:40   #11
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by m_f_h and/or, to what extend can heuristics which tell us that a sequence is "most probably" finite, also tell us something about the magnitude of the last term ?[/COLOR]
Generally speaking, they can't.

Your question strikes at the difference between existence proofs and
constructive proofs. Or, (say) that knowing a diophantine equation
has finitely many solutions, but not knowing a bound on them. Or
knowing that a set is infinite but being unable to exhibit one of its
elements or ....... any of a number of similar situations.

Alan Baker's work on linear forms in logarithms can be useful, but it
isn't always applicable.

A striking example is the Catalan Conjecture. Before Preda Mihailescu
finished his (very elegant) proof, we knew that there were at most
finitely many solutions. And we had a bound. But the bound was beyond
computer range. Then Preda found a connection to the Wieferich congruence
and this brought the problem to a point where the computation became
possible (but very large). Then he found a proof that avoided the computations. (APPLAUSE!)

Another example: We know that almost all real numbers are Transcendental.
The subset that is algebraic is countable, while the reals are uncountable.
Thus, the algebraic numbers have density 0 in the reals. But knowing that
almost all numbers are transcendental does not help us prove that e.g.
The Euler-Mascheroni constant is.

 Similar Threads Thread Thread Starter Forum Replies Last Post The Carnivore Conjectures 'R Us 84 2018-12-06 09:34 CGKIII Conjectures 'R Us 46 2017-01-03 17:31 Random Poster FactorDB 0 2012-07-24 10:53 Nebob Lounge 36 2010-03-30 13:14 jasong Math 67 2008-04-20 15:01

All times are UTC. The time now is 09:21.

Tue May 24 09:21:56 UTC 2022 up 40 days, 7:23, 0 users, load averages: 1.42, 1.68, 1.74