[SOLVED] Strong Pseudo-Primes

[Icebreaker]

How would I show that a^1729 = a (mod 1729) for all n?

[Muzza]

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.

[neurocomp2003]

attempt to show by successive squaring

[Icebreaker]

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.

The conjecture was that a^k=a. In your counterexample, that is, 5^1729=9, 5!=9.

[Muzza]

The conjecture was that a^k=a. In your counterexample, that is, 5^1729=9, 5!=9.

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.

[neurocomp2003]

is it a conjecture that you are trying to show or are you asked to find a solution "a" to the question?

[Icebreaker]

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.

[neurocomp2003]

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.

[Muzza]

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.


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.

[Icebreaker]

Yes, because, say, a^12 = 1 (mod 13). Thanks for the help.