NUMBER THEORY

Special Congruences
Lesson 5: Wilson’s Theorem and Euler’s Theorem

Specific Objectives

1. Prove the theorems in solving congruences involving prime and coprime numbers.
2. Solve problems involving Wilson’s and Euler’s Theorems using step-by-step solutions.
3. Demonstrate perseverance in solving challenging theory problems using Wilson’s and Euler’s
Theorems.
Special congruences refer to congruence relationships that occur under specific conditions and reveal
deeper properties of integers, especially in relation to prime numbers. Unlike general congruence rules that
apply broadly, these special congruences hold only when certain mathematical constraints are met—such
as the number being prime, or two numbers being coprime. These congruences are considered "special"
because they often lead to important theorems, shortcuts in computation, or are used to prove the primality
of numbers. They form the basis for many classical results and modern applications, including
cryptographic algorithms.

Discussions
In the rich history of number theory, certain theorems stand out for their elegance and foundational
significance. One such result is Wilson’s Theorem, a striking characterization of prime numbers. First stated
in Meditationes Algebraicae (1770) by Edward Waring, an accomplished English mathematician, this
theorem was based on an observation shared by one of his students, John Wilson. Though Waring himself
did not provide a proof, the theorem gained attention for its deep insight into the nature of primes. It would
later bear Wilson’s name, highlighting a fascinating relationship between factorials and prime numbers—
laying yet another cornerstone in the study of arithmetic and modular congruences.

Wilson’s Theorem. If p is a prime, then (𝑝 − 1)! ≡ −1(𝑚𝑜𝑑 𝑝).

This means that the factorial of one less than a prime number, when divided by that prime, leaves a
remainder of -1.

Now let’s prove that if p is prime, then, (𝑝 − 1)! ≡ −1(𝑚𝑜𝑑 𝑝).

Proof:
Let a be any integer such that:

𝑎 ∈ { 1, 2, 3, … , 𝑝 − 1}
We're considering all the positive integers less than p, since factorial means multiplying them all together.
Because p is prime, all these numbers are relatively prime to p, that means each one has a multiplicative
inverse modulo p.

2
 NUMBER THEORY

Every a has a unique inverse a' such that 𝑎 𝑎′ ≡ 1 (𝑚𝑜𝑑 𝑝).

In modular arithmetic, an inverse of a number a mod p is a number a' such that:

𝑎 𝑎′ ≡ 1 (𝑚𝑜𝑑 𝑝)
Because p is prime, the equation ax≡1 mod p has unique solution or each a with 1 ≤ 𝑎 ≤ 𝑝. So each
number less than p has a unique modular inverse.
Can a number be its own inverse? That is, can:

𝑎2 ≡ 1 (𝑚𝑜𝑑 𝑝)
This implies:

𝑎2 − 1 ≡ 0 (𝑚𝑜𝑑 𝑝)(𝑎 − 1)(𝑎 + 1) ≡ 0 (𝑚𝑜𝑑 𝑝)

Since p is prime, this equation only holds if:

𝑎 ≡ 1 (𝑚𝑜𝑑 𝑝)
or

𝑎 ≡ −1 (𝑚𝑜𝑑 𝑝) → 𝑎 = 𝑝 − 1
So only a=1 and a=p-1 are self- inverses. All the other numbers must pair with a different number a' such
that

