# Thread: Fermat's Little Theorem Help

1. ## Fermat's Little Theorem Help

Hi all,

I am kind of stuck with these proofs, which seemingly involve FLT ultimately. Since they're more or less related, I'm posting all three:

Let a be some integer. Prove that (let == be the symbol for congruence):

- a^21 == a (mod 15)
- a^7 == a (mod 42)
- if gcd(a,35) = 1 (i.e., a and 35 are coprimes), then a^12 == 1 (mod 35)

After tinkering with the problems a bit, I suspect that the solution involves the GCD of the exponent and the modulus. So, more specifically, I'd like help specially in rewriting the congruences so that the modulus is prime, while keeping it true. That the modulus is prime is obviously required by the FLT hypotesis.

Any help or tip for one or more of the proofs will be greatly appreciated. Thanks in advance.

2. Notice that $\mathbb{Z}_{35}^{\times} \simeq \mathbb{Z}_{5}^{\times} \times \mathbb{Z}_7^{\times} \simeq \mathbb{Z}_4 \times \mathbb{Z}_6$

The group $\mathbb{Z}_4 \times \mathbb{Z}_6$ has property than anything raised to $12$ gives the identity element. Therefore, if $\gcd(a,35)=1$ then $[a]_{35}\in \mathbb{Z}_{35}^{\times}$. It follows that $[a]_{35}^{12} = [1]_{35}$ i.e. $a^{12}\equiv 1(\bmod 35)$

3. $\color{red}(*)$ first note that if $d \mid n,$ then $a^d - 1 \mid a^n - 1.$

Originally Posted by Rafael Almeida

a^21 == a (mod 15)
by FLT: $5 \mid a^5 - a.$ but: $a^5-a=a(a^4 - 1) \mid a(a^{20}-1)=a^{21} - a.$ hence: $5 \mid a^{21} - a. \ \ \ (1)$

by FLT: $3 \mid a^3 - a.$ but: $a^3 - a = a(a^2 - 1) \mid a(a^{20}-1)=a^{21}-a.$ hence: $3 \mid a^{21} - a. \ \ \ (2).$

now (1) and (2) complete the proof.

a^7 == a (mod 42)
by FLT: $7 \mid a^7 - a.$ again by FLT: $2 \mid a^2 -a =a(a-1) \mid a(a^6-1)=a^7 - a,$ and $3 \mid a^3 - a =a(a^2 -1) \mid a(a^6 -1) = a^7 - a.$ so: $42=2 \times 3 \times 7 \mid a^7 - a.$

if gcd(a,35) = 1 (i.e., a and 35 are coprimes), then a^12 == 1 (mod 35)
since $\gcd(a,5)=1,$ by FLT we have: $5 \mid a^4 - 1.$ but $a^4 -1 \mid a^{12}-1.$ thus: $5 \mid a^{12} - 1. \ \ \ (1)$

since $\gcd(a,7)=1,$ by FLT we have: $7 \mid a^6 - 1.$ but: $a^6 - 1 \mid a^{12} - 1.$ thus: $7 \mid a^{12} - 1. \ \ \ (2)$

now (1) and (2) complete the proof.

Q.E.D.

4. Thank you two, this solves it.