Proving a^1729 = a (mod 1729) for all n

[Icebreaker]

[SOLVED] Strong Pseudo-Primes

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.

 

[krogi]

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

 

[krogi]

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 )

 

[krogi]

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