SMA3043 ELEMENTARY NUMBER THEORY

SEMESTER 1 2022/2023

FERMAT'S THEOREM, WILSON'S

THEOREM, EULER'S THEOREM

PROF. MADYA DR ROHAIDAH MASRI

DR. NOR HAFIZAH MD HUSIN
FERMAT’S THEOREM

• Pierre de Fermat was a French lawyer.

• He is best known for his Fermat's principle for light propagation and his Fermat's Last
Theorem in number theory, which he described in a note at the margin of a copy of
Diophantus' Arithmetica.

• In number theory, Fermat studied Pell's equation, perfect numbers, amicable numbers
and what would later become Fermat numbers.

• He invented a factorization method— Fermat's factorization method.

Fermat has described a technique for factoring large numbers.
Pierre de Fermat (1601-1665)
Source: Wikipedia

2
FERMAT’S THEOREM
The Fermat’s Factorization Method

• The security of the RSA cryptosystem depends on the difficulty in factoring the encryption modulus n=pq.

• Poor choices of p and q can lead to easily factored values of n, rendering the cryptosystem “cracked.”

• One such situation occurs when p and q are relatively close together.
In this case one can apply the Fermat Factorization Method to find p and q.

Remark:The Fermat method can be applied to arbitrary

odd n to try to find a divisor/complementary divisor pair that
are relatively close together, if such a pair exists.

3
FERMAT’S THEOREM
Fermat’s Factorization Method

4
FERMAT’S THEOREM
The Fermat’s Factorization Method

Example.

5
FERMAT’S THEOREM
The Fermat’s Factorization Method

Example.

Given n = 3977. Write n as a product of two prime numbers.

Answer: 3977 = 41 .97

6
FERMAT’S THEOREM

Theorem 1 (Fermat Theorem)

If p is prime and a is a positive integer with p | a,
then, a p −1  1(mod p ) .

Corollary 1

If p is a prime then, a  a (mod p ) for any integer a.

p

7
FERMAT’S THEOREM

Example.

Solution.
Let p = 11 ; a =5

Note that, 5 does not divide 11. Then,

Then, by Fermat’s theorem,

510  1 (mod11)

8
FERMAT’S THEOREM

Example.

Show that 3201 3 (mod11) .

Solution.

By Fermat’s Theorem,

310  1 (mod11)

9
FERMAT’S THEOREM

Another application of Fermat’s Theorem is can be used as a tool in testing the

primality of a given integer n.

If the congruence an  a (mod n) fails to hold for some a,

Then,
n is necessary composite.

10
FERMAT’S THEOREM

Lemma 1.
If p and q are distinct primes with ap  a (mod q) and aq  a (mod p),
then apq  a (mod pq).

Example

Verify that 2340  1 (mod 341).

11
WILSON’S THEOREM
• This theorem was stated by Ibn al-Haytham (c. 1000 AD).

• In the 18th century, by John Wilson.

• Edward Waring announced the theorem in 1770, although neither he nor his student
Wilson could prove it.

• Lagrange gave the first proof in 1771.

• There is evidence that Leibniz was also aware of the result a century earlier, but he never
published it.
[Source: Wikipedia]

Theorem 2 (Wilson Theorem)

If p is prime, then (p - 1)!  -1 (mod p)

12
WILSON’S THEOREM

Example.

13
WILSON’S THEOREM

Example.

14
WILSON’S THEOREM

Cont.

15
WILSON’S THEOREM
Converse of Wilson’s Theorem

Theorem 3 (Converse of Wilson’s Theorem)

If n ≥ 2 and (n−1)! ≡−1 mod n, then n is prime.

16
EULER’S THEOREM
Leonhard Euler (15 April 1707 – 18 September 1783) was a Swiss
mathematician, physicist, astronomer, geographer, logician and engineer

Euler made many contributions to the field of mathematics, including his

work in number theory.

