Results 1 to 6 of 6

Math Help - Proving a Pseudoprime?

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Proving a Pseudoprime?

    How can I prove that the number 1729 is a pseudoprime ? I know that a pseudoprime is a composite n where n|((2^n)-2).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    How can I prove that the number 1729 is a pseudoprime ? I know that a pseudoprime is a composite n where n|((2^n)-2).
    Just take  2^{1729}-2 modulo  1729 .
    Last edited by chiph588@; May 28th 2010 at 08:53 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    Just take [tex] 2^{1729}-2 [tex] modulo  1729 .
    Could you please recheck your formatting because I'm having trouble distinguishing what this means.

    Also, If you're saying just do the operation, that really doesn't qualify as a proof, isn't that just an evaluation? How would I prove it?
    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 1337h4x View Post
    Could you please recheck your formatting because I'm having trouble distinguishing what this means.

    Also, If you're saying just do the operation, that really doesn't qualify as a proof, isn't that just an evaluation? How would I prove it?
    You want to show that  2^{1729}-2\equiv 0\bmod{1729} .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    You want to show that  2^{1729}-2\equiv 0\bmod{1729} .
    How do I show that?

    Isn't that  (0-(2^{1729}-2)) / {1729} ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by 1337h4x View Post
    How can I prove that the number 1729 is a pseudoprime ? I know that a pseudoprime is a composite n where n|((2^n)-2).
    As you already wrote, you only need to evaluate 2^{1729} \mod 1729 (basically, verify that 1729 fulfills the definition).
    You should be familiar with [ur=http://en.wikipedia.org/wiki/Modular_arithmetic]modular arithmetics[/url] and congruences to do this.

    Whether you want to this by hand or by computer, an effective way is to compute powers for the exponents:
    1729 -> 864 -> 432 -> 216 -> 108 -> 54 -> 27 -> 13 -> 6 -> 3 -> 1
    (If you already know n-th power, then you can easily compute (2n)-th power, and by multiplying by 2, you get the (2n+1)-st power.)
    This method is described in this wikipedia article.

    For instance, you can start as
    2^6 \equiv 64 \pmod{1729}
    2^{12} \equiv 64^2 = 2\cdot 2048 \equiv 2\cdot319 \equiv 638<br />
  \pmod{1729}
     2^{13}\equiv 2\cdot638 = 1276 \equiv -453 \pmod{1729}
     2^{26} \equiv 453^2 \equiv \dots \pmod{1729}
    etc.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 2-pseudoprime!
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 20th 2011, 06:32 AM
  2. Strong pseudoprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 10th 2010, 11:24 AM
  3. How to prove 161038 is pseudoprime?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 07:47 PM
  4. programming for pseudoprime problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 29th 2009, 04:03 AM
  5. Fermat pseudoprime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 2nd 2008, 10:15 PM

Search Tags


/mathhelpforum @mathhelpforum