CS2050 L18 Fermat's Little Theorem, Euler's theorem
Overview
The lecture derives Euler’s totient formulas and proves Fermat’s Little Theorem by showing that multiplication by a nonzero residue permutes the nonzero classes modulo a prime. Extending the same proof to units modulo any n yields Euler’s theorem, which reduces modular exponents; examples apply it to 7^821 mod 15 and a four-level power tower whose last two digits are 87.
Key takeaways
- For n=∏p^a, the totient is φ(n)=∏p^(a−1)(p−1), or equivalently n times the product of (1−1/p) over distinct prime divisors p of n.
- Fermat’s Little Theorem follows because multiplication by a nonzero residue permutes 1 through p−1 modulo prime p; equating the products and cancelling (p−1)! gives a^(p−1)≡1 mod p.
- Euler’s theorem replaces the prime condition with gcd(a,n)=1 and gives a^φ(n)≡1 mod n, since multiplication by a permutes the φ(n) invertible residues.
- If gcd(a,n)=1, an exponent k can be reduced modulo φ(n): writing k=qφ(n)+r gives a^k≡a^r mod n.
- Nested modular powers may require repeated totient reductions: the calculation of 3^(3^(3^3)) mod 100 reduces through moduli 100, 40, and 16 before the Chinese remainder theorem gives 87.
Chapters
- The totient φ(n) counts integers a from 1 through n with gcd(a,n)=1.
- For a prime p, φ(p)=p−1 because every integer from 1 through p−1 is coprime to p.
- The Chinese remainder theorem explains why φ(mn)=φ(m)φ(n) when gcd(m,n)=1.
- For distinct primes p and q, the integers not coprime to pq are multiples of p or q.
- Among 1 through pq, there are q multiples of p and p multiples of q, with pq counted in both groups.
- Inclusion-exclusion gives φ(pq)=pq−q−p+1=(p−1)(q−1).
- Among 1 through p^a, exactly p^(a−1) numbers are multiples of p and are not coprime to p^a.
- Subtracting those multiples from p^a gives φ(p^a)=p^a−p^(a−1)=p^(a−1)(p−1).
- For example, the count relies on p being the only prime divisor of p^a.
- Write n as a product of prime powers, n=∏p_i^a_i, using only primes that divide n.
- Multiplicativity across coprime prime powers gives φ(n)=∏p_i^(a_i−1)(p_i−1).
- An equivalent form is φ(n)=n∏_{p|n}(1−1/p), where the product ranges over the distinct prime divisors of n.
- In this number-theory setting, a^n means multiplying a by itself n times, so exponents are nonnegative integers.
- The identity a^0=1 follows because zero multiplications leave the multiplicative identity.
- For an invertible residue, the inverse of a^n equals (a^−1)^n, since taking n inverses commutes with taking the power.
- Fermat’s Little Theorem states that a^(p−1)≡1 mod p when p is prime and 1≤a<p.
- Modulo p there are only p residue classes, so powers cannot keep producing new residues indefinitely.
- The proof will use the nonzero classes 1 through p−1, all of which have multiplicative inverses modulo p.
- For fixed nonzero a modulo prime p, multiplying each element of {1,…,p−1} by a modulo p produces a permutation of the nonzero residues.
- Injectivity follows by cancelling a using its inverse modulo p; surjectivity follows by multiplying a target residue by a^−1.
- The image cannot contain 0, since a·i≡0 mod p would imply i≡0, which is outside the domain.
- Because multiplication by a permutes {1,…,p−1}, the product of the residues equals the product of their multiples by a modulo p.
- Factoring out the p−1 copies of a yields (p−1)!≡a^(p−1)(p−1)! mod p.
- The factorial is invertible modulo p because none of its factors is divisible by p, so cancellation proves a^(p−1)≡1 mod p.
- For any n≥2, use the residues coprime to n as the domain; their count is φ(n).
- If gcd(a,n)=1, multiplication by a permutes those units modulo n because a has an inverse.
- Taking products of the permuted units and cancelling their invertible product proves a^φ(n)≡1 mod n.
- When gcd(a,n)=1, write k=qφ(n)+r; Euler’s theorem gives a^k≡a^r mod n.
- Thus modular powers can be simplified by reducing the exponent modulo φ(n), often avoiding enormous calculations.
- Fermat’s Little Theorem is the prime-modulus case because φ(p)=p−1.
- The totient is φ(15)=φ(3)φ(5)=2·4=8, and gcd(7,15)=1.
- Reduce 821 modulo 8 to get exponent 5, so 7^821≡7^5 mod 15.
- Since 7^2≡4 and 7^4≡1 mod 15, the result is 7^5≡7 mod 15.
- Finding the last two digits of 3^(3^(3^3)) means computing modulo 100; φ(100)=40 reduces the outer exponent to 3^27 mod 40.
- Using φ(40)=16 reduces 3^27 mod 40 to 3^11, which is 27; therefore the original expression is congruent to 3^27 mod 100.
- Split modulus 100 into coprime moduli 4 and 25: 3^27≡3 mod 4 and 3^27≡12 mod 25.
- The Chinese remainder theorem combines those congruences to give 87 mod 100, so the last two digits are 87.
Transcript excerpt
0:02 Okay. Uh this is CS 2050. Uh the topic of today are the theorems of Fermat and Euler. So Fermat's little theorem. And then we'll talk about Euler's theorem. Fermat's little theorem, Euler's theorem. I mean so what's this guy's name? It's technically pronounced Euler, but it's spelled Euler. So I mean you forgive you'd be forgiven if you called him Euler, but uh let's see where we were. Last time we talked about the Euler phi function, the totient. And the And this is said to be the cardinality
0:49 of the set of elements that are relatively prime to n. Uh so most formally this is the set How many elements are there a between one and n uh such that uh the GCD of a and n is one, right? And we gave some examples of how to compute this, but very importantly we proved uh a very important property. Uh if the GCD of m and n is one, then phi is multiplicative over m and n, right? [snorts] It only acts kind of like a homomorphism some of the time. Uh you remember how we proved this? We
1:38 showed that the Chinese remainder theorem showed a bijection between uh this group and the Cartesian products of these groups, right? And therefore they must have the same cardinality. Today we're going to try to finish giving a formula for uh the Euler phi and then we'll get to the theorems of Fermat and Euler. So first thing to note, if p is prime, what should of p be? By the way, this is only defined for n greater than or equal to two, let say. Right. If p is prime, what should phi of p be? Yeah, all elements less than p, strictly so, are relatively prime to p. Between
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.