𝑎 𝑎′ ≡ 1 (𝑚𝑜𝑑 𝑝)
Now we take the rest of the numbers 2, 3,…,𝑝 − 2 (excluding 1 and 𝑝 − 1 and pair them with their unique
inverses 𝑎′ , where 𝑎 ≠ 𝑎′ .
For each such pair:

𝑎 𝑎′ ≡ 1 (𝑚𝑜𝑑 𝑝)
𝑝−3
If there are such pairs, then multiplying all the pairs gives:
2

(𝑎1 ∙ 𝑎′ 1 )(𝑎2 ∙ 𝑎′ 2 ) … (𝑎𝑘 ∙ 𝑎′ 𝑘 ) ≡ 1 ∙ 1 ∙ … ∙ 1 ≡ 1 (𝑚𝑜𝑑 𝑝)

Now multiply all the numbers from 1 to 𝑝 − 1:

1 ∙ 2 ∙ 3 … (𝑝 − 1) = (𝑝 − 1)!
Rewriting the product:
(𝑝 − 1)! = (1) ∙ (𝑝 − 1) ∙ 1 ∙ 1 ∙∙∙/≡ (𝑝 − 1)(𝑚𝑜𝑑 𝑝)

Since 𝑝 − 1 ≡ −1 𝑚𝑜𝑑 𝑝 ,we conclude:

(𝑝 − 1)! ≡ −1(𝑚𝑜𝑑 𝑝)

3
 NUMBER THEORY

Example 1.
𝑝−3
Specifically, let us take 𝑝 = 13. It is possible to divide the integers 2, 3,…,11 into = 5 pairs, each
2
product of which is congruent to 1 modulo 13. To write these congruences out explicitly:
2 7 ≡ 1 (𝑚𝑜𝑑 13)

3 9 ≡ 1 (𝑚𝑜𝑑 13)

4 10 ≡ 1 (𝑚𝑜𝑑 13)
5 8 ≡ 1 (𝑚𝑜𝑑 13)

6 11 ≡ 1 (𝑚𝑜𝑑 13)

Multiply these congruences gives the result:

11! = (2 7)(3 9)(4 10)(5 8)(6 11) ≡ 1(𝑚𝑜𝑑 13)
12! ≡ 12 ≡ −1 (𝑚𝑜𝑑 13)
Thus, (𝑝 − 1)! ≡ −1 (𝑚𝑜𝑑 𝑝), with 𝑝 = 13

Example 2: Using Wilson’s Theorem, show that 63! ≡ −1 𝑚𝑜𝑑 71.

(𝑝 − 1)! ≡ −1 (𝑚𝑜𝑑 𝑝)

(71 − 0)! ≡ −1 (𝑚𝑜𝑑 71)

70! ≡ −1( 𝑚𝑜𝑑 71)

70 ∙ 69 ∙ 68 ∙ 67 ∙ 66 ∙ 65 ∙ 64 ∙ 63! ≡ −1 (𝑚𝑜𝑑 71)

−1 ∙ −2 ∙ −3 ∙ −4 ∙ −5 ∙ −6 ∙ −7 ∙ 63! ≡ −1 (𝑚𝑜𝑑 71)

−5040 ∙ 63! ≡ −1 (𝑚𝑜𝑑 71)

63! ≡ −1 (𝑚𝑜𝑑 71) ∙ −5040

63! ≡ 5040 (𝑚𝑜𝑑 71)

63! ≡ 70 (𝑚𝑜𝑑 71)

63! ≡ −1 (𝑚𝑜𝑑 71)

Example 3: Find the remainder when 15! is divided by 17.
For our solution:
(p-1)! ≡ -1 (mod 17)
(17-1)! ≡ -1 (mod 17)
16 x 15! ≡ -1 (mod 17)

4
 NUMBER THEORY

16 x 16 = 256 p→ ≡ 1 (mod 17)

15! ≡ -1 x 16 (mod 17)
15! ≡ -16 (mod 17)
15! ≡ 1 (mod 17)
The final answer is 1.

We’ve just explored and learned about Wilson’s Theorem — a neat little test for prime numbers. But here’s
a question for you: What if we wanted a theorem that works not just for primes, but for any number we
choose?

Wouldn’t that be more exciting and useful? Well, lucky for us, Euler thought of that too! So, let’s keep the
momentum going and discover Euler’s Theorem — a powerful tool that takes what we’ve learned and
makes it work for even more numbers. Ready to dive in?

In number theory, Euler's Theorem (also called the Fermat–Euler Theorem or Euler's Totient Theorem)
says that if two positive integers 𝑎 and 𝑛 are coprime (meaning their greatest common divisor is 1), then:
𝑎𝜙(𝑛) ≡ 1 (𝑚𝑜𝑑 𝑛).

