Modulo Calculator
Get a mod n right, negative numbers included, plus modular addition, multiplication, powers (aᵉ mod n) and inverses (a⁻¹ mod n), step by step. Numbers up to 10¹⁵ are handled exactly.
- Quotient ⌊a ÷ n⌋3
- Signed remainder (C, Java, JavaScript %)2
- Result (remainder)2
How it is calculated
Modular arithmetic works with remainders after division by a modulus; clocks, weekdays and calendars are everyday examples. IBAN check digits (ISO 13616, ISO/IEC 7064 MOD 97-10), hash functions and RSA encryption rely on it too. The % operator in programming languages can behave differently for negative numbers; the tool shows both.
a mod n = a − n × ⌊a ÷ n⌋ · 0 ≤ a mod n < na: the dividend (may be negative) · n: the modulus (positive) · ⌊ ⌋: rounding down. a ≡ b (mod n) means a and b leave the same remainder on division by n.- The quotient rounds down (negative numbers too) and the remainder is a − n × quotient, so it always lies between 0 and n − 1.
- For sums and products, remainders may be taken first: (a × b) mod n = ((a mod n) × (b mod n)) mod n.
- For aᵉ mod n the exponent is written in binary; the base is squared and reduced mod n at each step and multiplied into the result at the exponent’s 1 bits.
- a⁻¹ mod n comes from the extended Euclidean algorithm; it exists only when GCD(a, n) = 1.
Example
17 mod 5 = 2 because 17 = 3 × 5 + 2. For a negative number, −7 mod 3 = 2 because −7 = (−3) × 3 + 2. Eight hours after 10 o’clock: (10 + 8) mod 12 = 6. Power: 3⁷ mod 11 = 2,187 mod 11 = 9. Inverse: 17 × 2,753 = 46,801 = 15 × 3,120 + 1, so 17⁻¹ mod 3,120 = 2,753.
Frequently asked questions
How does mod work for negative numbers?
In mathematics the remainder is always 0 to n − 1: −7 mod 3 = 2 (−7 = −3 × 3 + 2). The % operator in C, Java and JavaScript rounds the quotient towards zero and gives −7 % 3 = −1; Python’s % and Excel’s MOD give 2.
How are huge powers worked out so fast?
By repeated squaring: 3²⁰⁰ is never written out; 3, 3², 3⁴, 3⁸ … are reduced mod n at each step and multiplied according to the binary digits of the exponent (200 = 11001000₂). Eight squarings suffice; 3²⁰⁰ mod 50 = 1.
When is there no modular inverse?
When a and n share a divisor above 1. GCD(6, 9) = 3, so 6⁻¹ mod 9 does not exist. If n is prime, every number except 0 has an inverse.
Source
- NIST DLMF §27.2 — congruences and Euler’s function
- ECMA-262 §6.1.6.1.6 Number::remainder: the result has the sign of the dividend (JavaScript %)
- ISO/IEC 9899:2011 (C11) draft N1570 §6.5.5: integer division truncates toward zero
- Java Language Specification (SE 21) §15.17.3: remainder operator %
- Python Language Reference §6.7: % takes the sign of its second operand
- Microsoft: MOD function (the result has the sign of the divisor)
- ISO 13616-1:2020 — IBAN structure (ISO/IEC 7064 MOD 97-10 check digits)