Page 2 of 4 FirstFirst 1234 LastLast
Results 16 to 30 of 46

Math Help - Prime Numbers (difficult question about something seemingly simple)

  1. #16
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    Ok, so the question is : for which k is 10^k + 1 prime.

    Theorem : if p | 10^k + 1, then p | 10^{mk} + 1 if m is odd.

    The proof is trivial, if 10^k \equiv -1 \pmod{p} \ \implies \ 10^{mk} \equiv {(-1)}^m \pmod{p} \ \implies \ 10^{mk} + 1 \equiv 0 \pmod{p}. This only works for odd m due to the special status of square roots in a congruence ring.

    Now, let k = 1 and p = 10^1 + 1 = 11 (since 11 is prime). Then 11 divides all numbers of the form 10^m + 1 where m is odd. That is, 50% of all concerned numbers.

    Then, let k = 2 and p = 10^2 + 1 = 101 (since 101 is prime). Then 101 divides all numbers of the form 10^{2m} where m is odd (2, 6, 10, ...).

    So we're still missing the numbers of the form 10^{2m} + 1 with m even. Let's look at 10^{2m - 1} + 1. This one's got to be composite (divisible by 11) since the exponent is odd.

    This is as far as I can go yet. I'm missing numbers of the form 10^{2m} + 1 for m even
    If you look at my post, I showed  10^a+1 is composite for all  a\neq2^n (this is a stronger result). I suspect we can't go much further than this... These resemble Fermat numbers.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by chiph588@ View Post
    If you look at my post, I showed  10^a+1 is composite for all  a\neq2^n (this is a stronger result). I suspect we can't go much further than this... These resemble Fermat numbers.
    Nice one, you just wiped some more numbers.
    So let's resume. We eliminated :
    All odd exponents : 1, 3, 5, 7, 9, ...
    All exponents of the form 2m with m odd : 2, 6, 10, 14, 18, 22, ...
    All exponents of the form 2^n : 2, 4, 8, 16, 32, ...

    We're still missing a small - yet infinite - subset of numbers, which can be expressed as m = 12k, k \in \mathbb{N}, that is, 12, 24, 36, ...

    Am I right ?
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by Bacterius View Post
    Nice one, you just wiped some more numbers.
    So let's resume. We eliminated :
    All odd exponents : 1, 3, 5, 7, 9, ...
    All exponents of the form 2m with m odd : 2, 6, 10, 14, 18, 22, ...
    All exponents of the form 2^n : 2, 4, 8, 16, 32, ...

    We're still missing a small - yet infinite - subset of numbers, which can be expressed as m = 12k, k \in \mathbb{N}, that is, 12, 24, 36, ...

    Am I right ?
    I thought that the only candidates were numbers of the form 10^{2^k}+1. We did not eliminate them.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by roninpro View Post
    I thought that the only candidates were numbers of the form 10^{2^k}+1. We did not eliminate them.
    Woops, I actually misread that. Sorry. I'll have a think.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    WOW! I thought that this question would be considerably less difficult to solve...no wonder I was having problems!
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by yeah:) View Post
    WOW! I thought that this question would be considerably less difficult to solve...no wonder I was having problems!
    IHMO, if you see "Prime number" in a question, either the question is trivial, either it is excruciatingly difficult to prove.
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    Quote Originally Posted by Bacterius View Post
    IHMO, if you see "Prime number" in a question, either the question is trivial, either it is excruciatingly difficult to prove.
    Yes, that is true! Any 'brainy' ideas yet, Bacterius (or anyone, for that matter!)?
    Follow Math Help Forum on Facebook and Google+

  8. #23
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by yeah:) View Post
    Yes, that is true! Any 'brainy' ideas yet, Bacterius (or anyone, for that matter!)?
    Nah, I'm off to sleep right now. Perhaps I'll get an idea while dreaming
    Follow Math Help Forum on Facebook and Google+

  9. #24
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Here's a start :

    Let 10^{2^k} + 1 \equiv 0 \pmod{n} for some prime number p, with p \neq 10^{2^k} + 1.

    So :

    10^{2^k} + 1 \equiv 0 \pmod{p}

    10^{2^k} + 10 - 10 + 1 \equiv 0 \pmod{p}

    10^{2^k} + 10 - 9 \equiv 0 \pmod{p}

    10^{2^k} + 10 \equiv 9 \pmod{p}

    10(10^{2^k - 1} + 1) \equiv 9 \pmod{p}

    10^{2^k - 1} + 1 \equiv 9 \times 10^{-1} \pmod{p}

    10^{2^k - 1} \equiv 9 \times 10^{-1} - 1 \pmod{p}

    Therefore, if 10^{2^k - 1} - 9 \times 10^{-1} + 1 divides some p in \mathbb{Z}/p\mathbb{Z}, then 10^{2^k} is divisible by p, thus is composite.

    So we basically have to show that such a p exists for all k > 1. I'll give the proof that it doesn't exist for k = 1.

    Let k = 1. Then, hypothetically, for some prime p :

    10^{2^1 - 1} - 9 \times 10^{-1} + 1 \equiv 0 \pmod{p}

    10 - 9 \times 10^{-1} + 1 \equiv 0 \pmod{p}

    11 - 9 \times 10^{-1} \equiv 0 \pmod{p}

    Multiply by 10 :

    110 - 9 \equiv 0 \pmod{p}

    101 \equiv 0 \pmod{p}

    Which is only true for the prime number 101. However, 101 = 10^{2^1} + 1 and we assumed that p \neq 10^{2^k} + 1 at the beginning, so we have a contradiction that leads to the conclusion that such a p does not exist for k = 1.

    Anyone can prove that for any k > 1 exists at least one p that satisfies the statement ?
    Follow Math Help Forum on Facebook and Google+

  10. #25
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    100501 IS a prime number!
    Follow Math Help Forum on Facebook and Google+

  11. #26
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by Bacterius View Post
    Here's a start :

    Let 10^{2^k} + 1 \equiv 0 \pmod{n} for some prime number p, with p \neq 10^{2^k} + 1.
    I'm having some trouble following you in the first line. Why would you want to assume that p \neq 10^{2^k} + 1? What if 10^{2^k}+1 is prime itself?

    Quote Originally Posted by yeah:) View Post
    100501 IS a prime number!
    I notice that you mentioned 100501 twice. What does this number have to do with the sequence 11, 101, 1001, 10001, ...?
    Follow Math Help Forum on Facebook and Google+

  12. #27
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    You are right - it is completely irrelevant. I apologise about that.
    Follow Math Help Forum on Facebook and Google+

  13. #28
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    ok so if we have that 10^m+1 is coposite for all odd m, then we assume m is even and so

    10^m + 1 = 10^2k +1 = 100^k + 1 and so if k is odd then we have the number is composite, if it is not then we just repeat the process until we have the exponent as an odd number which we will get as m must be a finite, and so there are no more primes of this form, is this helpful??
    Follow Math Help Forum on Facebook and Google+

  14. #29
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    So do we have a definitive answer yet?
    Follow Math Help Forum on Facebook and Google+

  15. #30
    Member
    Joined
    Oct 2009
    Posts
    95
    Best bet at figuring this out is probably modifying Pepin's test and running an optimized computer program:

    Pépin's test - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

Page 2 of 4 FirstFirst 1234 LastLast

Similar Math Help Forum Discussions

  1. Simple Windows application to compute prime numbers
    Posted in the Math Software Forum
    Replies: 4
    Last Post: July 9th 2010, 01:03 AM
  2. Replies: 4
    Last Post: April 26th 2010, 09:20 AM
  3. seemingly simple derivative
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 17th 2009, 07:05 PM
  4. Help with a (seemingly?) simple proof.
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 27th 2009, 10:38 PM
  5. Seemingly simple probability question...
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 23rd 2009, 12:05 PM

Search Tags


/mathhelpforum @mathhelpforum