# Fermat's Little Theorem Help

• Oct 26th 2008, 10:50 AM
Rafael Almeida
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.
• Oct 26th 2008, 01:32 PM
ThePerfectHacker
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)$
• Oct 26th 2008, 04:12 PM
NonCommAlg
$\color{red}(*)$ first note that if $d \mid n,$ then $a^d - 1 \mid a^n - 1.$

Quote:

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.

Quote:

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

Quote:

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.
• Oct 27th 2008, 10:13 AM
Rafael Almeida
Thank you two, this solves it.