Here, 𝜙(𝑛) represents Euler's Totient Function, which counts how many numbers less than 𝑛 are coprime
to it. In other words, raising 𝑎 to the power of 𝜙(𝑛) will leave a remainder of 1 when divided by 𝑛.
Euler's Totient Function, also known as the Phi function, is a function that counts how many positive
whole numbers less than 𝑛 are coprime to 𝑛 — meaning their greatest common divisor (GCD) with 𝑛 is 1.
In other words, 𝜙(𝑛) is the number of positive integers a such that:

1≤ 𝑎<𝑛
and

gcd(𝑎, 𝑛)=1.

Now take a look at this!

Suppose a is relatively prime to 10 that is n. Since ϕ(10) = 4, Euler's theorem says that 𝑎4 ≡ 1 (𝑚𝑜𝑑 10),
the units digit of 𝑎4 is always 1.
The numbers less than 10: 1, 2, 3, 4, 5, 6, 7, 8, 9. Now, checking which of these have gcd = 1 with 10, let’s
do a listing method:

gcd (1, 10) = 1

gcd (2, 10) = 2

gcd (3, 10) = 1

5
 NUMBER THEORY

gcd (4, 10) = 2

gcd (5, 10) = 5

gcd (6, 10) = 2

gcd (7, 10) = 1

gcd (8, 10) = 2

gcd (9, 10) = 1

The numbers marked with check are coprime to 10: 1, 3, 7, 9 which in total are 4 numbers. That’s why
ϕ(10) = 4, where a can be any value or number less than 10 that are relatively prime to 10, and they satisfy
Euler's theorem.
What if we want a larger number than 10 like 30, do we have to list it all? We don’t want that!
Let’s put n = 30 and a = 11. Now, we first find the prime factorization of 30, which is 2, 3, and 5.
Using the Euler’s Totient Function Formula,
1 1 1 1
𝜙(𝑛) = 𝑛 (1 − ) (1 − ) (1 − ) … (1 − )
𝑝1 𝑝2 𝑝3 𝑝𝑚
then,
1 1 1
𝜙(30) = 30 (1 − ) (1 − ) (1 − )
2 3 5
1 2 4
= 30 × × ×
2 3 5
8
= 30 ×
30
=8
There are 8 numbers less than 30 that are coprime to 30. To solve this, we will use modular arithmetic and
laws of exponents 𝑎𝑚𝑛 = (𝑎𝑚 )𝑛 .

11𝜙(30) = 118 = (112 )4 = 1214 = 14

= 1 (𝑚𝑜𝑑 30)
Now we will get:

114 ≡ 1 (𝑚𝑜𝑑 30)

𝑎8 ≡ 1 (𝑚𝑜𝑑 30)

Lemma. Let 𝑛 > 1 and (𝑎, 𝑛) = 1. If 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) are the positive integers less than n
and relatively prime to n, then 𝑎𝑎1 , 𝑎𝑎2 , … 𝑎𝑎𝜙(𝑛) are congruent modulo n to
𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) in some order.

6
 NUMBER THEORY

We want to show that when you multiply a number a (that’s coprime to n) by each number that’s also
coprime to n, and then take the remainder when divided by n, you’ll still get the same set of numbers —
just in a different order.

Theorem 7.2 (The function 𝜙 is a multiplicative function) guarantees that each of the 𝑎𝑎𝑖
is relatively prime to n.

