Euler Theorem
Euler's theorem generalizes Fermat's little theorem: if gcd(a,n)=1, then a^φ(n)≡1 (mod n), where φ is Euler's totient function.
Purpose
To extend modular-exponentiation simplification to arbitrary moduli; the basis of the RSA decryption correctness proof.
Mechanism
a^φ(n)≡1 (mod n) means a^e mod n can be simplified with e mod φ(n). RSA decryption: m^(ed)≡m^(ed mod φ(N))≡m^1≡m (mod N), because ed≡1 mod φ(N).
Use cases
- RSA correctness proof
- Modular exponentiation simplification
- Number theory