
Fermat's Thm applied
If gcd(a,35) = 1, show that $\displaystyle a^12 equiv/ 1$ (mod 35)
the hint in the book says remember, by Femat's thm: $\displaystyle a^6 equiv/1$ (mod 7) and $\displaystyle a^4 equiv/1$ (mod 5)
So since gcd(a,5) = 1 and gcd(a,7) = 1, you can apply Fermat's them  and prove the hint
But thats where I'm stuck  is there another theorem I've forgot where you can multiply the exponent and mod???? is it a property I don't remember??
help!


ok  but how do you show that combined  they are the same as 35 
I understand how $\displaystyle 5  a^{12}  1$ and $\displaystyle 7  a^{12}  1$  but how do you put them together?

One can show that: If $\displaystyle a \equiv b \ (\text{mod } m_1)$ and $\displaystyle a \equiv b \ (\text{mod } m_2)$, then $\displaystyle a \equiv b \ (\text{mod } \text{lcd}(m_{1}, m_2) )$
Or if you prefer, purely by definitions:
$\displaystyle 5 \mid a^{12}  1 \ \iff \ a^{12} = 1 + 5k_1 \ \iff 7a^{12} = 7 + 35k_1$
$\displaystyle 7 \mid a^{12}  1 \ \iff \ a^{12} = 1 + 7k_2 \ \iff 5a^{12} = 5 + 35k_2$
Add the equations to get: $\displaystyle 12a^{12} = 12 + 35(k_1 + k_2) \ \iff 12a^{12} \equiv 12 \ (\text{mod 35})$
Since (12, 35) = 1, we have: $\displaystyle a^{12} \equiv 1 \ (\text{mod } 35)$