1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Strong Pseudo-Primes

  1. Oct 4, 2005 #1
    [SOLVED] Strong Pseudo-Primes

    How would I show that a^1729 = a (mod 1729) for all n?
     
    Last edited by a moderator: Oct 5, 2005
  2. jcsd
  3. Oct 4, 2005 #2
    Without further hypotheses on a and n, you wouldn't. For example, 5^1729 = 9 (mod 11).

    Any similar conjecture will also be false. That is to say, let k be some fixed number. Then "a^k = a (mod n) for all n" is false, since it would imply that there would not be exist a primitive root mod p for p > k - 1, p prime.
     
    Last edited: Oct 4, 2005
  4. Oct 4, 2005 #3
    attempt to show by successive squaring
     
  5. Oct 4, 2005 #4
    The conjecture was that a^k=a. In your counterexample, that is, 5^1729=9, 5!=9.
     
  6. Oct 5, 2005 #5
    Yes. What's your point?! 5 != 9 (mod 11) is precisely what makes it a counterexample to the conjecture, hence the conjecture isn't true.
     
    Last edited: Oct 5, 2005
  7. Oct 5, 2005 #6
    is it a conjecture that you are trying to show or are you asked to find a solution "a" to the question?
     
  8. Oct 5, 2005 #7
    I must show for all a. The modolus is the same as the exponent. The modulus is not a prime, therefore Fermat's little theorem does not apply.
     
    Last edited by a moderator: Oct 5, 2005
  9. Oct 5, 2005 #8
    ok i think you need toi restate your quesiton.

    "How would I show that a^1729 = a (mod 1729) (for all n)?"
    there is no n in this statement though i rememebr there being one.
     
  10. Oct 5, 2005 #9
    I'll assume that what you actually want to prove is that a^1729 = a (mod 1729) for all a.

    Since 1729 = 7*13*29, this is equivalent to showing that

    a^1729 = a (mod 7),
    a^1729 = a (mod 13), and
    a^1729 = a (mod 19)

    for all a. That should be easy.
     
  11. Oct 5, 2005 #10
    Yes, because, say, a^12 = 1 (mod 13). Thanks for the help.
     
  12. Dec 20, 2009 #11
    Re: [SOLVED] Strong Pseudo-Primes

    I still was confused wether the answer or question is correct ..



    I'll assume that what you actually want
    to prove is that a^1730 == a (mod 1729) for all a.

    since 1730 = 1729 + 1 == 1 ( mod 1729 ), we have 1730 mod 1729 = 1

    <=>

    a^1 = a, hence a^1730 = a^1 = a ( mod 1729 )

    a^1729 == a^0 = 1 ( mod 1729 )

    <=>

    1729 == 1 ( mod 1729 )

    = = =

    Since 1729 = 7*13*29, this is equivalent to showing that

    a^1729 = a (mod 7),
    a^1729 = a (mod 13), and
    a^1729 = a (mod 19)

    for all a. ??

    Well 1729 = 7x13x19
    <=>
    1729 mod 1729 = 0
    1729 mod 7 = 0
    1729 mod 13 = 0
    1729 mod 19 = 0

    So a^1729 = a^0 = 1 (mod 1279),which only equals a for a=1 ....
     
  13. Dec 20, 2009 #12
    Re: [SOLVED] Strong Pseudo-Primes

    a^12 = 1 (mod 13).

    13 = 12 + 1
    12 mod 13 = 1,

    a^12 = a ( mod 13 )

    a^12 = a^0 = 1 (mod 12 )

    Actually

    a^(n+1) = a ( mod n )

    a^n = 1 ( mod n )
     
  14. Dec 20, 2009 #13
    Re: [SOLVED] Strong Pseudo-Primes

    a^(n-1) = a^(-1) ( mod n )
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Strong Pseudo-Primes
  1. Strong Induction (Replies: 8)

  2. Pseudo Inverse (Replies: 3)

Loading...