Transcript Document
Chapter 8
Introduction to Number Theory
Contents
Prime Numbers
Fermat’s and Euler’s Theorems
2
Prime Numbers
Primes numbers
An integer p > 1 is a prime number if and only if it is divisible by only 1
and p.
3
Prime Numbers
Integer factorization
Any integer a > 1 can be factored in a unique way as
a p1a1 p2a2 p3a3 ... ptat
where p1 < p2 < … < pt are prime numbers and
each ai is a positive integer.
91 = 7 × 13;
11101 = 7 × 112 ×13
4
Prime Numbers
Another integer factorization
If P is the set of all prime numbers, then any positive integer can be
written uniquely in the following form:
ap
ap
where each a p 0
pP
The right side is the product over all possible prime numbers p.
Most of the exponents ap will be 0.
3600 = 24×32×52×70×110×….
5
Prime Numbers
Another integer factorization
The value of any given positive integer can be specified by listing all
the nonzero exponents.
The integer 12 =22×31 is represented by {a2=2, a3=1}.
The integer 18 =21×32 is represented by {a2=1, a3=2}.
The integer 91= 72×131 is represented by {a7= 2, a13= 1}.
6
Prime Numbers
Multiplication
Multiplication of two numbers is adding the corresponding exponents.
k = 12 × 18 = 216
12 = 22 × 31
18 = 21 × 32
-----------------216 = 23 × 33
7
Prime Numbers
Divisibility
a|b
→
ap ≤ bp for all p
a = 12; b= 36; 12|36
12 = 22×3;
36 = 22×32
a2 = 2 = b2
a3 = 1 ≤ 2 = b3
8
Prime Numbers
GCD
k = gcd (a, b) → kp = min(ap, bp) for all p
300
18
= 22×31×52
= 21×32×50
gcd (18, 300) = 21×31×50 = 6
9
Fermat’s and Euler’s Theorems
Fermat’s theorem
If p is prime and a is a positive integer not divisible by p,
then
ap-1 ≡ 1 (mod p)
10
Fermat’s and Euler’s Theorems
Proof of Fermat’s theorem.
Outline
Show {1, 2, …, p-1}={a mod p, 2a mod p, …, (p-1)a mod p}
Show ( p 1)! ( p 1)!a
p 1
mod p .
Since ( p 1)! is relatively prime to p, we multiply ( p 1)!-1
to both sides to get 1 a p 1 mod p .
11
Fermat’s and Euler’s Theorems
Proof of Fermat’s theorem
Show {1, 2, …, p-1}={a mod p, 2a mod p, …, (p-1)a mod p}
Show ka mod p for any 1 ≤ k ≤ p-1 is in {1, 2, …, p-1}
by showing that ka mod p ≠ k’a mod p for k≠ k’.
Show ka mod p ≠ k’a mod p for 1 ≤ k≠ k’ ≤ p-1.
Proof by contradiction
Assume that ka ≡ k’a mod p for some 1 ≤ k≠ k’ ≤ p-1.
Since a is relatively prime to p, we multiply a-1 to get k ≡ k’ mod p,
which contradiction the fact that k≠ k’.
12
Fermat’s and Euler’s Theorems
Proof of Fermat’s theorem
Show ( p 1)! a p 1 ( p 1)! mod p.
{1, 2, …, p-1} = {a mod p, 2a mod p, …, (p-1)a mod p}
[1 2 ... ( p 1)] [( a mod p ) (2a mod p ) ... (( p 1)a mod p)] mod p
[1 2 ... ( p 1)] [a 2a ... ( p 1)a ] mod p
( p 1)! ( p 1)! a p 1 mod p
1 a p 1 mod p
13
Fermat’s and Euler’s Theorems
An alternative form of Fermat’s Theorem
ap ≡ a mod p
where p is prime and a is any positive integer.
Proof
If a and p are relatively prime, we get ap ≡ a mod p by
multiplying a to each side of ap-1 ≡ 1 mod p.
If a and p are not relatively prime, a = cp for some positive
integer c. So ap ≡ (cp)p ≡ 0 mod p and a ≡ 0 mod p, which
means ap ≡ a mod p.
14
Fermat’s and Euler’s Theorems
An alternative form of Fermat’s Theorem
ap ≡ a mod p
where p is prime and a is any positive integer.
p = 5, a = 3
35 = 243 ≡ 3 mod 5
p = 5, a = 10
105 = 100000 ≡ 10 mod 5 ≡ 0 mod 5
15
Fermat’s and Euler’s Theorems
Euler’s Totient Function (n)
The number of positive integers less than n and relatively prime to n.
(37) = 36
37 is prime, so all the positive number from 1 to 36
are relatively prime to 37.
(35) = 24
35 = 5×7
1, 2, 3, 4, 6, 8, 9,11, 12, 13, 16, 17, 18, 19, 22,
23, 24, 26, 27, 29, 31, 32, 33, 34
16
Fermat’s and Euler’s Theorems
How to compute (n)
In general,
1
(n) n (1 ), where p runs over all the primes dividing n
p
For a prime n, (Zn = {1,2,…, n-1})
( n) n 1
For n = pq, p and q are prime numbers and p≠ q
(n) ( p 1) (q 1)
17
Fermat’s and Euler’s Theorems
Proof of (n) ( p 1) (q 1)
(n) is the number of positive integers less than pq that are relatively
prime to pq.
(n) can be computed by subtract from pq – 1 the number of positive
integers in {1, …, pq – 1} that are not relatively prime to pq.
The positive integers that are not relatively prime to pq are a multiple of
either p or q.
{ p, 2p,…,(q – 1)p}, {q, 2q, …,(p – 1)q}
There is no same elements in the two sets.
So, there are p + q – 2 elements that are not relatively prime to pq.
Hence,
(n) = pq – 1– (p + q – 2)
= pq – p – q +1
= (p – 1)(q – 1)
18
Fermat’s and Euler’s Theorems
Φ(21) = Φ(3)×Φ(7) = (3-1)×(7-1) = 2 ×6 = 12
Z21={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Φ(3)={3,6,9,12,15,18}
Φ(7)={7,14}
where the 12 integers are {1,2,4,5,8,10,11,13,16,17,19,20}
19
Fermat’s and Euler’s Theorems
Euler’s theorem
For every a and n that are relatively prime:
a ( n ) 1 mod n
a = 3;
a = 2;
n = 10;
n = 11;
Φ(10) = 4;
Φ(11) = 10;
34 = 81 ≡ 1 mod 10
210 = 1024 ≡ 1 mod 11
20
Fermat’s and Euler’s Theorems
Proof of Euler’s theorem
a ( n ) 1 mod n
If n is prime, it holds due to Fermat’s theorem.
a n 1 1 mod n
Otherwise (If n is not prime),
define two sets R and S.
show the sets R and S are the same.
then, show a ( n ) 1 mod n
21
Fermat’s and Euler’s Theorems
Proof of Euler’s theorem
Set R
The elements are positive integers less than n and relatively prime to n.
The number of elements is (n)
R={x1, x2,…, xΦ(n)} where x1< x2<…< xΦ(n)
Set S
Multiplying each element of R by a∈R modulo n
S ={(ax1 mod n), (ax2 mod n),…(axΦ(n) mod n)}.
22
Fermat’s and Euler’s Theorems
Proof of Euler’s theorem
The sets R and S are the same.
We show S has all integers less than n and relatively prime to n.
S ={(ax1 mod n), (ax2 mod n),…(axΦ(n) mod n)}
1.
2.
All the elements of S are integers less than n that are relatively prime
to n because a is relatively prime to n and xi is relatively prime to n,
axi must also be relatively prime to n.
There are no duplicates in S.
If axi mod n = axj mod n, then xi = xj. by cancellation law.
23
Fermat’s and Euler’s Theorems
Proof of Euler’s theorem
Since R and S are the same sets,
(n)
(n)
(ax mod n) x
i
i
i 1
i 1
(n)
(n)
ax x (mod n)
i
i 1
i
i 1
(n)
(n)
a ( n ) xi xi (mod n)
i 1 i 1
a ( n ) 1(mod n)
24
Fermat’s and Euler’s Theorems
Alternative form of the theorem
a ( n )1 a(mod n)
If a and n are relatively prime, it is true due to Euler’s
theorem.
Otherwise, ….
25
Fermat’s and Euler’s Theorem
The validity of RSA algorithm
Given 2 prime numbers p and q, and integers n = pq and m,
with 0<m<n, the following relationship holds.
m ( n ) 1 m ( p 1)( q 1) 1 m mod n
If m and n are re relatively prime, it holds by Euler’s theorem.
If m and n are not relatively prime, m is a multiple of either p or q.
26
Fermat’s and Euler’s Theorem
Case 1: m is a multiple of p
m=cp for some positive integer c.
gcd(m, q)=1, otherwise, m is a multiple of p and q and yet m<pq
because gcd(m, q)=1, Euler’s theorem holds
mq 1 1 mod q
by the rules of modular arithmetic,
[m q 1 ] p 1 1 mod q
m ( n ) 1 mod q
m ( n ) 1 kq,
for some integer k
Multiplying each side by m=cp
m ( n )1 m kcpq m kcn
m ( n )1 m mod n
27
Fermat’s and Euler’s Theorem
Case 2: m is a multiple of q
prove similarly.
Thus, the following equation is proved.
m ( n ) 1 m ( p 1)( q 1) 1 m mod n
28
Fermat’s and Euler’s Theorem
An alternative form of this corollary is directly
relevant to RSA.
m k ( n ) 1
[( m ( n ) k m1 ] mod n
[(1) k m] mod n,
m mod n
by Euler' s theorem
29