Intermediate Modular Arithmetic

MathDash
Last updated 2025-04-09

1 Lecture Notes

s h
Modular arithmetic goes way deeper than the introductory module you worked through

y
previously. Ever wonder why the last digit of 3𝑥 cycles every 4 powers? This handout

a l
dives deeper into some very powerful tools that we can use to solve modular arithmetic
problems.

hD O n
1.1 Fermat’s Little Theorem

a t e
To better understand Fermat’s Little Theorem, let’s explore it with some examples.

Example 1.1

s
y M l U
Let 𝑝 = 5 and 𝑥 = 2. Then:

25−1 = 24 = 16 ≡ 1 ( mod 5)

B rna
Example 1.2
Let 𝑝 = 7 and 𝑥 = 3. Then:

te 37−1 = 36 = 729 ≡ 1 ( mod 7)

In
Example 1.3
Let 𝑝 = 11 and 𝑥 = 4. Then:

411−1 = 410 = 1048576 ≡ 1 ( mod 11)

Example 1.4
Let 𝑝 = 13 and 𝑥 = 5. Then:

513−1 = 512 = 244140625 ≡ 1 ( mod 13)

Remark 1.5. From the examples above, it seems like for any prime number 𝑝 and any in-
teger 𝑥 not divisible by 𝑝, 𝑥 𝑝− 1 ≡ 1 ( mod 𝑝) . This is a direct application of Fermat’s Little
Theorem.

1
MathDash (Last updated 2025-04-09) Intermediate Modular Arithmetic

Theorem 1.6 (Fermat’s Little Theorem)

If 𝑝 is a prime number and 𝑎 is an integer not divisible by 𝑝, then:

𝑎 𝑝−1 ≡ 1 ( mod 𝑝)

Remark 1.7. Fermat’s Little Theorem is useful for simplifying large exponents modulo a
prime.

1.2 The Totient Function

Definition 1.8 (Euler’s Totient Function)
The Euler’s totient function 𝜙(𝑛) , pronounced ”phi of n”, is defined as the number
of positive integers up to 𝑛 that are coprime to 𝑛.

Example 1.9

s h y
D a
So, 𝜙( 12) = 4.

n l
Calculate 𝜙( 12) : The numbers less than 12 that are coprime to 12 are: 1, 5, 7, and 11.

a t h O
We can actually calculate the Totient Function more directly than having to manually
list out each possibility.

e
s
To understand how the numbers are grouped, consider that for a number 𝑛, the to-
tient function counts the integers up to 𝑛 that are coprime to 𝑛. If 𝑛 has prime factors

M U
𝑝1 , 𝑝2 , . . . , 𝑝𝑘 , then any number that is not coprime to 𝑛 must be divisible by at least one
of these prime factors.

y l
For each prime factor 𝑝𝑖 , the fraction of numbers up to 𝑛 that are divisible by 𝑝𝑖 is 𝑝1 .

B rna
𝑖
Therefore, the fraction of numbers that are not divisible by 𝑝𝑖 is 1 − 𝑝1 .
𝑖

To find the fraction of numbers that are coprime to 𝑛, we multiply these fractions to-
gether for all distinct prime factors of 𝑛:

te 
1−
1

1−
1

··· 1−

1


In
𝑝1 𝑝2 𝑝𝑘

Multiplying this fraction by 𝑛 gives us the number of integers up to 𝑛 that are coprime
to 𝑛. Thus, the formula for Euler’s Totient Function is:
    
1 1 1
𝜙(𝑛) = 𝑛 1 − 1− ··· 1−
𝑝1 𝑝2 𝑝𝑘

where 𝑝1 , 𝑝2 , . . . , 𝑝𝑘 are the distinct prime factors of 𝑛.

For 𝑛 = 12, the prime factors are 2 and 3. Applying the formula:
  
1 1
𝜙( 12) = 12 1 − 1−
2 3

1 2
= 12 · ·
2 3
2
MathDash (Last updated 2025-04-09) Intermediate Modular Arithmetic

1
= 12 ·
3
=4

Thus, 𝜙( 12) = 4.

Remark 1.10. The totient function is multiplicative, meaning if gcd (𝑚, 𝑛) = 1, then 𝜙(𝑚𝑛) =
𝜙(𝑚) · 𝜙(𝑛) .

Example 1.11
Let’s verify that the totient function is multiplicative by calculating 𝜙( 15) in two dif-
ferent ways.

First, calculate 𝜙( 15) directly using the formula. The prime factors of 15 are 3 and 5:

h
  
1 1

s
𝜙( 15) = 15 1 − 1−
3 5

a ly = 15 ·
2
·
4

D n
3 5
8

h O
= 15 ·
15

a t s e
=8

Now, calculate 𝜙( 15) using the multiplicative property. Since 15 = 3×5 and gcd ( 3, 5) =

M
1, we have:

y l U
Calculate 𝜙( 3) and 𝜙( 5) :
𝜙( 15) = 𝜙( 3) · 𝜙( 5)

B rna
 
1 2
𝜙( 3) = 3 1 − =3· =2
3 3

e
 
1 4

t
𝜙( 5) = 5 1 − =5· =4
5 5

