The document discusses several number theory theorems:
[1] Fermat's theorem states that if p is prime and a is any positive integer not divisible by p, then a^p-1 ≡ 1 (mod p).
[2] Wilson's theorem states that if p is prime, then (p-1)! ≡ -1 (mod p).
[3] Euler's theorem, an extension of Fermat's theorem, states that if n is a positive integer and a and n are relatively prime, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.
The document discusses several number theory theorems:
[1] Fermat's theorem states that if p is prime and a is any positive integer not divisible by p, then a^p-1 ≡ 1 (mod p).
[2] Wilson's theorem states that if p is prime, then (p-1)! ≡ -1 (mod p).
[3] Euler's theorem, an extension of Fermat's theorem, states that if n is a positive integer and a and n are relatively prime, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.
The document discusses several number theory theorems:
[1] Fermat's theorem states that if p is prime and a is any positive integer not divisible by p, then a^p-1 ≡ 1 (mod p).
[2] Wilson's theorem states that if p is prime, then (p-1)! ≡ -1 (mod p).
[3] Euler's theorem, an extension of Fermat's theorem, states that if n is a positive integer and a and n are relatively prime, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.
The document discusses several number theory theorems:
[1] Fermat's theorem states that if p is prime and a is any positive integer not divisible by p, then a^p-1 ≡ 1 (mod p).
[2] Wilson's theorem states that if p is prime, then (p-1)! ≡ -1 (mod p).
[3] Euler's theorem, an extension of Fermat's theorem, states that if n is a positive integer and a and n are relatively prime, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.
• 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
