Page 1 of 4 1234 LastLast
Results 1 to 15 of 46

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

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    51

    Prime Numbers (difficult question about something seemingly simple)



    Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    It might help to note that the numbers you are considering have the form 10^n+1. Can you see how to use that to factor 1001?

    I tried to search for additional primes in this sequence and could not find any. (I believe that if a number of the form 10^n+1 is prime, then n must be of the form 2^k. I'm a bit too lazy to prove it right now.) Can part (b) even be fulfilled?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    So can anyone do part b)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by yeah:) View Post
    So can anyone do part b)?
    Haven't put too much thought into part b, but what I can tell you is a number of that form with an even number of zero's will always be divisible by  11 .

    Divisibility rule - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    For what it's worth, I've used PARI/GP to test numbers of the form 10^n+1 from n = 3 up to n = 6000 without finding any primes. To my knowledge, PARI's isprime() is deterministic rather than probabilistic.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    What about 100501???
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by yeah:) View Post
    What about 100501???
    You mean 10^100501 + 1? That returns composite.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    We're looking at 10^a+1. Suppose  a=2^ns where  s is odd.

     10^a+1=\left(10^{2^n}\right)^s+1\equiv(-1)^s+1=0\bmod{(10^{2^n}+1)} . Thus we see  10^a+1 is composite for all  a such that  s\neq1 .

    So the only remaining case to show are numbers of the form  10^{2^n}+1, \; n>3 . I'll see what I can come up with.
    Last edited by chiph588@; June 5th 2010 at 05:01 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chiph588@ View Post
    We're looking at 10^a+1. Suppose  a=2^ns where  s is odd.

     10^a+1=\left(10^{2^n}\right)^s+1\equiv(-1)^s+1=0\bmod{10^{2^n}} . Thus we see  10^a+1 is composite for all  a such that  s\neq1 .

    So the only remaining case to show are numbers of the form  10^{2^n}+1, \; n>3 . I'll see what I can come up with.

    I don't get it:

    (1) Did you mean \left(10^{2^n}\right)^s+1\equiv(-1)^s+1\!\!\!\pmod{10^{2^n}} ? This is absurd, and then looking at the extremes you get:

    2) 10^a+1=0\!\!\!\pmod{10^{2^n}} , which is also absurd...or, perhaps very probably, I misunderstood something.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by tonio View Post
    I don't get it:

    (1) Did you mean \left(10^{2^n}\right)^s+1\equiv(-1)^s+1\!\!\!\pmod{10^{2^n}} ? This is absurd, and then looking at the extremes you get:

    2) 10^a+1=0\!\!\!\pmod{10^{2^n}} , which is also absurd...or, perhaps very probably, I misunderstood something.

    Tonio
    Whoops! I had a typo. Take a look at my post again.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    So, is there any definitive way of solving/proving part b)?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by yeah:) View Post
    So, is there any definitive way of solving/proving part b)?
    Well, read my posts. It's being narrowed down.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    I can see that...if you have any more ideas, please post them up! I would really like to know how to solve this question!
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Perhaps actually setting 10^{2m} + 1 with m even, then :

    10^{2m} \equiv -1 \pmod{p}

    2^{2m} \times 5^{2m} \equiv -1 \pmod{p}

    Then breaking the congruence :

    2^{2m} \equiv \pm 1 \pmod{p} and 5^{2m} \equiv \mp 1 \pmod{p}

    And working with both : we've got some kind of Mersenne number on one side, and the other one's got to be composite (divisible by 2). These are just ideas, I don't even know if it's valid to break up a congruence in such a way.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 4 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