What is the smallest natural number n for a^(3n)=a (mod 85)?

[papacy]

Homework Statement

Find the smallest natural number n such that: a^(3n)=a (mod 85) for each integer a.
Justify your answer.

Homework Equations

The Attempt at a Solution

because 85=17 . 5 and gcd (5,17)=1 we have to find the n such:

a^(3n)=a (mod 5) and a^(3n)=a (mod 17).

From Fermat theorem we know that a^(17)=a (mod 17) and a^(5)=a (mod 5)

so we have: a^(5)=a^(3n) (mod 5) and a^(17)=a^(3n)(mod 17).

I don't now how to continue and find the smallest natural n.

 

[Petek]

You've already observed that it suffices to find a minimal n such that $a^{3n} \equiv a \pmod{5}$ and $a^{3n} \equiv a \pmod{17}$. Here's a hint about how to do so:

You already know that $a^{5} \equiv a \pmod{5}$. Show that $a^9 \equiv a \pmod{5}, a^{13} \equiv a \pmod{5}$ and so on.

Similarly, you know that $a^{17} \equiv a \pmod{17}$. Show that $a^{33} \equiv a \pmod{17}$, and so on.

Use the above to find the least exponent 3n such that $a^{3n} \equiv a \pmod{5}$ and $a^{3n} \equiv a \pmod{17}$.

Please post again if you have any questions.

 

[papacy]

i just do it. i find a^(33)=a(mod5) and a^(33)=a(mod17)
now can i say that 3n=33 and n=11. is that right ?

 

[Petek]

i just do it. i find a^(33)=a(mod5) and a^(33)=a(mod17)
now can i say that 3n=33 and n=11. is that right ?

I got the same answer.