skip to content

Modulo a prime p, why does raising a to the power p-2 act as its inverse, and when does that route fail?

level: seniorimportance: nice to knowfreq 34%

answer

  1. one exponentiation instead of a loop
  2. peel one factor off the exponent
  3. a^(p-1) = 1 for prime p
  4. so a^(p-2) is the inverse
  5. primality and a not divisible by p

basics

~20 s

Fermat's little theorem says a^(p-1) = 1 (mod p) for a prime p and any a not divisible by p. Multiplying that by the inverse of a leaves a^(p-2) as the inverse. It fails for a composite modulus and for a divisible by p.

solid answer

~50 s

**Fermat's little theorem**: for a prime `p` and any `a` not divisible by `p`, `a^(p-1) = 1 (mod p)`. Split off one factor and that reads `a * a^(p-2) = 1 (mod p)`, which is precisely the definition of `a^(p-2)` being the inverse of `a`. Two preconditions carry the whole argument. The modulus must be **prime** - with a composite modulus the exponent `n-2` means nothing, and computing it gives a wrong value rather than an error. And `a` must not be a multiple of `p`, which is the same coprimality condition as always, since the only residue sharing a factor with a prime is 0. The practical appeal is shape, not speed: it is one exponentiation with a fixed exponent and no data-dependent branching, whereas the extended Euclidean route is a loop whose trip count depends on the inputs. The extended route, though, works against **any** modulus and reports honestly when no inverse exists.

go deeper

for a junior

Know the shape: modulo a prime p, raising a value to the power p-2 gives its inverse, and this depends on the modulus really being prime.

for a middle

Derive it rather than memorise it: a^(p-1) = 1 modulo a prime, so peeling off one factor of a leaves a^(p-2) as exactly the inverse.

for a senior

The operational point is the silent failure: with a composite modulus the computation still returns a residue, just a wrong one, so the primality precondition has to be asserted rather than assumed.

for a principal

Treat it as a fit decision - a fixed prime modulus and uniform control flow argue for the exponent route, while a modulus that can vary argues for the route that can answer 'there is no inverse'.

## The identity and the one-line derivation **Fermat's little theorem**: if `p` is prime and `a` is not divisible by `p`, then `a^(p-1) = 1 (mod p)` Rewrite the left side as `a * a^(p-2)`. The equation becomes `a * a^(p-2) = 1 (mod p)`, and that is the definition of an inverse. So **`a^(p-2) mod p` is the inverse of `a` modulo `p`** - no gcd loop, no coefficient bookkeeping, just one exponentiation. Sanity check with small numbers: modulo 7, take `a = 3`. Then `3^5 = 243 = 238 + 5`, and `238 = 34 * 7`, so `3^5 = 5 (mod 7)`. And indeed `3 * 5 = 15 = 1 (mod 7)`, matching what the extended Euclidean route returns for the same pair. ## The two preconditions Both are easy to state and both are load-bearing: - **The modulus must be prime.** The exponent `p-2` is not a general recipe; it is derived from the theorem, and the theorem assumes primality. For a composite modulus the correct exponent is a different quantity entirely, belonging to a different result. - **`a` must not be a multiple of `p`.** Modulo a prime, the only residue that fails coprimality is 0, so this is the familiar condition in its simplest form: 0 has no inverse, and `0^(p-2)` is 0, not an inverse of anything. The failure mode of the first precondition deserves emphasis because it is **silent**. Try it with `n = 15`, which is composite, and `a = 2`: `2^13 = 8192`, and `8192 = 546*15 + 2`, so `2^13 = 2 (mod 15)`. That is not the inverse - the true inverse of 2 modulo 15 is 8, since `2*8 = 16 = 1 (mod 15)`. The computation ran to completion, produced a residue, and the residue was wrong. Nothing in the arithmetic signals the mistake; only the primality assumption did, and it was not checked. ## Choosing between the two routes | | exponentiation route | extended Euclidean route | |---|---|---| | works for | prime modulus only | any modulus | | detects "no inverse" | no - returns a wrong residue | yes - the gcd is not 1 | | shape of the computation | one exponentiation, fixed exponent | a loop whose length depends on inputs | | control flow | uniform, no data-dependent branches | data-dependent trip count | | extra state | none beyond the running power | one coefficient column | Both cost a number of multiplications proportional to the number of digits in the modulus, so the choice is rarely about raw speed. It is about **fit**: a fixed modulus known to be prime, code that wants uniform control flow, and an exponent that can be baked in favour the first; a modulus that varies, may be composite, or arrives from configuration favours the second, because it answers "is there an inverse?" instead of assuming one. ## Inverting many values at once When a batch of residues must be inverted against the same prime modulus, neither route needs to run once per value. The standard trick is a prefix-product walk: 1. Build the running products `p_1 = a_1`, `p_2 = a_1*a_2`, ... up to `p_k`, the product of all of them. 2. Invert `p_k` **once**, by either route. 3. Walk backwards: the inverse of `a_i` is `inv(p_i) * p_(i-1)`, and `inv(p_(i-1)) = inv(p_i) * a_i`. That turns `k` inversions into one inversion plus a few multiplications per element, which is why a fingerprinting or verification pass that needs many inverses does not pay the inversion cost `k` times. ## Where this shows up and what to watch - **A modulus that is documented as prime but never asserted.** The theorem's precondition is an assumption about data, so it belongs in a check or a constant, not in a comment. - **A zero coefficient sliding through.** `a = 0` has no inverse; the exponentiation route quietly returns 0 for it. - **Copying the exponent to a new modulus.** The exponent is tied to the specific prime; reusing `p-2` after the modulus changes is the most common way this breaks in a code base. - **Assuming it is the fast option.** It is the *uniform* option. If speed is the goal, measure - the extended Euclidean loop is frequently the cheaper of the two.

  • Thousands of residues need inverting against the same prime - must you invert each one?
    No. Build prefix products of the batch, invert the single total product once, then walk backwards: the inverse of each element falls out as the running inverse times the previous prefix, and the running inverse updates by multiplying in the element just consumed. The cost is one inversion plus a small constant number of multiplications per element.
  • Does the same exponent trick work when the modulus is composite?
    No, and it fails silently. Modulo 15 with a = 2, the value 2^13 reduces to 2, while the true inverse of 2 modulo 15 is 8. The computation returns a residue rather than an error, so the wrong value propagates. For a composite modulus the extended Euclidean route is the correct general tool.
  • Why might a team prefer the exponentiation route even though it is narrower?
    Its control flow does not depend on the value being inverted: the same fixed sequence of squarings and multiplications runs every time, whereas the Euclidean loop's trip count varies with the inputs. Where uniform, input-independent execution is a requirement, that shape is worth more than the narrower applicability costs.

saying these in an interview costs you the question

  • Uses a^(n-2) for a composite modulus n
  • Thinks the exponent route detects a missing inverse
  • Forgets that a divisible by p has no inverse
  • Claims the exponent route is always faster than extended Euclid
  • Reuses the exponent p-2 after the modulus changed