Fermat's Little Theorem and Wilson's Theorem

Fermat’s Little
Theorem and
Wilson’s Theorem
Introduction
Pierre de Fermat (1601-1665)
Born in France
AFrench lawyer and Mathematician
University of Orleans
Analytic Geometry, Probability Theory,

Calculus and Number Theory
“Fermat’s Conjecture”
For any integer n>2, the equation

has no positive integer
solutions.
FERMAT’S LAST THEOREM

Fermat’s Little

Theorem
Theorem: Let p be a
prime and suppose that p
does not divide a.
Then,
FERMAT’S LITTLE
THEOREM
FERMAT’S LITTLE THEOREM
A. Fermat's little theorem states that

if p is a prime number, then for any
integer a, the number ap − a is an
integer multiple of p. In the notation
of modular arithmetic, this is
expressed as ap = a mod p
B. If a is not divisible by p, Fermat's
little theorem is equivalent to the
statement that a(p - 1) - 1 is an integer
multiple of p. In symbols, it is expressed
as a(p - 1) = 1 mod p.
Examples:
1. Find the value of 313 mod 11.
Solution:
Since 13 is not divisible by 11, we will
proceed to the 2nd statement above. 11 - 1
= 10. Therefore, 310 = 1 mod 11. Then,
divide 13 by 10 and get the remainder. What
we are doing is that we are reducing the
exponent to a smaller value. 13/10 = 1
remainder 3. This will become 33 mod 11 =
27 mod 11 = 5.
2. 22003 mod 11
Solution:
a(p - 1) = 1 mod p.
11-1=10,
210=1 mod 11
(210)200 (23)
(1) 200 (23)= 8 mod 11= 8
3. 52018 mod 7.
Solution:
Using FLT, 7 - 1 = 6, therefore, 56 = 1
mod 7. Then divide the exponent by 6
and get the remainder. 2018 mod 6 =
2. [Since 2018/6 = 336 remainder 2].
We reduce then the exponent to 2. 52
mod 7 = 25 mod 7 = 4.
4. 43929 mod 13.
Solution:
Using FLT, 13 - 1 = 12, therefore, 412 =
1 mod 13. Then divide the exponent by
12 and get the remainder. 3929 mod 6
= 5. [Since 3929/12 = 327 remainder
5]. We reduce then the exponent to 5.
45 mod 13 = 1024 mod 13 = 10.
5. 32105 mod 17.
Solution:
Using FLT, 17 - 1 = 16, therefore, 316 =
1 mod 17. Then divide the exponent by
16 and get the remainder. 2105 mod
17 = 9. [Since 2015/16 = 131
remainder 9]. We reduce then the
exponent to. 39 mod 17 = 19683 mod
17 = 14.
Method of Successive Squaring for
a k MOD m
Idea is to break the exponent k into a
0
sum of powers of 2 (starting with 2)
k
and break a
in terms of exponential terms as these
powers of 2, computing the powers of 2
by “successively squaring” the previous
term.
85
Example : Compute 7 MOD 41
Solution: We first note that the exponent k = 85.

We first determine the powers of 2 that are less
than this exponent. Starting with, we see that
0 1 2
2  1 , 2  2 , 2  4 , 23  8 , 24  16 , 25  32 , 26  64
7
26  64 2  128  85.
We can stop at since
We now decompose the exponent k into powers
of 2.
85  64  21  64  16  5  64  16  4  1  1  4  16  64
We next write
785 MOD 41  71 4 16  64 MOD 41  (71  7 4  716  764 ) MOD 41
We next compute the needed powers of 7

needed with respect to the modulus 41. The
ones that we will need are indicated by . Note
that arrows are used to indicate the substitutions
from the previous step.
71 MOD 41  7
7 2 MOD 41  49 MOD 41  8
7 4 MOD 41  (7 2 ) 2 MOD 41  (8) 2 MOD 41  64 MOD 41  23
78 MOD 41  (7 4 ) 2 MOD 41  (23) 2 MOD 41  529 MOD 41  37
716 MOD 41  (78 ) 2 MOD 41  (37) 2 MOD 41  1369 MOD 41  16
732 MOD 41  (716 ) 2 MOD 41  (16)2 MOD 41  256 MOD 41  10
764 MOD 41  (732 ) 2 MOD 41  (10) 2 MOD 41  100 MOD 41  18

785 MOD 41  71 4 16  64 MOD 41
 (71  7 4  716  764 ) MOD 41
 (7  23  16  18) MOD 41 Substituti ng from ' s above
 (161  288) MOD 41 Note that 7  23  161 and 16  18  288
 (38  1) MOD 41 Note 161 MOD 41  38 and 288 MOD 41  1
 38 MOD 41
 38 Hence, 785 MOD 41  38
