Modular Arithmetic Calculator
Calculate a mod n, modular inverses, and a^b mod n with Euclidean algorithm steps, repeated-squaring work, and clear cryptography-friendly explanations.
Reduce
a -> r
Find the residue in one modulo cycle.
Invert
gcd(a,n)=1
Use Euclid to prove an inverse exists.
Power
a^b mod n
Square and reduce instead of expanding.
Calculating...
Choose an operation and calculate a remainder, modular inverse, or modular power with the steps shown.
What Is Modular Arithmetic?
Modular arithmetic is arithmetic on remainders. Instead of asking only what a division gives as a quotient, it asks where a number lands after wrapping around a fixed modulus. In the expression a mod n, n is the modulus and the answer is the residue left after dividing a by n.
This is the same idea as a clock. If the hour hand moves 17 hours on a 12-hour clock, it lands at 5 because 17 mod 12 = 5. The same wraparound structure appears in computer science, hashing, checksums, calendars, cyclic groups, and cryptography.
Modulo Clock Diagram
Modulo 12 wraps every integer into one of 12 residues: 0 through 11. Larger moduli work the same way; the cycle just has more positions.
How to Calculate a mod n
To calculate a mod n, divide a by n and keep the least non-negative remainder. For positive a this feels like ordinary division. For negative a, the least non-negative residue rule matters: -7 mod 5 is 3 because -7 = -2 × 5 + 3.
The calculator uses this standard normalization so answers always fall in the range 0 ≤ r < n. That convention is the one most often used in number theory, programming languages that expose a true modulo operation, and cryptographic formulas.
What Is a Modular Inverse?
A modular inverse is a number that reverses multiplication under a modulus. If x is the inverse of a modulo n, then a × x ≡ 1 (mod n). For example, 7 inverse mod 26 is 15 because 7 × 15 = 105, and 105 mod 26 = 1.
Not every number has an inverse. The key test is gcd(a, n) = 1. If a and n share a factor greater than 1, multiplication by a cannot reach every residue, so there is no value that acts like a true inverse.
Euclidean Algorithm Flow
Start
a and n
GCD
run Euclid
Back substitute
track coefficients
Inverse
normalize x mod n
Euclidean Algorithm for Modular Inverses
The extended Euclidean algorithm does more than find the gcd. It also finds coefficients x and y such that ax + ny = gcd(a, n). When the gcd is 1, that identity becomes ax + ny = 1. Reducing both sides modulo n removes the ny term, leaving ax ≡ 1 (mod n). That coefficient x is the modular inverse after it is normalized into the range 0 to n - 1.
This is why the calculator shows both the Euclidean division table and the coefficient/back-substitution steps. The final number is useful, but the proof is what students need when learning number theory, RSA examples, affine ciphers, or congruence equations.
How Modular Exponentiation Works
Modular exponentiation calculates a^b mod n without expanding a^b into a huge integer. The fast method is repeated squaring: reduce the base, square it modulo n, and multiply into the running answer only when the current binary exponent bit is 1.
Repeated-Squaring Visual
Reduce
base = a mod n
Square
base² mod n
Multiply
when bit = 1
Result
final residue
This method is essential for cryptography because exponents can be hundreds or thousands of bits long. Direct expansion is impractical; repeated squaring keeps every intermediate value smaller than the modulus.
Why Modular Arithmetic Matters in Cryptography
Many public-key systems are built on modular arithmetic. RSA uses modular exponentiation for encryption, decryption, signing, and verification. Modular inverses appear when deriving private exponents and solving congruence equations. Even when professional systems use carefully audited libraries, learning the small-number version is the best way to understand the underlying math.
Common Modular Arithmetic Examples
| Problem | Result | Why |
|---|---|---|
| 17 mod 5 | 2 | 17 = 3 × 5 + 2 |
| -7 mod 5 | 3 | -7 = -2 × 5 + 3 |
| 7^-1 mod 26 | 15 | 7 × 15 mod 26 = 1 |
| 5^117 mod 19 | 1 | Repeated squaring keeps values reduced |
Trusted Modular Arithmetic Resources
Authoritative references for modular arithmetic, Euclidean algorithms, and cryptography context.
Modular Arithmetic FAQ
What does a mod n mean? +
It means the least non-negative remainder after dividing a by n. For example, 17 mod 5 is 2.
Can the remainder be negative? +
In this calculator, no. It returns the standard least non-negative residue from 0 to n - 1.
When does a modular inverse exist? +
A modular inverse exists exactly when gcd(a, n) = 1. If a and n share a factor, the inverse does not exist.
How do you find a modular inverse by hand? +
Use the extended Euclidean algorithm to write ax + ny = 1. The coefficient x, normalized modulo n, is the inverse.
Why use modular exponentiation instead of calculating a^b first? +
Because a^b becomes enormous very quickly. Repeated squaring reduces after every multiplication, keeping the calculation fast.
Is modular arithmetic used in RSA? +
Yes. RSA uses modular exponentiation, modular inverses, and arithmetic modulo a product of large primes.