mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-08-01, 18:04   #1
monst
 
monst's Avatar
 
Mar 2007

17910 Posts
Default 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?
monst is offline   Reply With Quote
Old 2007-08-01, 18:42   #2
maxal
 
maxal's Avatar
 
Feb 2005

111111002 Posts
Default

Quote:
Originally Posted by monst View Post
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).
maxal is offline   Reply With Quote
Old 2007-08-01, 19:11   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by maxal View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-08-01, 19:37   #4
monst
 
monst's Avatar
 
Mar 2007

179 Posts
Default

Quote:
Originally Posted by maxal View Post
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?
monst is offline   Reply With Quote
Old 2007-08-01, 20:10   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2007-08-01, 20:11   #6
maxal
 
maxal's Avatar
 
Feb 2005

111111002 Posts
Default

Quote:
Originally Posted by monst View Post
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 View Post
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.
maxal is offline   Reply With Quote
Old 2007-08-01, 20:14   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·3·1,931 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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]
ewmayer is offline   Reply With Quote
Old 2007-08-02, 03:43   #8
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2·5·23 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
Jens K Andersen is offline   Reply With Quote
Old 2007-08-02, 16:32   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·3·1,931 Posts
Default

Quote:
Originally Posted by Jens K Andersen View Post
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."
ewmayer is offline   Reply With Quote
Old 2007-08-03, 13:52   #10
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by ewmayer View Post
"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 ?
m_f_h is offline   Reply With Quote
Old 2007-08-03, 14:40   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by m_f_h View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
List of proven/1k/2k/3k conjectures The Carnivore Conjectures 'R Us 84 2018-12-06 09:34
Primes for proven bases CGKIII Conjectures 'R Us 46 2017-01-03 17:31
Proven PRPs? Random Poster FactorDB 0 2012-07-24 10:53
Poincare conjecture proven? Nebob Lounge 36 2010-03-30 13:14
Are Legendre symbols proven to be defective? jasong Math 67 2008-04-20 15:01

All times are UTC. The time now is 16:34.

Tue Jan 26 16:34:53 UTC 2021 up 54 days, 12:46, 0 users, load averages: 2.70, 2.34, 2.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.