How this instrument works
A modular inverse of a number, taken with respect to some modulus, is whatever second number multiplies against the first to leave a remainder of exactly 1. Finding one has traditionally meant reaching for the extended Euclidean algorithm, a loop that tracks a pair of running coefficients until they settle on the answer. When the modulus happens to be prime, that loop becomes unnecessary: Fermat's Little Theorem hands over a closed-form shortcut instead, turning a multi-step algorithm into a single formula.
Fermat's Little Theorem states that for any prime modulus and any whole number a it does not divide, raising a to one less than that modulus and reducing by it always leaves 1 behind — a^(p−1) is congruent to 1, mod p. Split that exponent as a·a^(p−2), and the statement rearranges itself: a times a^(p−2) is congruent to 1, which is exactly the definition of a modular inverse. The quantity a^(p−2) mod p is a's own inverse, in one line, needing nothing more exotic than ordinary exponentiation followed by a single remainder step.
The prime requirement is not decoration. Drop it and the rearrangement stops working, because the underlying identity itself no longer holds for a composite modulus — some numbers below a composite m share a common factor with m and have no inverse at all, prime or otherwise. That is the genuine trade this calculator makes: restrict the modulus to primes, and a problem once needing an iterative algorithm collapses into a formula anyone can evaluate by hand for modest numbers.
- Enter the number you want to invert into Number (a).
- Enter a prime number into Prime modulus (p) — the shortcut only holds when p is genuinely prime.
- Confirm a is not itself a multiple of p; the sheet flags that case since no inverse would exist.
- Read Modular inverse of a, mod p — the value that, multiplied by a and reduced by p, returns 1.
- Multiply your entered a by the returned inverse and reduce by p yourself as a quick check that the answer lands on 1.
Worked example — inverting 3, modulo the prime 7
Set Number (a) to 3 and Prime modulus (p) to 7. The shortcut asks for a raised to the power p minus 2, so 3 raised to the 5th power: 3^5 equals 243. Reducing 243 by 7 leaves a remainder of 5, since 7 times 34 is 238 and 243 minus 238 is 5 — so Modular inverse of a, mod p reads exactly 5.
Multiplying back confirms it without any extra machinery: 3 times 5 equals 15, and 15 is one more than 14, which is 2 times 7. So 3 times 5 leaves a remainder of 1 when divided by 7, precisely the property a modular inverse is defined by. Nothing about 3 and 7 needed a coefficient-tracking loop to reach that 5 — Fermat's Little Theorem produced it directly from a single power and a single remainder.
Questions
What is a modular inverse, in plain terms?
It is the number that, multiplied by your original number and then reduced by the modulus, leaves a remainder of 1 — the modular stand-in for dividing by that number. For 3 modulo the prime 7, the inverse is 5, since 3 times 5 equals 15, which is 1 more than 14, a multiple of 7.
Why does this calculator require the modulus to be prime?
Because the shortcut it uses, a^(p−2) mod p, comes directly from rearranging Fermat's Little Theorem, and that theorem is stated for prime moduli specifically. Under a composite modulus the identity aᵐ⁻¹ ≡ 1 does not hold in general, so the same rearrangement no longer produces a correct inverse; a different method, such as the extended Euclidean algorithm, is needed instead.
How does this differ from computing an inverse with the extended Euclidean algorithm?
The extended Euclidean algorithm works for any modulus, prime or composite, by iterating a coefficient-tracking loop until it lands on the inverse. This calculator trades that generality for simplicity: restricted to a prime modulus, it needs only one exponentiation, a^(p−2), followed by one modulo operation — no loop, no tracked coefficients, no branching logic at all.
What is Fermat's Little Theorem, and how does it lead to this formula?
It states that for a prime modulus and any a it does not divide, raising a to one less than that modulus leaves a remainder of 1 once divided by it. Writing that exponent as 1 plus (p−2) splits the expression into a times a^(p−2), so multiplying those two together also leaves remainder 1 — meaning a^(p−2) mod p already is a's modular inverse, with no further rearrangement needed.
What happens if the entered number a is a multiple of the prime p?
No inverse exists, and this sheet flags that input rather than returning a value. A multiple of p is congruent to 0 modulo p, and nothing multiplied by 0 can ever produce a remainder of 1 under any modulus, so the theorem's own requirement that p not divide a is enforced here directly.
Does a larger prime modulus make the calculation harder?
Only in the size of the numbers involved, not in the number of steps: the method stays a single exponentiation followed by a single remainder regardless of how large p grows. In practice, very large primes call for repeated-squaring techniques to keep the intermediate power manageable, but the underlying formula, a^(p−2) mod p, never changes shape.