Modular Exponentiation and the Euler-Fermat Theorem

Euler's theorem and fast modular exponentiation together form the computational core of modern public-key cryptography. In the RSA Cryptosystem, a modulus $n = pq$ is chosen as a product of two large primes, and encryption/decryption exponents $e, d$ are chosen so that $ed \equiv 1 \pmod{\phi(n)}$; correctness of decryption is a direct application of Euler's theorem (with some extra care for messages not coprime to $n$, handled via the Chinese Remainder Theorem). Without fast modular exponentiation, computing $c^d \bmod n$ for a 2048-bit exponent $d$ would be entirely infeasible; repeated squaring makes it routine, requiring only a few thousand modular multiplications rather than an astronomically large number. Beyond RSA, the same machinery underlies the Diffie–Hellman key exchange, Rabin cryptosystem, and various digital signature schemes, all of which perform exponentiation in a finite group of known or partially known order. In primality testing, Fermat's Little Theorem (the prime-modulus special case) is the seed idea behind the Fermat primality test and its refinements (Miller–Rabin), which rely on fast modular exponentiation to test candidate primes with hundreds of digits in milliseconds. In computer algebra and coding theory, modular exponentiation appears in polynomial evaluation over finite fields, and the order-divides-group-order corollary generalizes to the structure theory of finite fields and cyclic groups used in error-correcting codes. Even outside cryptography, Euler's theorem is a standard tool in competition mathematics and in analytic number theory for controlling the multiplicative order of residues, feeding into deeper results about the distribution of primes and the structure of $(\mathbb{Z}/n\mathbb{Z})^\times$.

Ask the tutor: How does Euler's theorem, combined with the Chinese Remainder Theorem, guarantee that RSA decryption recovers the original message even when the message shares a factor with the modulus?

Think of the coprime residues modulo $n$ as points arranged in a cycle, and think of multiplication by $a$ as a shuffle of these points. Because $a$ is invertible modulo $n$ (this is exactly what $\gcd(a,n)=1$ buys us), the shuffle is a bijection: no two points collide, and no point is left out. A finite set shuffled bijectively by repeatedly applying the same rule must eventually return every point to its original position — you cannot shuffle a finite deck forever without repeating a configuration. Euler's theorem pins down exactly how many shuffles it takes in the worst case: $\phi(n)$ applications of "multiply by $a$" always return every coprime residue to itself, though the true minimal period (the order of $a$) may be a proper divisor of $\phi(n)$. A second way to see it: the coprime residues modulo $n$ form a group under multiplication, of size $\phi(n)$. The powers of $a$ trace out a subgroup — a smaller cycle sitting inside the big cycle. Lagrange's theorem, a purely group-theoretic fact, says the size of any subgroup divides the size of the whole group. Since the size of the subgroup generated by $a$ is precisely the order of $a$, this order must divide $\phi(n)$, and raising $a$ to the $\phi(n)$-th power is just going around the big cycle a whole number of times, landing back at the identity element $1$.

Euler's theorem tells us $a^{\phi(n)} \equiv 1 \pmod n$, but in applications (and especially in cryptography) we need to compute $a^k \bmod n$ for specific, often astronomically large, exponents $k$ — we cannot simply reduce $k$ modulo $\phi(n)$ unless we already know $\phi(n)$, and even then we must still exponentiate efficiently. The naive approach of multiplying $a$ by itself $k-1$ times is computationally infeasible once $k$ has, say, hundreds of digits. The algorithm of repeated squaring (also called binary exponentiation, or exponentiation by squaring) solves this by exploiting the binary representation of $k$.

