Notes - Fermat's Little Theorem and Euler's Theorem

The following are notes from Introduction to Cryptography with Coding Theory.

• Fermat's Little Theorem
• if p is a prime and p does not divide a, then
• a ^p-1≡ (1 mod p)
• Example
• 2¹⁰ = 1024 ≡ 1 (mod 11)
• can then evaluate 2⁵³ (mod 11)
• 2⁵³ = (2¹⁰)⁵2³ ≡ 1⁵2³  ≡ 8 (mod 11)
• We now require an analog for composite modulus n
• Define φ(n) as the number of integers a between 1 and n such that gcd(a,n) = 1
• Example
• φ(10) = 4 [1,3,7,9]
• Also can be deduced from chinese remainder theorem
• φ(n) = n Π_p|n (1-1/p)
• φ(p) = p - 1 where p is a prime number
• when n = pq where p and q are primes φ(pq) = (p - 1)(q - 1)
• Euler's Theorem
• If gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n)
• Example
• What are the last 3 digits of 7⁸⁰³
• same as working mod 1000
• 1000 = 2³5³
• φ(1000) = 1000(1-1/2)(1-1/5) = 400
• Example
• Compute 2⁴³²¹⁰  (mod 101)
• Note that 101 is prime, therefore 2¹⁰⁰  ≡ 1 (mod 101)
• Therefore (2¹⁰⁰)⁴³²2¹⁰ = 1⁴³²2¹⁰ ≡ 1024 (mod 101) ≡ 14

Back to ToC