Theorem 7.2 says that if two numbers are each relatively prime to 𝑛, then their product is also relatively
prime to 𝑛. In the lemma, we start with a number 𝑎 that is coprime to 𝑛, and a list of all the numbers less
than 𝑛 that are also coprime to 𝑛. The lemma says that if we multiply each of these numbers by 𝑎, the new
results (modulo 𝑛) will still be coprime to 𝑛, and will just be the same original numbers, but maybe in a
different order. Theorem 7.2 is important because it guarantees that after we multiply, we still have numbers
that are coprime to 𝑛. Without this property, we couldn’t be sure that the new set matches the original set.

We start by listing the 𝜙(𝑛) positive integers less than 𝑛 that are coprime to it — call them
𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛)

Then, we multiply each of these by a fixed number 𝑎 (where gcd(𝑎, 𝑛)=1) and reduce modulo 𝑛 forming:
𝑎𝑎1 , 𝑎𝑎2 , … 𝑎𝑎𝜙(𝑛)

Now, we check whether any two of these numbers could be congruent. For if:
𝑎𝑎𝑖 ≡ 𝑎𝑎𝑗 (𝑚𝑜𝑑 𝑛)

with 1 ≤ 𝑖 < 𝑗 ≤ 𝜙(𝑛) and gcd(𝑎, 𝑛)=1, then we can cancel out 𝑎, leading to
𝑎𝑖 ≡ 𝑎𝑗 (𝑚𝑜𝑑 𝑛)

But because the numbers 𝑎𝑎1 , 𝑎𝑎2 , … 𝑎𝑎𝜙(𝑛) are distinct and coprime to 𝑛, this cannot happen unless 𝑖=𝑗.

Next, for each product 𝑎𝑎𝑖 , there exists a unique integer 𝑏 (where 0 ≤ 𝑏 < 𝑛 such that:

𝑎𝑎𝑖 ≡ 𝑏(𝑚𝑜𝑑 𝑛)
And since both 𝑎 and 𝑎𝑖 are coprime to 𝑛, this 𝑏 must also be one of the numbers in the original set
𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛)

Finally, when we multiply all these congruences together:

𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) ≡ 𝑎𝑎1 , 𝑎𝑎2 , … 𝑎𝑎𝜙(𝑛)(𝑚𝑜𝑑 𝑛)

We can then divide both sides by 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) to get:

1 ≡ 𝑎𝜙(𝑛) (𝑚𝑜𝑑 𝑛)

𝑎𝑎1 , 𝑎𝑎2 , … 𝑎𝑎𝜙(𝑛) are numbers 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) rearranged in some order modulo 𝑛. Meaning, multiplying
each number by 𝑎 doesn’t create new numbers — it just shuffles the existing coprime numbers around in a
different order under modulo 𝑛.

7
 NUMBER THEORY

Now let’s move on to Theorem 7.5 Euler.

Theorem 7.5 Euler. If 𝑛 ≥ 1 and gcd (𝑎, 𝑛) = 1, then 𝑎𝜙(𝑛) ≡ 1 𝑚𝑜𝑑 𝑛.

Let 𝑛 ≥ 1 and let 𝑎 be an integer such that gcd (𝑎, 𝑛) = 1. Consider the set of positive integers less than 𝑛
that are relatively prime to 𝑛. Denote the set as:
𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛)

where 𝜙(𝑛) is Euler’s totient function — the number of integers less than 𝑛 that are coprime to it.
Since gcd (𝑎, 𝑛) = 1 and each 𝑎𝑖 is also coprime to 𝑛, the products 𝑎𝑎1 , 𝑎𝑎2 , … 𝑎𝑎𝜙(𝑛) are also coprime to
𝑛, and each is congruent modulo 𝑛 to some integer in the original set
𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛)

in a different order.

There exists a rearrangement

𝑎𝑎1 ≡ 𝑎′ 1 (𝑚𝑜𝑑 𝑛)
𝑎𝑎2 ≡ 𝑎′ 2 (𝑚𝑜𝑑 𝑛)
𝑎𝑎𝜙(𝑛) ≡ 𝑎′ 𝜙(𝑛) (𝑚𝑜𝑑 𝑛)

