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

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

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