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

Homework Help: 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 )
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook