Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primes of form 10^k + 1?

  1. Apr 6, 2010 #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?
     
  2. jcsd
  3. Apr 6, 2010 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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: Apr 6, 2010
  4. Apr 7, 2010 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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: May 4, 2017
  5. Apr 7, 2010 #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...
     
  6. Apr 7, 2010 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    That's not what your link says :confused:
    (but there seems to be an error: 1001 = 7.11.13 seems to be missing)
     
    Last edited by a moderator: May 4, 2017
  7. Apr 7, 2010 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  8. Apr 7, 2010 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  9. Apr 7, 2010 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    oh i see

    you're talking about 102n + 1 …

    but this thread is about 10n + 1 …
     
  10. Apr 7, 2010 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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: Apr 7, 2010
  11. Apr 7, 2010 #10
    But 10^n +1 can only be a prime if n is a power of 2
     
  12. Apr 7, 2010 #11
    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
     
  13. Apr 7, 2010 #12
    Homework assignment from last Thursday. :smile:
     
  14. Apr 7, 2010 #13

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  15. Apr 7, 2010 #14
    Actually, that's what I was thinking too.

    Petek
     
  16. Apr 7, 2010 #15

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  17. Apr 7, 2010 #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.
     
  18. Apr 7, 2010 #17

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It's also worth pointing out (in the spirit of extreme pedantry) that 2 is a prime of the form 10^k + 1.

    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. Apr 7, 2010 #18
  20. Apr 9, 2010 #19
    Why are you overlooking these:

    100000001 Prime 257
    10000000000000001 Prime 65537
     
  21. Apr 9, 2010 #20

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Because they are greater than 10001_2 = 17.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook