Euler Theorem Application

Euler’s totient φ(n) counts residues coprime to n; Euler’s theorem: a^φ(n) ≡ 1 (mod n) when gcd(a,n)=1.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Compute φ via prime factorization: n * Π(1-1/p). Totient sieve builds φ for all i≤n. Powers use φ(p^k)=p^k-p^(k-1).

Try this in Python

def mod_pow(base: int, exp: int, mod: int) -> int:
    res = 1
    base %= mod
    while exp:
        if exp & 1:
            res = res * base % mod
        base = base * base % mod
        exp >>= 1
    return res


print(mod_pow(2, 1000000000, 1000000007))

Common mistakes

• Using Fermat with composite modulus.
• Wrong φ formula on repeated prime powers.
• Forgetting gcd condition on base a.

Key takeaways

• Build totient sieve when many φ queries.
• Reduce exponent mod φ(m) only when gcd(a,m)=1.