In
Therefore:
𝜙( 15) = 𝜙( 3) · 𝜙( 5) = 2 · 4 = 8

Both methods give us the same result, confirming that the totient function is indeed
multiplicative.

1.3 Euler’s Theorem

3
MathDash (Last updated 2025-04-09) Intermediate Modular Arithmetic

Example 1.12
Let’s compute 𝜙( 10) .

The prime factors of 10 are 2 and 5:

  
1 1
𝜙( 10) = 10 1 − 1−
2 5

1 4
= 10 · ·
2 5
4
= 10 ·
10
=4

h
Thus, 𝜙( 10) = 4.

Example 1.13

a s ly
Now, let’s compute 1𝜙( 10) , 3𝜙( 10) , 7𝜙( 10) , and 9𝜙( 10) modulo 10.

hD O n 14 ≡ 1 ( mod 10)

a t s e
34 = 81 ≡ 1
74 = 2401 ≡ 1
94 = 6561 ≡ 1
( mod 10)
( mod 10)

M
( mod 10)

l U
As we can see, 14 , 34 , 74 , and 94 are all congruent to 1 modulo 10.

y
B rna
Theorem 1.14 (Euler’s Theorem)
If 𝑛 is a positive integer and 𝑎 is an integer coprime to 𝑛, then:

e
𝑎𝜙(𝑛) ≡ 1 ( mod 𝑛)

t
where 𝜙(𝑛) is the Euler’s totient function.

In
Proof. Let 𝑛 be a positive integer and 𝑎 be an integer coprime to 𝑛. We need to show
that:
𝑎𝜙(𝑛) ≡ 1 ( mod 𝑛)
where 𝜙(𝑛) is the Euler’s totient function.

Consider the set of integers that are coprime to 𝑛:

𝑆 = {𝑥1 , 𝑥2 , . . . , 𝑥𝜙(𝑛) }

where gcd (𝑥𝑖 , 𝑛) = 1 for all 𝑖 .

Since 𝑎 is coprime to 𝑛, the product 𝑎 · 𝑥𝑖 is also coprime to 𝑛. Therefore, the set:

𝑎𝑆 = {𝑎 · 𝑥1 , 𝑎 · 𝑥2 , . . . , 𝑎 · 𝑥𝜙(𝑛) }
4
MathDash (Last updated 2025-04-09) Intermediate Modular Arithmetic

is a permutation of the set 𝑆 modulo 𝑛.

Taking the product of all elements in 𝑆 and 𝑎𝑆 , we have:

𝑥1 · 𝑥2 · . . . · 𝑥𝜙(𝑛) ≡ (𝑎 · 𝑥1 ) · (𝑎 · 𝑥2 ) · . . . · (𝑎 · 𝑥𝜙(𝑛) ) ( mod 𝑛)

Since 𝑎𝑆 is a permutation of 𝑆 , the products of the elements are congruent modulo 𝑛:

𝑥1 · 𝑥2 · . . . · 𝑥𝜙(𝑛) ≡ 𝑎𝜙(𝑛) · (𝑥1 · 𝑥2 · . . . · 𝑥𝜙(𝑛) ) ( mod 𝑛)

Canceling the common product 𝑥1 · 𝑥2 · . . . · 𝑥𝜙(𝑛) (which is coprime to 𝑛) from both sides,
we get:
1 ≡ 𝑎𝜙(𝑛) ( mod 𝑛)

Thus, we have proved that:

h
𝑎𝜙(𝑛) ≡ 1 ( mod 𝑛)

s
□

Example 1.15

a ly
hD O n
Let 𝑛 = 10 and 𝑎 = 3. Since gcd ( 3, 10) = 1, and 𝜙( 10) = 4:

34 = 81 ≡ 1

t
( mod 10)

a e
Remark 1.16. Euler’s Theorem generalizes Fermat’s Little Theorem to any modulus 𝑛.

s
M l U
Example 1.17
Determine the remainder when 9123 is divided by 50 using Euler’s Theorem.

y
B rna
First, calculate 𝜙( 50) :
  
1 1 1 4
𝜙( 50) = 50 1 − 1− = 50 · · = 20
2 5 2 5

te
Since gcd ( 9, 50) = 1, by Euler’s Theorem:

In
920 ≡ 1 ( mod 50)

Now, express 123 as a multiple of 20 plus a remainder:

123 = 20 · 6 + 3

Thus:
9123 = ( 920 ) 6 · 93 ≡ 16 · 93 ≡ 93 ( mod 50)

Calculate 93 :
93 = 729 ≡ 29 ( mod 50)

Therefore:
9123 ≡ 29 ( mod 50)
5
MathDash (Last updated 2025-04-09) Intermediate Modular Arithmetic

Remark 1.18. Using Euler’s Theorem and the totient function can greatly simplify computa-
tions involving large exponents.

1.4 Wilson’s Theorem

Theorem 1.19 (Wilson’s Theorem)
If 𝑝 is a prime number, then:

( 𝑝 − 1) ! ≡ −1 ( mod 𝑝)

Example 1.20
Let 𝑝 = 5. Then:
( 5 − 1) ! = 4! = 24

