Primes of form 10^k + 1?

  • #1

Main Question or Discussion Point

"11 and 101 are primes, whereas 1001 is not (7*11*13). Find the next smallest prime of the form 100...01, and show that it is the next"

I'm fairly sure that there no primes of the form 10^k + 1 above 101, but I can't seem to find a complete proof.

Consider the general case of factorising x^n + 1 = 0 (the above problem is the special case at x = 10)

If n were odd, then there would be a root of x^n + 1 = 0 at x = -1, and hence (x + 1) is a factor of (x^n + 1) where n is odd. (transfers to 11 dividing 11, 1001, 100001, etc)

If n = 2 (mod 4), then there is a solution at x = i to x^n + 1 = 0, so (x^2 + 1) is a factor (transferring to 101 dividing 101, 1000001, 10000000001)

This does not extend to when n = 0 (mod 4), as x^4 + 1 cannot be factorised, nor can x^8 + 1, etc. However, 10^4 + 1, 10^8 + 1, etc, are all composite numbers, up to 1300 (according to various sources on the internet).

Am I going down completely the wrong path, or what?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Well, 10k + 1 divides 10kn + 1 for odd n (since then (-1)^n = -1 mod 10k + 1), so if 10k + 1 is prime then k is a power of 2. But I can't rule out the possibility of a Fermat-like high power popping up here.

I checked the small candidates; there are no such primes up to 10^1048576 + 1. This was made easier by knowing that the factors of such numbers are of the form km + 1 for some m.
 
Last edited:
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Oh, of course -- these are just the generalized Fermat numbers... that would be why all the properties are so nice.

http://www1.uni-hamburg.de/RRZ/W.Keller/GFN10.html [Broken]
There are no primes of the form 10n + 1 below 1016777216 + 1 other than 11 and 101.
 
Last edited by a moderator:
  • #4
The exact wording of the question:

"11 and 101 are prime numbers.
a) Show that 1001 is not a prime number.
b) Find the next smallest prime number of the form 100...01 and show that it is the next"

I highly doubt it's intended to infringe on the subject of Generalised Fermat Numbers, so I'm wondering if there's something that's being missed here...
 
  • #5
tiny-tim
Science Advisor
Homework Helper
25,832
250
http://www1.uni-hamburg.de/RRZ/W.Keller/GFN10.html [Broken]
There are no primes below 10^16777216 + 1.
That's not what your link says :confused:
Summary of factoring status for numbers Fm(10)



Character unknown m = 24, 25, 31, 32, 33, 34, 36, 38, 42, . . .



Last modified: April 2, 2010.
(but there seems to be an error: 1001 = 7.11.13 seems to be missing)
 
Last edited by a moderator:
  • #6
CRGreathouse
Science Advisor
Homework Helper
2,820
0
That's not what your link says :confused:
Sure it is (unless you're being pedantic about my omission of 11 and 101). m = 24 corresponds to 10^16777216 + 1, so there are no primes of the form 10^k + 1 below 10^16777216 + 1 (other than the trivial 11 and 101).
 
  • #7
CRGreathouse
Science Advisor
Homework Helper
2,820
0
(but there seems to be an error: 1001 = 7.11.13 seems to be missing)
How is that an error? 1001 is not of the form 10^(2^n) + 1 for integer n. It's out of the page's scope.
 
  • #8
tiny-tim
Science Advisor
Homework Helper
25,832
250
Sure it is (unless you're being pedantic about my omission of 11 and 101). m = 24 corresponds to 10^16777216 + 1, so there are no primes of the form 10^k + 1 below 10^16777216 + 1 (other than the trivial 11 and 101).
How is that an error? 1001 is not of the form 10^(2^n) + 1 for integer n. It's out of the page's scope.
oh i see

you're talking about 102n + 1 …

but this thread is about 10n + 1 …
"11 and 101 are primes, whereas 1001 is not (7*11*13). Find the next smallest prime of the form 100...01, and show that it is the next"

I'm fairly sure that there no primes of the form 10^k + 1 above 101, but I can't seem to find a complete proof.

Consider the general case of factorising x^n + 1 = 0 (the above problem is the special case at x = 10)

If n were odd, then there would be a root of x^n + 1 = 0 at x = -1, and hence (x + 1) is a factor of (x^n + 1) where n is odd. (transfers to 11 dividing 11, 1001, 100001, etc)

If n = 2 (mod 4), then there is a solution at x = i to x^n + 1 = 0, so (x^2 + 1) is a factor (transferring to 101 dividing 101, 1000001, 10000000001)

This does not extend to when n = 0 (mod 4), as x^4 + 1 cannot be factorised, nor can x^8 + 1, etc. However, 10^4 + 1, 10^8 + 1, etc, are all composite numbers, up to 1300 (according to various sources on the internet).

Am I going down completely the wrong path, or what?
 
  • #9
CRGreathouse
Science Advisor
Homework Helper
2,820
0
The exact wording of the question:

"11 and 101 are prime numbers.
a) Show that 1001 is not a prime number.
b) Find the next smallest prime number of the form 100...01 and show that it is the next"

I highly doubt it's intended to infringe on the subject of Generalised Fermat Numbers, so I'm wondering if there's something that's being missed here...
I don't know what to tell you. If there is a next prime of that form, it's greater than 10^16777216. I can neither find it nor prove that it does not exist. In a probabilistic sense, it likely does not exist: heuristically,
Pr(10^(2^m) + 1 is prime) ~ e^gamma/log 10 * m/2^m
if I have made no mistakes in my derivation. (There are of course lower-order terms I have omitted.) So the expected number of primes of this form is 2.000012, given that there are 2 below 24 and the others are unknown.*