where 𝑎′ 1 , 𝑎′ 2 , 𝑎′ 𝜙(𝑛) are precisely the numbers 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) in some order.

Now, multiply all these congruences together,

(𝑎𝑎1 )(𝑎𝑎2 ) … (𝑎𝜙(𝑛) ) ≡ (𝑎′1 𝑎′ 2 𝑎′ 𝜙(𝑛) )(mod n)

On the left side, we can factor out 𝑎𝜙(𝑛) ,

𝑎𝜙(𝑛) × 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) ≡ 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛)

Since the set 𝑎′1 , 𝑎′ 2 , 𝑎′ 𝜙(𝑛) is a rearrangement of 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) their products are equal.

𝑎′1 , 𝑎′ 2 , 𝑎′ 𝜙(𝑛) = 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛)

Therefore, we have

𝑎𝜙(𝑛) × 𝑎′ 1 , 𝑎′ 2 , 𝑎′ 𝜙(𝑛) = 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛)(𝑚𝑜𝑑 𝑛)

Now, since each 𝑎𝑖 is coprime to n, their product is also coprime to 𝑛, meaning gcd (𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) , 𝑛) = 1

This allows us to cancel the common factor 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) from both sides of the congruence, giving:

𝑎𝜙(𝑛) ≡ 1 (𝑚𝑜𝑑 𝑛).

8
 NUMBER THEORY

Example 4. Let n = 9. The positive integers less than and relatively prime to 9 are 1,2,4,5,7, and 8.
These play the role of the integers 𝑎1 , 𝑎2 , … 𝑎𝜙(𝑛) in the proof of Theorem discussed. If 𝑎 = −4, then the
integers 𝑎𝑎𝑖 are -4,-8,-16,-20,-28, and -32 where modulo 9 are

−4 ≡ 5, −8 ≡ 1, −16 ≡ 2, −20 ≡ 7, −28 ≡ 8 , −32 ≡ 4

When these congruences are all multiplied together, we will have
(−4)(−8) (−16)(−20)(−32) ≡ 5 ∙ 1 ∙ 2 ∙ 7 ∙ 8 ∙ 4(𝑚𝑜𝑑 9)
when will become

(1 ∙ 2 ∙ 4 ∙ 5 ∙ 7 ∙ 8)(−4)6 ≡ (1 ∙ 2 ∙ 4 ∙ 5 ∙ 7 ∙ 8)(𝑚𝑜𝑑 9)
Being relatively prime to 9, the six integers 1, 2, 4, 5, 7, 8 may be canceled to give

(−4)6 ≡ 1 (𝑚𝑜𝑑 9)
The validity of this last congruence is confirmed by the calculation

(−4)6 ≡ 46 ≡ 642 ≡ 12 ≡ 1 (𝑚𝑜𝑑 9).

Example 5. Find the last two digits of 3256 .

Finding the last two digits of a number is the same as

3256 ≡ 𝑚𝑜𝑑 100

Since gcd (3,100) = 1, we can use Euler’s Theorem, which says

3𝜙(100) ≡ 1 (𝑚𝑜𝑑 100)

Computing the modulo knowing the prime factors of 100 is 2 and 5, Euler’s Theorem will yield
1 1
𝜙(100) = 100(1 − )(1 − )
2 5
1 4
= 100 × ×
2 5
= 40

Now that we know 𝜙(100) = 40 Euler’s theorem gives

3(40) ≡ 1 (𝑚𝑜𝑑 100)

We need 3256 ≡ 𝑚𝑜𝑑 100. Then use division, 256 = 6 × 40 + 16 where 16 is remainder when 6 is
multiplied by 40.
This means that

3256 ≡ (340 )6 × 316

Since 3(40) ≡ 1 (𝑚𝑜𝑑 100) this simplifies to

9
 NUMBER THEORY

(1)6 × 316 ≡ 316 (𝑚𝑜𝑑 100)

32 = 9 (𝑚𝑜𝑑 100)