s h y
24 ≡ −1 ( mod 5)

D a n l
Remark 1.21. Wilson’s Theorem provides a necessary and sufficient condition for a number
to be prime. If 𝑛 is a composite number, then (𝑛 − 1) ! is not congruent to −1 modulo 𝑛.

t h O
Proof. To prove Wilson’s Theorem, we need to show that for any prime number 𝑝, ( 𝑝 −

e
1) ! ≡ −1 ( mod 𝑝) .

a s
Consider the set of integers {1, 2, 3, . . . , 𝑝 − 1}. Each element in this set has a unique
multiplicative inverse modulo 𝑝. Specifically, for each 𝑎 in the set, there exists an integer

y M l U
𝑏 such that 𝑎𝑏 ≡ 1 ( mod 𝑝) .
Since 𝑝 is prime, the only elements in the set that are their own inverses are 1 and 𝑝 − 1

B rna
because:

𝑎2 ≡ 1 ( mod 𝑝) =⇒ 𝑎2 − 1 ≡ 0 ( mod 𝑝) =⇒ (𝑎 − 1)(𝑎 + 1) ≡ 0 ( mod 𝑝)

Given that 𝑝 is prime, this implies 𝑎 ≡ 1 ( mod 𝑝) or 𝑎 ≡ 𝑝 − 1 ( mod 𝑝) .

te
For all other elements 𝑎 in the set, there exists a distinct 𝑏 ≠ 𝑎 such that 𝑎𝑏 ≡ 1 ( mod 𝑝) .
Therefore, we can pair up the elements of the set {1, 2, 3, . . . , 𝑝− 1} into (𝑎, 𝑏) pairs where

In
𝑎𝑏 ≡ 1 ( mod 𝑝) .
When we take the product of all elements in the set, each pair (𝑎, 𝑏) will contribute a
factor of 1 modulo 𝑝:
Ö
1 · 2 · 3 · · · (𝑝 − 1) ≡ ( 1 · ( 𝑝 − 1)) · (𝑎𝑏) ≡ ( 1 · ( 𝑝 − 1)) · 1 ≡ (𝑝 − 1) ( mod 𝑝)
𝑎≠1,𝑝−1

Thus, we have:
(𝑝 − 1) ! ≡ (𝑝 − 1) ( mod 𝑝)

Since 𝑝 − 1 ≡ −1 ( mod 𝑝) , we conclude that:

( 𝑝 − 1) ! ≡ −1 ( mod 𝑝)

This completes the proof of Wilson’s Theorem. □

6
MathDash (Last updated 2025-04-09) Intermediate Modular Arithmetic

2 Advanced Examples
Example 2.1
Use Wilson’s Theorem to find the remainder when 83! is divided by 89.

Solution. Since 89 is a prime number, by Wilson’s Theorem, we have:

( 89 − 1) ! ≡ −1 ( mod 89)

This means:
88! ≡ −1 ( mod 89)

We can express 88! in terms of 83!:

88! = 88 × 87 × 86 × 85 × 84 × 83!

Thus, we have:

s h y
a l
88 × 87 × 86 × 85 × 84 × 83! ≡ −1 ( mod 89)

D n
(−1) × (−2) × (−3) × (−4) × (−5) × 83! ≡ −120 × 83! ≡ −1 ( mod 89)
83! ≡ 120−1 ( mod 89)

t h O
To find the modular inverse of 120 modulo 89, we need to find an integer 𝑥 such that:

a e
s
120𝑥 ≡ 1 ( mod 89)

y M l U
We use guess and check or the extended euclidean algorithm to find that the modular
inverse is 23.

B rna
Therefore, the remainder when 83! is divided by 89 is:

23

te
3 Practice Problems

In
Example 3.1
Use Fermat’s Little Theorem to find the remainder when 3100 is divided by 7.

Solution. By Fermat’s Little Theorem, since 7 is a prime number and 3 is not divisible by
7, we have:
37−1 = 36 ≡ 1 ( mod 7)
Now, we can write 100 as:
100 = 6 · 16 + 4
Thus,
3100 = ( 36 ) 16 · 34 ≡ 116 · 34 ≡ 34 ( mod 7)
Calculate 34 :
34 = 81
7
MathDash (Last updated 2025-04-09) Intermediate Modular Arithmetic

Now, find the remainder when 81 is divided by 7:

81 ÷ 7 = 11 R 4

Thus,
3100 ≡ 4 ( mod 7)

Example 3.2
Calculate 𝜙( 30) using Euler’s Totient Function.

Solution. First, find the prime factorization of 30:

30 = 2 × 3 × 5

s h
Using the formula for Euler’s Totient Function:

y
a l
   
1 1 1
𝜙( 30) = 30 1 − 1− 1−
2 3 5

D
Calculate each term:

h O n 1 1 1 2 1 4

t
1− = , 1− = , 1− =
2 2 3 3 5 5

a e
Now, multiply the results:

M U s 𝜙( 30) = 30 ·
1
2
·
2
3
·
4
5
= 30 ·
30
8
=8

y l
Thus, 𝜙( 30) = 8.

B rna
te
In