Modulo Calculator (a mod n, modular exponent)

Understanding the modulo calculator — concept and principle

The modulo operation, a mod n, gives the remainder left after dividing a by n. On a 12-hour clock, 17 hours after midnight is 5 o'clock because 17 mod 12 = 5. This calculator finds a mod n, the modular power aᵉ mod n, and the modular inverse of a, operations used in number theory, check digits, hashing and cryptography.

How it is calculated

• Remainder: a mod n = a − n × ⌊a ÷ n⌋, always between 0 and n − 1 (so −7 mod 5 = 3, not −2).
• Modular power: aᵉ mod n by fast exponentiation (square-and-multiply), reducing after every step.
• Modular inverse: the number x with a × x ≡ 1 (mod n), found with the extended Euclidean algorithm. It exists only when a and n are coprime, that is gcd(a, n) = 1.

The principle

Two numbers are congruent modulo n, written a ≡ b (mod n), when they leave the same remainder. Congruence respects addition and multiplication: you can reduce at any stage and the final remainder does not change. That is why aᵉ mod n can be computed without ever forming the huge number aᵉ. Fast exponentiation writes e in binary and squares the base once per bit, so the work grows only with the number of digits of e. The inverse comes from Bézout's identity: the extended Euclidean algorithm finds integers x and y with a x + n y = gcd(a, n). When the gcd is 1, reducing this equation modulo n gives a x ≡ 1.

Worked example

1. Inputs: a = 17, n = 5, e = 3.
2. 17 ÷ 5 = 3 remainder 2, so 17 mod 5 = 2.
3. Modular power: 17³ ≡ 2³ = 8 ≡ 3 (mod 5). Directly, 17³ = 4,913 = 982 × 5 + 3, so 17³ mod 5 = 3.
4. Inverse: gcd(17, 5) = 1, so an inverse exists. 17 × 3 = 51 = 10 × 5 + 1, so 17 × 3 ≡ 1 (mod 5) and the inverse is 3.

How to read the result

The remainder tells you where a lands in a cycle of length n: a result of 0 means n divides a exactly. A modular inverse lets you "divide" in modular arithmetic; if the calculator reports none, a and n share a common factor and division by a is impossible modulo n. Modular powers with a prime n obey Fermat's little theorem, aⁿ⁻¹ ≡ 1 (mod n) when n does not divide a, which is a quick consistency check: 2⁴ mod 5 = 1.

Common mistakes

• Expecting a negative remainder for a negative a: programming languages such as JavaScript and C return −2 for −7 % 5, while the mathematical result shown here is 3.
• Computing aᵉ in full before reducing, which overflows for large exponents.
• Assuming every number has an inverse; 2 has no inverse modulo 4.

Frequently asked questions

What is the difference between mod and remainder?

For positive numbers they are the same. For negative numbers, "mod" in mathematics always gives a result from 0 to n − 1, while a programming remainder may keep the sign of a.

What is the modular inverse used for?

It solves equations such as 3x ≡ 1 (mod 7), where x = 5, and it is the step that produces the private key in RSA.

Sources: Carl Friedrich Gauss, Disquisitiones Arithmeticae (1801), Section I (congruences) · Donald E. Knuth, The Art of Computer Programming, Vol. 2, §4.5.2 (the greatest common divisor) and §4.6.3 (evaluation of powers)