* It would be unfair to omit from this total those about 24 for which a factor is known -- doing this would bias the expected number. It's not a big deal in this case, though; it would change the expected total to about 2.00009.
 
Last edited:
  • #10
1,838
7
you're talking about 10^2^n + 1 …

but this thread is about 10^n + 1 …
But 10^n +1 can only be a prime if n is a power of 2
 
  • #11
362
7
The exact wording of the question:

"11 and 101 are prime numbers.
a) Show that 1001 is not a prime number.
b) Find the next smallest prime number of the form 100...01 and show that it is the next"

I highly doubt it's intended to infringe on the subject of Generalised Fermat Numbers, so I'm wondering if there's something that's being missed here...
What's the source of this question? It seems to me, from what's been posted here and looking elsewhere, that no larger primes of this form are known.

Petek
 
  • #12
1,838
7
What's the source of this question? It seems to me, from what's been posted here and looking elsewhere, that no larger primes of this form are known.

Petek
Homework assignment from last Thursday. :smile:
 
  • #13
CRGreathouse
Science Advisor
Homework Helper
2,820
0
you're talking about 102n + 1 …

but this thread is about 10n + 1 …
I proved in my first post on this thread that numbers of the form 10n + 1 are prime only if n is a power of two. I didn't realize at that time that this was well-known -- I was pretty 'out of it' yesterday.
 
  • #14
362
7
Homework assignment from last Thursday. :smile:
Actually, that's what I was thinking too.

Petek
 
  • #15
tiny-tim
Science Advisor
Homework Helper
25,832
250
I proved in my first post on this thread that numbers of the form 10n + 1 are prime only if n is a power of two. I didn't realize at that time that this was well-known -- I was pretty 'out of it' yesterday.
ah yes … for any m, mn + 1 cannot be prime for odd n,

so if k has any odd factor n, then 10k + 1 = (10something)n + 1 cannot be prime,

so k cannot have any odd factor, so must be a power of 2.
 
  • #16
907
2
Let me offer some out of the box thinking.

Suppose the problem is posited in base 2.

11 = 3 and 101 = 5 are prime.
1001 = 9 is not.
10001 = 17 is prime.
 
  • #17
CRGreathouse
Science Advisor
Homework Helper
2,820
0
It's also worth pointing out (in the spirit of extreme pedantry) that 2 is a prime of the form 10^k + 1.

Let me offer some out of the box thinking.

Suppose the problem is posited in base 2.

11 = 3 and 101 = 5 are prime.
1001 = 9 is not.
10001 = 17 is prime.
Very good! That's probably worth turning in (along with comments on generalized Fermat numbers and the bound I gave). That should be worth at least 100% of the points for the problem.
 
  • #18
1,838
7
  • #19
105
0
Let me offer some out of the box thinking.

Suppose the problem is posited in base 2.

11 = 3 and 101 = 5 are prime.
1001 = 9 is not.
10001 = 17 is prime.
Why are you overlooking these:

100000001 Prime 257
10000000000000001 Prime 65537
 
  • #20
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Why are you overlooking these:

100000001 Prime 257
10000000000000001 Prime 65537
Because they are greater than 10001_2 = 17.
 
  • #21
77
0
The odds on 10^4+1 being prime (if we didn't already know it was composite) is one in ten. The odds of 10^8+1 being prime (if we didn't already know it was composite) is one in twenty. The odds of 10^12+1 being prime is one in thirty.

So the chance that 10^4+1, 10^8+1, 10^12+1, 10^16+1, 10^20+1 all being composite by coincidence is 3 in 4. I would conjecture that somewhere in this series is a prime. But not necessarily small.

We should be able to run a primality test on these monsters pretty quickly. Even if factorring them is out of the question.
 
  • #22
CRGreathouse
Science Advisor
Homework Helper
2,820
0
The odds on 10^4+1 being prime (if we didn't already know it was composite) is one in ten. The odds of 10^8+1 being prime (if we didn't already know it was composite) is one in twenty. The odds of 10^12+1 being prime is one in thirty.

So the chance that 10^4+1, 10^8+1, 10^12+1, 10^16+1, 10^20+1 all being composite by coincidence is 3 in 4. I would conjecture that somewhere in this series is a prime. But not necessarily small.
I have a more sophisticated analysis in post #9, considering both the numbers known to be composite and the special form of the factors. It suggests that there are about 0.000012 (rather than 0.75) primes left to be discovered in the sequence.

We should be able to run a primality test on these monsters pretty quickly. Even if factorring them is out of the question.
Factoring them completely is out of the question, yes. But even running a primality test would be prohibitively difficult, I think -- the smallest untested number has over 55 million bits.

What can be done is partial trial factorization. It's easy to check if a given (small) prime divides one of these large numbers. It takes me 270 milliseconds to verify that 10^16777216 + 1 has no prime factors under a million, for example. (Actually, in this case I know that the factors have a special form so there could be no prime factors under 16777216 + 1, but for the sake of an example I ignored this.)
 

Related Threads on Primes of form 10^k + 1?

Replies
4
Views
9K
Replies
2
Views
3K
Replies
4
Views
3K
Replies
10
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
4K
Top