Example 1 (using Euler's theorem to reduce a large exponent, non-prime modulus). Compute $7^{1000} \bmod 24$. First, $\gcd(7, 24) = 1$ since $24 = 2^3 \cdot 3$ and $7$ is divisible by neither $2$ nor $3$. Compute $\phi(24)$: using the standard product formula (a consequence of the multiplicativity of $\phi$, itself provable from the definition, though we take it as known here per the prerequisites) $\phi(24) = 24\left(1 - \tfrac12\right)\left(1 - \tfrac13\right) = 24 \cdot \tfrac12 \cdot \tfrac23 = 8$. By Euler's theorem, $7^8 \equiv 1 \pmod{24}$. Now reduce the exponent: write $1000 = 8 \cdot 125 + 0$, so $1000 = 8\cdot 125$ exactly, with remainder $r=0$. Then

Let's double check independently by directly computing small powers of $7$ mod $24$: $7^1 = 7$, $7^2 = 49 \equiv 1 \pmod{24}$ (since $49 = 2\cdot 24 + 1$). So actually the true order of $7$ modulo $24$ is $2$, a proper divisor of $\phi(24) = 8$, consistent with the Corollary above ($\mathrm{ord}_{24}(7) \mid \phi(24)$, and indeed $2 \mid 8$). Since $1000$ is even, $7^{1000} = (7^2)^{500} \equiv 1^{500} = 1 \pmod{24}$, confirming the answer $7^{1000} \equiv 1 \pmod{24}$. This illustrates an important subtlety: Euler's theorem always gives a valid exponent ($\phi(n)$) that works, but the true period (the order) can be much smaller, and knowing the order lets us reduce even faster — though Euler's theorem alone, without knowing the order, already suffices to get the correct final answer via the division $1000 = 8\cdot 125$.

Example 2 (fast modular exponentiation by hand, asymmetric numbers). Compute $a^k \bmod n = 5^{117} \bmod 91$ using repeated squaring, and cross-check with Euler's theorem. First, $91 = 7 \times 13$, so $\phi(91) = \phi(7)\phi(13) = 6 \times 12 = 72$ (using multiplicativity of $\phi$ on the coprime factors $7, 13$). Since $\gcd(5, 91) = 1$ (as $5$ shares no factor with $7$ or $13$), Euler's theorem gives $5^{72} \equiv 1 \pmod{91}$. Binary expansion of the exponent. $117 = 64 + 32 + 16 + 4 + 1 = 2^6 + 2^5 + 2^4 + 2^2 + 2^0$. Check: $64+32+16+4+1 = 117$. ✓. So in binary, $117 = 1110101_2$, i.e. bits $b_0=1, b_1=0, b_2=1, b_3=0, b_4=1,b_5=1,b_6=1$. Building the squaring tower $S_i \equiv 5^{2^i} \pmod {91}$: $S_0 = 5 \bmod 91 = 5$. $S_1 = S_0^2 \bmod 91 = 25 \bmod 91 = 25$. $S_2 = S_1^2 \bmod 91 = 625 \bmod 91$. Since $91 \times 6 = 546$ and $625 - 546 = 79$, $S_2 = 79$. $S_3 = S_2^2 \bmod 91 = 79^2 \bmod 91 = 6241 \bmod 91$. Since $91 \times 68 = 6188$, $6241 - 6188 = 53$, so $S_3 = 53$. $S_4 = S_3^2 \bmod 91 = 53^2 \bmod 91 = 2809 \bmod 91$. Since $91 \times 30 = 2730$, $2809 - 2730 = 79$, so $S_4 = 79$. (Sanity check on the cycle: $S_2 = 79$ and $S_4 = 79$ — this recurrence is plausible since $5$ has some order dividing $72$, and squaring is periodic; we don't need this observation for the computation, we just continue mechanically.) $S_5 = S_4^2 \bmod 91 = 79^2 \bmod 91 = 6241 \bmod 91 = 53$ (identical computation to $S_3$, since $S_4 = S_2 = 79$). $S_6 = S_5^2 \bmod 91 = 53^2 \bmod 91 = 2809 \bmod 91 = 79$ (identical computation to $S_4$). So the tower is:

Assembling the answer. We need $\prod_{i : b_i=1} S_i$ for $i \in \{0,2,4,5,6\}$ (bits equal to $1$ at positions $0,2,4,5,6$, matching $2^0+2^2+2^4+2^5+2^6 = 1+4+16+32+64=117$ ✓). So

Compute step by step, reducing modulo $91$ after each multiplication: $5 \times 79 = 395$. $395 \bmod 91$: $91 \times 4 = 364$, $395 - 364 = 31$. Running product: $31$. $31 \times 79 = 2449$. $2449 \bmod 91$: $91 \times 26 = 2366$, $2449 - 2366 = 83$. Running product: $83$. $83 \times 53 = 4399$. $4399 \bmod 91$: $91 \times 48 = 4368$, $4399 - 4368 = 31$. Running product: $31$. $31 \times 79 = 2449 \equiv 83 \pmod{91}$ (computed above). Running product: $83$. So $5^{117} \equiv 83 \pmod{91}$. Cross-check via Euler's theorem. We know $5^{72} \equiv 1 \pmod {91}$. Write $117 = 72 + 45$, so $5^{117} = 5^{72} \cdot 5^{45} \equiv 5^{45} \pmod{91}$. We can verify $5^{45} \equiv 83$ independently: note $45 = 32+8+4+1 = 2^5+2^3+2^2+2^0$, using bits at $0,2,3,5$. We already have $S_0=5, S_2=79, S_5=53$; we need $S_3 = 53$ (already computed above). So

$5\times 79 = 395 \equiv 31$ (as before). $31 \times 53 = 1643$; $91\times 18 = 1638$, remainder $5$. Running product: $5$. $5 \times 53 = 265$; $91 \times 2 = 182$, $265-182=83$. Running product: $83$. Both routes give $5^{117} \equiv 83 \pmod{91}$, confirming the computation and simultaneously illustrating how Euler's theorem can be combined with repeated squaring to shrink the exponent before squaring, cutting the work further.