← MATH 01352 · Theory of Numbers
MATH 01352 · Congruences
Euler totient / Fermat little theorem
Definition
φ(n) counts integers in 1..n−1 coprime to n. Euler: if gcd(a,n)=1 then a^{φ(n)}≡1 (mod n). Fermat: if p prime and p∤a then a^{p−1}≡1 (mod p) (since φ(p)=p−1).
Read this
Also aᵖ ≡ a (mod p) for prime p (freshman dream form).
φ is multiplicative on coprime factors; φ(pᵏ)=pᵏ−pᵏ⁻¹.
Use to reduce huge exponents mod n.
Drill with flashcards
Flip through these until you can say the answer before revealing it.
Flashcards · 1 / 3
Click the card to flip
Try this
Attempt each problem first, then open the worked solution.
1.Compute 2^{100} mod 17 using Fermat.