# Homework Help: Strong Pseudo-Primes

1. Oct 4, 2005

### Icebreaker

[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. Oct 4, 2005

### 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.

Last edited: Oct 4, 2005
3. Oct 4, 2005

### neurocomp2003

attempt to show by successive squaring

4. Oct 4, 2005

### Icebreaker

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

5. Oct 5, 2005

### Muzza

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
6. Oct 5, 2005

### neurocomp2003

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

7. Oct 5, 2005

### 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.

Last edited by a moderator: Oct 5, 2005
8. Oct 5, 2005

### 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.

9. Oct 5, 2005

### Muzza

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.

10. Oct 5, 2005

### Icebreaker

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

11. Dec 20, 2009

### krogi

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 ....

12. Dec 20, 2009

### krogi

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 )

13. Dec 20, 2009

### krogi

Re: [SOLVED] Strong Pseudo-Primes

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