Euler's theorem shrinks a huge exponent: when computing g^k mod n, what licenses replacing k with k mod phi(n)?
answer
- powers of a coprime base cycle
- one full cycle multiplies by one
- exponent matters only up to the cycle length
- cycle length divides phi(n)
- condition sits on the base, not the modulus
basics
~20 sEuler's theorem gives g^phi(n) congruent to 1 mod n whenever gcd(g, n) = 1, so the powers of g cycle with a period dividing phi(n) and only k mod phi(n) matters. Without that coprimality the reduction is simply invalid.
solid answer
~40 sEuler's theorem says that if `gcd(g, n) = 1` then `g^phi(n)` is congruent to `1` modulo `n`. Multiplying by 1 changes nothing, so every whole block of `phi(n)` in the exponent can be discarded: `g^k` is congruent to `g^(k mod phi(n))`. That turns an exponent with millions of digits into one below `phi(n)`, after which ordinary repeated squaring finishes the job. The **condition is coprimality of the base with the modulus, not primality of the modulus**. With `gcd(g, n) > 1` the powers never return to 1 - the powers of 2 modulo 10 run 2, 4, 8, 6 forever - and reducing the exponent gives a wrong answer. Note also that `phi(n)` is *a* period, not necessarily the smallest.
code
pseudocode · 13 linesfunction power_mod(g, k, n): // k may be astronomically large
if gcd(g, n) = 1:
e = k mod phi(n) // Euler's theorem licenses this
else:
e = k // no reduction: g^phi(n) need not be 1
result = 1
base = g mod n
while e > 0:
if e is odd:
result = (result * base) mod n
base = (base * base) mod n
e = e div 2
return resultgo deeper
Know the headline: powers of a base repeat modulo a fixed number, so an enormous exponent can be cut down to a small one. Which number to cut it by, and when that is allowed, is the part to learn next.
Explain the mechanics: one full cycle multiplies by 1, so only the remainder of the exponent survives, and the cycle length divides phi(n). State the coprimality condition and be able to produce a base where it fails.
Show the failure concretely - the powers of 2 modulo 10 never reach 1 - and separate phi(n) from the actual order. Note that getting phi(n) at all needs the modulus's factorization, which bounds where the trick is usable.
Treat it as a design constraint, not a speed-up: if a rotation's step is not coprime to its modulus the schedule visits only part of the space, which is a coverage bug. Choose the step and the modulus together.
## The theorem, stated precisely **Euler's theorem:** if `gcd(g, n) = 1`, then `g^phi(n)` is congruent to `1` modulo `n`, where `phi(n)` is the count of integers in `1..n` coprime to `n`. The reason is structural rather than computational. The residues coprime to `n` are exactly the invertible ones, there are `phi(n)` of them, and multiplying every one of them by `g` permutes that set - `g` is invertible, so the map is reversible and cannot collapse two residues together. Multiplying all the elements together before and after the permutation gives the same product, and cancelling it (legal, because the product is invertible) leaves `g^phi(n)` congruent to 1. ## Why the exponent collapses Write `k = q * phi(n) + r` with `r = k mod phi(n)`. Then `g^k = (g^phi(n))^q * g^r`, which is congruent to `1^q * g^r = g^r` modulo `n`. So only the remainder of the exponent survives. Concretely, with `n = 10` we have `phi(10) = 4` (the residues 1, 3, 7, 9) and the powers of 3 repeat with period 4: | k | 1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---|---| | 3^k mod 10 | 3 | 9 | 7 | 1 | 3 | 9 | | 2^k mod 10 | 2 | 4 | 8 | 6 | 2 | 4 | For `3^2026 mod 10`: `2026 mod 4 = 2`, so the answer is `3^2 = 9`. The exponent's size never mattered. ## The condition, and exactly what breaks without it Read the second row of that table again. The powers of 2 modulo 10 cycle through 2, 4, 8, 6 and **never reach 1** - they cannot, because `gcd(2, 10) = 2` forces every power to stay even. Euler's theorem makes no claim here, and the reduction is not merely weaker, it is wrong: - true value: `2^2028 mod 10`. The cycle `2, 4, 8, 6` starts at exponent 1, so exponent `2028` lands at position `(2028 - 1) mod 4 = 3`, the fourth entry, giving **6**. - naive reduction: `2028 mod 4 = 0`, so `2^0 = 1`. Wrong. The general picture for `gcd(g, n) > 1` is that the sequence of powers is only *eventually* periodic - it has a lead-in that never recurs - so there is no exponent modulus that can be applied uniformly from `k = 1`. Two further precision points that interviewers probe: 1. The condition is on the **base**, not the modulus. `n` composite is fine; `n` prime is fine; what matters is `gcd(g, n) = 1`. 2. `phi(n)` is **a** period, not necessarily the smallest one. The multiplicative order of `g` - the least `t > 0` with `g^t` congruent to 1 - always divides `phi(n)` but can be far smaller. Modulo 8, `phi(8) = 4`, yet `3^2 = 9` is congruent to 1, so 3 has order 2. Reducing modulo `phi(n)` is always safe under coprimality; reducing modulo the order is safe too and sometimes cheaper, but it is a per-base fact, not a per-modulus one. ## Using it 1. Check `gcd(g, n) = 1`. If it fails, stop - no exponent reduction of this form applies. 2. Compute `phi(n)` from the factorization of `n` (prime-power rule, multiplied across coprime factors). 3. Replace `k` by `k mod phi(n)`. 4. Evaluate the small power by repeated squaring, reducing modulo `n` at every step. Step 2 is the practical limit: you need the factorization of `n` to get `phi(n)`, so this trick is available exactly when you know how `n` was built. ## Where the reduction earns its keep Any scheme where a position advances multiplicatively - a rotation offset applied once per interval, a running fingerprint that multiplies in a factor per element, a placement slot advanced by a fixed step - accumulates an exponent that grows without bound while the state it describes has only `phi(n)` distinct settings. The theorem is what lets you jump straight to the state after a billion intervals without walking them, and equally what tells you the schedule is periodic at all. The converse reading matters as much in a design review: if the base is *not* coprime to the modulus, that rotation does not visit all the positions you assumed, and the set it does visit shrinks. That is a correctness statement about the scheme, not an optimisation detail.
- If k mod phi(n) comes out as 0, is the answer 1 or g^phi(n)?Both, and they agree. Under `gcd(g, n) = 1`, `g^phi(n)` is congruent to 1, so any exponent that is a whole multiple of `phi(n)` gives 1 modulo `n`. The zero remainder is not a special case to guard - it is the theorem's own statement, and `g^0 = 1` computes it correctly.
- The powers of g modulo n returned to 1 after fewer than phi(n) steps. Is Euler's theorem violated?No. Euler's theorem says `phi(n)` is *a* period, not the least one. The multiplicative order of `g` always divides `phi(n)`, so a shorter cycle whose length divides `phi(n)` is exactly what the theorem predicts. Modulo 8, `phi(8) = 4` while 3 has order 2.
- Why does the reduction need phi(n) rather than n?Because the repetition lives in the exponent, and the exponents index the invertible residues, of which there are `phi(n)`. Reducing the exponent modulo `n` has no theorem behind it and is generally wrong: modulo 10 the powers of 3 repeat every 4 steps, not every 10, so discarding blocks of 10 lands on the wrong entry.
saying these in an interview costs you the question
- Reduces the exponent modulo n instead of modulo phi(n)
- Believes the theorem requires the modulus to be prime
- Applies the reduction without checking gcd of base and modulus
- Claims phi(n) is always the smallest period of the powers
- Thinks a base sharing a factor still eventually reaches 1