Fermat’s Little Theorem in special cases can
be used to simplify the process of modular
exponentiation. We state it now.
Fermat’s Little Theorem: Let p be a prime

number, a an integer where 1  a  p . Then
1. If gcd( a , p )  1 , then a p 1
MOD p  1 .
p
2. a MOD p  a .
85
 Compute in FLT 7 MOD 41
Solution:
Using FLT, 41 - 1 = 40, therefore, 740 = 1
mod 41. Then divide the exponent by 40
and get the remainder. 85 mod 41 = 5.
[Since 85/40 = 2 remainder 5]. We reduce
then the exponent to 5. 75 mod 41 = 16807
mod 41 = 38 .

 Use FLT to calculate
Solution:
 Use FLT to calculate

Solution:
https://www.youtube.com/watch?v=w0ZQvZLx2KA
https://www.youtube.com/watch?v=W6tKAAyTczw
https://www.youtube.com/watch?v=1h1RzWPTnME
https://www.youtube.com/watch?v=KPCkFLMHyr4
https://youtu.be/pMA-dD-KCWM
http://youtube.com/watch?v=HtyreGLePLU
John Alexander Wilson
(1741-1793)
Born in England
AGeologists and Mathematician
University of St. Andrews
Number Theory
If p is prime
then 1 + (p - 1)! is
divisible by p.
WILSON’S THEOREM
WILSON’S THEOREM
Wilson Prime
In Number Theory, a Wilson Prime is a
prime number such that
Divides ,It bears a striking
resemblance to Wilson's Theorem.
Although conjectured to be infinite in
number, no other Wilson primes have
been discovered besides 5, 13, and 563.
Case 1
In number theory, Wilson's Theorem states

that if integer p > 1 then (p-1)!+1
is divisible by P if and only if P is prime. It
was stated by John Wilson. The French
mathematician Lagrange proved it in 1771.
Proofs
Suppose first that is composite. Then has a
factor that is less than or equal to . Then
divides , so does not divide . Therefore
does not divide
Two proofs of the converse are provided: an
elementary one that rests close to basic principles
of modular arithmetic, and an elegant method that
relies on more powerful algebraic tools.

Elementary proof
Case 2
Example:
Find the remainder of 5! When divided by 7.
P = 7 (since 7 is a prime number we can use Wilson’s
Theorem)
Therefore, the remainder is 1 when 5! divided by 7.

2. Find the remainder of 9! When divided by 11.
p = 11 (prime number)
Therefore, the remainder is 1 when 9! divided

by 11.
P = 23 ( prime number)
Therefore, the remainder is 1 when 21! divided by

23.
P = 17 ( prime number)
 https://www.youtube.com/watch?v=abLT6QSGZ9c
 https://www.youtube.com/watch?v=VLFjOP7iFI0
 https://www.youtube.com/watch?v=IW0bco1a788
 https://www.youtube.com/watch?v=Rmtjry3HUMM

Fermat's Little Theorem and Wilson's Theorem

Uploaded by

Copyright:

Available Formats

Fermat's Little Theorem and Wilson's Theorem

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Fermat's Little Theorem and Wilson's Theorem

Uploaded by

Copyright:

Available Formats

Fermat’s Little

Analytic Geometry, Probability Theory,

For any integer n>2, the equation

FERMAT’S LAST THEOREM

A. Fermat's little theorem states that

Solution: We first note that the exponent k = 85.

785 MOD 41  71 4 16  64 MOD 41  (71  7 4  716  764 ) MOD 41

We next compute the needed powers of 7

7 4 MOD 41  (7 2 ) 2 MOD 41  (8) 2 MOD 41  64 MOD 41  23

78 MOD 41  (7 4 ) 2 MOD 41  (23) 2 MOD 41  529 MOD 41  37

716 MOD 41  (78 ) 2 MOD 41  (37) 2 MOD 41  1369 MOD 41  16

732 MOD 41  (716 ) 2 MOD 41  (16)2 MOD 41  256 MOD 41  10

764 MOD 41  (732 ) 2 MOD 41  (10) 2 MOD 41  100 MOD 41  18

Fermat’s Little Theorem: Let p be a prime

 Use FLT to calculate

In number theory, Wilson's Theorem states

Therefore, the remainder is 1 when 5! divided by 7.

Therefore, the remainder is 1 when 9! divided

Therefore, the remainder is 1 when 21! divided by

You might also like