34 = (32 )2 = 92 = 81 (𝑚𝑜𝑑 100)

38 = (34 )2 = 812 = 6561 (𝑚𝑜𝑑 100) = 61

316 = (38 )2 = 612 = 3721 (𝑚𝑜𝑑 100) = 21

So, 3256 ≡ 21 𝑚𝑜𝑑 100 which means that the last two digits of 3256 are 21.

Euler’s Theorem generalized the one credited to Fermat, which we proved earlier. For if p is a prime, then

𝜙(𝑝) = 𝑝 − 1

hence, when gcd (𝑎, 𝑝) = 1 we get:

𝑎𝑝−1 ≡ 𝑎𝜙(𝑛) ≡ 1 (𝑚𝑜𝑑 𝑝)

and we will have the following corollary.

Corollary Fermat. If p is a prime and p is 𝑝 ∤ a, then 𝑎𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝).

Example 6. Solve for 151976 mod 23.

𝑎𝑝−1 ≡ 1 mod (n)

a= 15 p= 23
gcd(15,23) = 1 relatively prime

1523−1 ≡ 1 mod (23) by substituting the Fermat's theorem.

1522 ≡ 1 mod (23)

1976 ÷ 22 = 89 r. 18 8 is the remainder when 89 is multiplied by 22

151976 ≡ (1522 )89 × 1518 by exponentiation property of congruence that if a ≡ b mod (n), then
𝑎𝑘 ≡ 𝑏 𝑘 mod (n)

Solve for 1518 mod (23) using successive squaring.

151 = 15 mod (23)

152 ≡ 18 mod (23)

154 ≡ 2 mod (23)

158 ≡ 4 mod (23)

1516 ≡ 16 mod (23)

10
 NUMBER THEORY

To come up with 18 we can now write 18 as a sum of powers of 2.

1518 = 1516 × 152

= 16 × 18
= 288

𝟏𝟓𝟏𝟖 ≡ 12 mod (23)

Example 7. Find the remainder if 241947 is divided by 17.

We can rewrite this as 241947 mod (17)

𝑎𝑝−1 ≡ 1 mod (n)

a= 24 p= 17
gcd(24,17) = 1 relatively prime

2417−1 ≡ 1 mod (17) by substituting the Fermat's theorem.

2416 ≡ 1 mod (17)

1947 ÷ 16 = 121 r. 11 11 is the remainder when 121 is multiplied by 16

241947 ≡ (2416 )121 × 2411 by exponentiation property of congruence that if a ≡ b mod (n), then
𝑎𝑘 ≡ 𝑏 𝑘 mod (n)

Solve for 2411 mod (17) using successive squaring.

241 = 7 mod (17)

242 ≡ 15 mod (17)

243 ≡ 3 mod (17)

244 ≡ 4 mod (23)

248 ≡ 16 mod (23)

To come up with 11 we can now write 11 as a sum of powers of 2:

2411 = 248 × 243

= 16 × 3
= 48

𝟐𝟒𝟏𝟏 ≡ 14 mod (17)

11
 NUMBER THEORY

Instructions:
Solve all problems with complete and rigorous solutions. Justify your steps clearly. Use a separate sheet if
needed.

1. Proof-based Question (Wilson’s Theorem)

Let p be a prime number greater than 2. Prove that (p - 1)! ≡ -1 (mod p).

2. Fermat's Little Theorem

Simplify 5^100 mod 17, let p = 17 and a = 5.

3. Euler's Theorem
Compute 3^φ(40) mod 40, let a = 3, n = 40.

4. Theoretical Comparison
Discuss the differences and relationships among the following theorems:

• Wilson's Theorem
• Fermat's Little Theorem
• Euler's Theorem

5. Challenge Problem
It is known that if (n - 1)! ≡ -1 mod n, then n must be prime.
Use this to construct a primality test based on Wilson's Theorem.
a) Apply your test to check whether n = 11 is prime.
b) Attempt to use the same test on n = 15 and explain why it fails.

