Are there any primes of the form 10^k + 1 above 101?

In summary, there are no primes of the form 10n + 1 below 10^16777216 + 1 other than 11 and 101. The next smallest prime of the form 10...01 is unknown, but is expected to be greater than 10^16777216. It is likely that there is no such prime, with a probability of 2.000012 out of 10^16777216.
  • #1
RobinElliott
2
0
"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?
 
Physics news on Phys.org
  • #2
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
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
CRGreathouse said:
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
tiny-tim said:
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
tiny-tim said:
(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
CRGreathouse said:
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 said:
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 …
RobinElliott said:
"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
RobinElliott said:
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
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
RobinElliott said:
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
Petek said:
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
tiny-tim said:
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
Count Iblis said:
Homework assignment from last Thursday. :smile:

Actually, that's what I was thinking too.

Petek
 
  • #15
CRGreathouse said:
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
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
It's also worth pointing out (in the spirit of extreme pedantry) that 2 is a prime of the form 10^k + 1.

hamster143 said:
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.
 
  • #19
hamster143 said:
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
Mensanator said:
Why are you overlooking these:

100000001 Prime 257
10000000000000001 Prime 65537

Because they are greater than 10001_2 = 17.
 
  • #21
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
robert2734 said:
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.

robert2734 said:
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.)
 

1. What are "Primes of form 10^k + 1"?

"Primes of form 10^k + 1" are prime numbers that can be written in the form 10^k + 1, where k is a positive integer.

2. How are "Primes of form 10^k + 1" different from other prime numbers?

"Primes of form 10^k + 1" have a specific pattern in their digits, as they always end in a 1 and have a series of zeros before it. This makes them stand out from other prime numbers.

3. What is the significance of "Primes of form 10^k + 1"?

There is no known practical application for "Primes of form 10^k + 1", but they have been extensively studied for their mathematical properties and patterns.

4. Are there infinitely many "Primes of form 10^k + 1"?

It is not known whether there are infinitely many "Primes of form 10^k + 1". However, there are infinitely many primes in general, so it is possible that there are infinitely many of this particular form.

5. Can "Primes of form 10^k + 1" be predicted or calculated?

No, it is not possible to predict or calculate "Primes of form 10^k + 1" as they follow the same rules as other prime numbers and are randomly distributed among all natural numbers.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
6
Views
931
  • Precalculus Mathematics Homework Help
Replies
3
Views
751
  • General Math
Replies
24
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
Back
Top