Abstract-Algebra-1-Fermats Little Theorem and Eulers Theorem, guaranteed and verified 100% Pass

1


Fermat’s Little Theorem and Euler’s Theorem

Theorem: In any field, 𝐹, the non-zero elements, 𝑈, form a group under the
field multiplication.


Proof:

0. 𝑈 is closed under multiplication since if 𝑥, 𝑦 ∈ 𝑈, then by definition 𝑥 ≠ 0
and 𝑦 ≠ 0. But then 𝑥𝑦 ≠ 0 otherwise 𝐹 would have zero divisors. So
𝑥𝑦 ∈ 𝑈.
1. The multiplication in 𝐹 is associative since 𝐹 is also a ring.
2. The identity element 1 ∈ 𝐹 is in 𝑈 since it’s non-zero.

3. If 𝑥 ∈ 𝑈 then by definition 𝑥 is a unit and has a non-zero inverse which is also
in 𝑈.
Hence, 𝑈 is a group under the field multiplication.


In particular, the non-zero elements of ℤ𝑝 , 𝑝 being a prime number, form a
group. Thus, {1, 2, … , 𝑝 − 1} is a group of order 𝑝 − 1 under multiplication
modulo 𝑝.
Since the order of any element of the group must divide the order of the group, if
𝑎 ≠ 0, 𝑎 ∈ ℤ𝑝 then 𝑎𝑝−1 = 1 in ℤ𝑝 .
Since ℤ𝑝 is isomorphic to the group of cosets:

{𝑝ℤ, 1 + 𝑝ℤ, 2 + 𝑝ℤ, …, (𝑝 − 1) + 𝑝ℤ}.
This gives us: 𝑎𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝).



Note: the notation 𝑎𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝) read as "𝑎𝑝−1 is congruent to 1 modulo
𝑝”, is often used in place of 𝑎𝑝−1 = 1 (𝑚𝑜𝑑 𝑝).

, 2


Thus we have:

Little Theorem of Fermat: If 𝑎 ∈ ℤ and 𝑝 is prime not dividing 𝑎, then 𝑝
divides 𝑎𝑝−1 − 1, that is, 𝑎𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝) for 𝑎 ≢ 0 (𝑚𝑜𝑑 𝑝).



Corollary: If 𝑎 ∈ ℤ, then 𝑎𝑝 ≡ 𝑎 (𝑚𝑜𝑑 𝑝) for any prime 𝑝.



Proof: If 𝑎 ≢ 0 (𝑚𝑜𝑑 𝑝) then this follows from the previous theorem.

If 𝑎 ≡ 0 (𝑚𝑜𝑑 𝑝) then both sides are 0 modulo 𝑝.




Ex. Find the remainder of 8100 when divided by 13, i.e. find 8100 (𝑚𝑜𝑑 13).



We know by the The Little Theorem of Fermat that when 𝑝 = 13 and
𝑎 = 8 we have: 813−1 = 812 ≡ 1 (𝑚𝑜𝑑 13).
Thus: (812 )𝑏 ≡ 1 (𝑚𝑜𝑑 13) for any integer 𝑏.
Write:

8100 = (812 )8 (84 ) ≡ (1)8 (84 )
≡ 84 ≡ (−5)4
≡ (−25)2 (−25)2 ≡ (25)2 (25)2
≡ (−1)2 (−1)2 ≡ 1 (𝑚𝑜𝑑 13).