# Homework Help: Number of theory modulo

1. Oct 17, 2012

### papacy

1. The problem statement, all variables and given/known data

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

2. Relevant equations

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

2. Oct 17, 2012

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

3. Oct 18, 2012

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

4. Oct 18, 2012