Assessment
I. Multiple Choice (10 points)
Directions: Read each question carefully and choose the best answer from the options provided by
encircling the letter. Mark only one answer per question and do not leave any questions unanswered.

1. Which of the following is Wilson’s Theorem?

A. aϕ(n) ≡ 1 mod n
B. (p − 1)! ≡ −1 mod p
C. pn−1 ≡ 1 mod n
D. ap ≡ a mod p

12
 NUMBER THEORY

2. Which of these is a prime number according to Wilson’s Theorem?

A. 6
B. 8
C. 7
D. 9

3. Which theorem uses the totient function ϕ(n)?

A. Fermat’s Little Theorem
B. Wilson’s Theorem
C. Euclid’s Lemma
D. Euler’s Theorem

4. If p = 11, then 10! mod 11 is equal to:

A. 1
B. 0
C. -1
D. 5

5. Euler’s theorem works only when a and n are:

A. Equal
B. Relatively prime
C. Even numbers
D. Both primes

6. What is ϕ(9)?
A. 6
B. 3
C. 9
D. 1

7. Which of the following is NOT true?

A. Wilson’s Theorem only applies to prime numbers
B. Euler’s Theorem applies for any integer
C. ϕ(p) = p − 1 for prime p
D. Euler’s theorem uses modulo arithmetic

13
 NUMBER THEORY

8. If a = 3 and n = 10, then 3ϕ(10) mod 10 equals:

A. 9
B. 1
C. 3
D. 0

9. The value of ϕ(15) is:

A. 15
B. 7
C. 8
D. 4

10. Which of the following is a correct conclusion from Euler’s Theorem?

A. ap ≡ a mod p
B. aϕ(n) ≡ 1 mod n
C. a · a−1 ≡ 0 mod n
D. a · b ≡ 1 mod n

II. True or False (10 points)

Directions: Read each statement carefully. Decide whether the statement is True or False based on your
knowledge of special congruences in number theory.

1. Wilson’s theorem states that a natural number 𝑝 > 1 is prime if and only if (𝑝 − 1)! ≡ 1 𝑚𝑜𝑑 𝑝.
2. Wilson’s theorem applies to all integers, whether prime or composite.
3. If 𝑝 is prime, then (𝑝 − 1)! + 1 is divisible by 𝑝.
4. For a composite number 𝑛, it is always true that (𝑛 − 1)! ≡ −1 𝑚𝑜𝑑 𝑛.
5. Wilson’s theorem can be used to check if a small number is prime, but it is inefficient for large
numbers because calculating factorials is slow.
6. Euler’s theorem states that if and 𝑎 and 𝑛 are coprime, then 𝑎𝜑(𝑛) ≡ 1 𝑚𝑜𝑑 𝑛, where 𝜑(𝑛) is
Euler's totient function.
7. Euler’s theorem is fundamental in the RSA encryption algorithm used in modern cryptography.
8. Euler’s theorem generalizes Fermat’s Little Theorem, which is the special case when 𝑛 is a prime
number.
9. The value of 𝜑(𝑛) is always 𝑛 − 1 for any 𝑛.
10. Euler’s theorem requires that 𝑎 and 𝑛 are not coprime.

14
 NUMBER THEORY

Problem Solving
1. Wilson’s Theorem (Factorial Modulo a Prime)
Compute 16! mod 17.

2. Wilson’s Theorem (Reduced Factorial)

Compute 17! mod 19.

3. Euler’s Theorem (High Exponent Reduction)

Find the remainder when 151976 is divided by 23, 151976 mod 23

15
 NUMBER THEORY

4. Euler’s Theorem (Composite Modulus)

Compute 3100 mod 28.

5. Euler’s Theorem (Last Two Digits)

Determine the last two digits of 7345 mod 100.

16
 NUMBER THEORY