His number theoretic work was suggested by issues raised by Pierre de Fermat,
as well as his own ideas.

Euler's work in number theory included topics such as the study of

perfect numbers, the quadratic reciprocity law, the so-called Pell
equation, and Fermat's Last Theorem.

Source: Wikipedia

17
EULER’S THEOREM
’s Phi-Function
Euler’

The Fermat’s Theorem has been extended by Euler – congruences with prime moduli, to
arbitrary moduli.

The following definition was introduced by Euler – number-theoretic function.

Definition 1 (Number-Theoretic Function)

For n  1, the number of positive integers not exceeding n that are relatively prime to n, denoted by (n).

Example.

For n = 16,  (16) = 8 :

Then, there are 8 positive integers that not exceed 16, & relatively prime to 16.
1, 3, 5, 7, 9, 11, 13, 15

18
EULER’S THEOREM
Euler’s Phi-Function

Example.

For n = 27,  (27) = 18 :

Then, there are 18 positive integers that not exceed 27, & relatively prime to 27.
1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26

Example.
For n = 30,  (30) = 8 :

Then, there are 8 positive integers that not exceed 30, & relatively prime to 30.
1, 7, 11, 13, 17, 19, 23, 29

19
EULER’S THEOREM
Euler’s Phi-Function

Notes:

1.  (1) = 1 since gcd(1,1) = 1

2.  (p) = p – 1 , if p is a prime number.

3.  (n)  n – 2, if n is a composite numbers.

20
EULER’S THEOREM
Euler’s Phi-Function

Theorem 4
If p is a prime and k  0, then
 (p k
)=p k
−p k −1

 1
= p 1− 
k

 p

Example.

21
EULER’S THEOREM
Euler’s Phi-Function

Lemma 2

Given integers a, b, c, gcd(a, bc) = 1 if and only if gcd(a, b) = 1 and gcd(a, c) = 1.

Theorem 5

The function  is a multiplicative function.

22
EULER’S THEOREM
Euler’s Phi-Function

Theorem 6 (multiplicative function)

 (mn) =  (m)  (n) if and only if gcd (m, n) = 1

23
EULER’S THEOREM
Euler’s Phi-Function

Theorem 7

If the integer n  1 has the prime factorization n = p1k1 p2k2 ... prkr , then
 ( n ) =  ( p1k p2k ... prk ) =  ( p1k )  ( p2k ) ...  ( prk
1 2 r 1 2 r
)
(
= p −p k1
1
k1 −1
1 ) (p k2
2
k2 −1
−p
2 )... ( p
kr
r
kr −1
−p
r )
 1  k2  1 kr  1
= p  1 −  p2  1 −  ... pr  1 − 
k1
1
 p1   p2   pr 
 1  1  1
( 1
k2
2
kr
r )
= p p ... p  1 −  1 −  ...  1 − 
k1

 p1  p2   pr 
 1  1  1
= n  1 −  1 −  ...  1 − 
 p1  p2   pr 

24
EULER’S THEOREM
Euler’s Phi-Function
Example.

25
EULER’S THEOREM
’s Theorem
Recall: Fermat’

26
EULER’S THEOREM

Lemma 3

Let n > 1 and gcd(a, n) = 1. If a1, a2, ..., a(n) are the positive integers less than
n and relatively prime to n, then
aa1, aa2, aa3, ... , a a(n)

are congruent modulo n to a1, a2, ..., a(n) in some order.

Theorem 8 (Euler Theorem)

If n  1 and gcd ( a, n ) = 1 , then

 1 ( mod n )
 (n )
a

27
EULER’S THEOREM

Corollary 2

For prime p, with  ( p ) = p − 1, and gcd ( a, p ) = 1, then

 1 ( mod p )
p −1  ( p)
a a

28
EULER’S THEOREM

Example

29
EULER’S THEOREM

Example

30
EULER’S THEOREM

Example (Cont)

31
EULER’S THEOREM

Example

Solution.

Then,

32