Primes of form 10^k + 1?

[RobinElliott]

"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?

 

[CRGreathouse]

Well, 10^k + 1 divides 10^kn + 1 for odd n (since then (-1)^n = -1 mod 10^k + 1), so if 10^k + 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.

 

[CRGreathouse]

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 10ⁿ + 1 below 10^16777216 + 1 other than 11 and 101.

 

[RobinElliott]

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...

 

[tiny-tim]

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 …

Summary of factoring status for numbers F_m(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)

 

[CRGreathouse]

That's not what your link says …

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).

 

[CRGreathouse]

(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.

 

[tiny-tim]

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 10²ⁿ + 1 …

but this thread is about 10ⁿ + 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?

 

[CRGreathouse]

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.

 

[Count Iblis]

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

 

[Petek]

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

 

[Count Iblis]

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.

 

[CRGreathouse]

you're talking about 10²ⁿ + 1 …

but this thread is about 10ⁿ + 1 …

I proved in my first post on this thread that numbers of the form 10ⁿ + 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.

 

[Petek]

Homework assignment from last Thursday.

Actually, that's what I was thinking too.

Petek

 

[tiny-tim]

I proved in my first post on this thread that numbers of the form 10ⁿ + 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, mⁿ + 1 cannot be prime for odd n,

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

so k cannot have any odd factor, so must be a power of 2.

 

[hamster143]

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.

 

[CRGreathouse]

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.

 

[Count Iblis]

There is also a nice connection between the primality of the Fermat numbers and the fractional part of the Bernoulli numbers B_{2^k}. This follows from the von Staudt-Clausen Theorem:

http://mathworld.wolfram.com/vonStaudt-ClausenTheorem.html

 

[Mensanator]

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

 

[CRGreathouse]

Why are you overlooking these:

100000001 Prime 257
10000000000000001 Prime 65537

Because they are greater than 10001_2 = 17.

 

[robert2734]

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.

 

[CRGreathouse]

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.)