Answer Key:
I. Multiple Choice
1. B
2. C
3. D
4. C
5. B
6. A
7. B
8. B
9. C
10. B

II. True or False

1. False
2. False
3. True
4. False
5. True
6. True
7. True
8. True
9. False
10. False

III. Problem-solving

1. Compute 16! mod 17.

By Wilson’s theorem, for prime p, (p − 1)! ≡ −1 (mod p).
Here p = 17, so (17-1)! = 16! ≡ −1 (mod 17).
Hence 16! Mod 17 = 17 – 1 = 16
Answer: 16

2. Compute 17! mod 19.

Wilson theorems gives (19−1)! = 18! ≡ - 1 (mod 19).
But 18! = 18 x 17!. Therefore 18 x 17! ≡ - 1 (mod 19)
17! ≡ - 1 x 18−1 (mod 19).
Since 18 ≡ - 1 (mod 19), its inverse also -1.
Thus 17! ≡ - 1 x (- 1) = 1 (mod 19).
Answer: 1

3. Compute 𝟏𝟓𝟏𝟗𝟕𝟔 mod 23.

Since gcd (15, 23) = 1, Euler’s Theorem applies.
Euler’s Theorem states: 𝑎ϕ (n) ≡ 1 mod n if gcd (a, n) = 1
Here, a = 15 n = 23

17
 NUMBER THEORY

Since 23 is prime, we get ϕ (23) = 23 – 1 = 22 ⇒ 1522 ≡ 1 mod 23

Reduce the exponent 1976 mod 22
1976 ÷ 22 = 89 remainder 18 ⇒ 1976 ≡ 18 mod 22
Reduce the problem 151976 ≡ 1518 mod 23
Now compute 1518 mod 23
By using of repeated squaring compute powers of 15 mod 23:

151 = 15

152 = 225 mod 23 = 18

154 = (152 ) 2 = 182 = 324 mod 23 = 2

158 = (154 ) 2 = 22 = 4

1516 = (158 ) 2 = 42 = 16

Now multiply powers to get 1518 = 1516 ⋅ 152

• 1516 mod 23 = 16

• 152 mod 23 = 18

1518 mod 23 = 16 ⋅ 18 = 288 mod 23 = 12

Answer: 12

4. Compute 𝟑𝟏𝟎𝟎 mod 28.

gcd(3, 28) = 1 so Euler’s Theorem applies.
Compute ϕ (28) 28 is composite so 28 = 22 ⋅ 7
Euler’s totient function:
1 1 1 6 6
ϕ(28) = 28(1− ) (1− ) = 28 ⋅ ⋅ = 14 ⋅ = 12
2 7 2 7 7
So 312 ≡ 1 mod 28
Reduce the exponent mod 12
100 mod 12 = 4 ⇒ 3100 ≡ 34 mod 28
Compute 34 mod 28
34 = 81 mod 28 ⇒ 81 ÷ 28 = 2 ⋅ 28 = 56 ⇒ 81 – 56 = 25
Answer: 25

5. Compute 𝟕𝟑𝟒𝟓 mod 100.

We'll use Euler’s Theorem, since gcd (7,100)=1.
Compute ϕ(100)
1 1 1 4
100 = 22 ⋅ 52 ⇒ ϕ(100) = 100(1− ) (1− ) = 100 ⋅ ⋅ = 40
2 5 2 5
So 740 ≡ 1 mod 100
Reduce the exponent modulo 40
345 mod 40 = 25 ⇒ 7345 ≡ 725 mod 100
Compute 725 mod 100 using modular exponentiation
We’ll use successive squaring:

18
 NUMBER THEORY

• 71 = 7
• 72 = 49
• 74 = 492 = 2401 mod 100 = 1
• So, 74 ≡ 1 mod 100
Now express 25 as:
25 = 4 ⋅ 6 + 1 ⇒ 725 = (74 )6 ⋅ 71 ≡ 16 ⋅ 7 = 7 mod 100
Answer: 07

19