# Math Help - Fermat's Thm applied

1. ## Fermat's Thm applied

If gcd(a,35) = 1, show that $a^12 equiv/ 1$ (mod 35)
the hint in the book says remember, by Femat's thm: $a^6 equiv/1$ (mod 7) and $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 $5 | a^{12} - 1$ and $7 | a^{12} - 1$ - but how do you put them together?

3. One can show that: If $a \equiv b \ (\text{mod } m_1)$ and $a \equiv b \ (\text{mod } m_2)$, then $a \equiv b \ (\text{mod } \text{lcd}(m_{1}, m_2) )$

Or if you prefer, purely by definitions:
$5 \mid a^{12} - 1 \ \iff \ a^{12} = 1 + 5k_1 \ \iff 7a^{12} = 7 + 35k_1$
$7 \mid a^{12} - 1 \ \iff \ a^{12} = 1 + 7k_2 \ \iff 5a^{12} = 5 + 35k_2$

Add the equations to get: $12a^{12} = 12 + 35(k_1 + k_2) \ \iff 12a^{12} \equiv 12 \ (\text{mod 35})$

Since (12, 35) = 1, we have: $a^{12} \equiv 1 \ (\text{mod } 35)$