Modular Arithmetic Calculator
Perform modular arithmetic operations including modular exponentiation and inverse. Enter values for instant results with step-by-step formulas.
Reviewed by Manoj Kumar, Mathematics Educator
Formula
a mod m = r, where a = m x q + r and 0 <= r < m
Modular arithmetic computes the remainder after division. Key operations include modular addition ((a+b) mod m), multiplication ((a*b) mod m), exponentiation (a^n mod m via square-and-multiply), and inverse (a^(-1) mod m exists iff GCD(a,m)=1). Euler theorem: a^phi(m) = 1 mod m when GCD(a,m)=1.
Worked Examples
Example 1: Modular Exponentiation for Cryptography
Problem:Compute 7^13 mod 11 using the square-and-multiply method.
Solution:13 in binary = 1101\nStep 1: result=1, base=7\nBit 1 (1): result = 1 x 7 = 7 mod 11 = 7, base = 7^2 = 49 mod 11 = 5\nBit 2 (0): base = 5^2 = 25 mod 11 = 3\nBit 3 (1): result = 7 x 3 = 21 mod 11 = 10, base = 3^2 = 9 mod 11 = 9\nBit 4 (1): result = 10 x 9 = 90 mod 11 = 2\n7^13 mod 11 = 2\nVerify: phi(11) = 10, 7^10 = 1 mod 11, 7^13 = 7^3 = 343 mod 11 = 2
Result:7^13 mod 11 = 2 | Computed in 4 steps instead of 13
Example 2: Finding Modular Inverse
Problem:Find the modular inverse of 17 mod 43.
Solution:Extended Euclidean Algorithm:\n43 = 17 x 2 + 9\n17 = 9 x 1 + 8\n9 = 8 x 1 + 1\n8 = 1 x 8 + 0\nGCD = 1, so inverse exists\nBack-substitute:\n1 = 9 - 8 x 1\n1 = 9 - (17 - 9) = 2 x 9 - 17\n1 = 2(43 - 2 x 17) - 17 = 2 x 43 - 5 x 17\nSo 17 x (-5) = 1 mod 43, and -5 mod 43 = 38\nVerify: 17 x 38 = 646 = 15 x 43 + 1
Result:17^(-1) mod 43 = 38 | Verify: 17 x 38 = 646 = 1 mod 43
Frequently Asked Questions
What is modular arithmetic and why is it called clock arithmetic?
Modular arithmetic is a system of arithmetic for integers where numbers wrap around after reaching a certain value called the modulus. It is called clock arithmetic because a 12-hour clock is a natural example: after 12, the hours wrap back to 1, so 15 o'clock is 3 in 12-hour time (15 mod 12 = 3). In notation, we write a is congruent to b (mod m) to mean that a and b have the same remainder when divided by m, or equivalently that m divides (a - b). Modular arithmetic is fundamental to number theory, cryptography, computer science, and has applications in checksums, hash functions, and cyclic structures. It provides a finite, well-structured arithmetic system that is both theoretically elegant and practically useful.
How does modular addition and multiplication work?
Modular addition and multiplication follow the same rules as regular arithmetic, with the result reduced modulo m afterward. For addition: (a + b) mod m = ((a mod m) + (b mod m)) mod m. For multiplication: (a x b) mod m = ((a mod m) x (b mod m)) mod m. For example, (17 + 8) mod 5 = 25 mod 5 = 0, or equivalently (2 + 3) mod 5 = 5 mod 5 = 0. This property that you can reduce before or after the operation is crucial for computing with very large numbers, as in cryptography. In RSA encryption, numbers with hundreds of digits are multiplied modulo a large prime product, and intermediate reductions keep the numbers manageable throughout the computation.
What is modular exponentiation and how is it computed efficiently?
Modular exponentiation computes a^n mod m and is one of the most important operations in modern cryptography. The naive approach of computing a^n first and then taking the modulus is impractical for large exponents because a^n can have billions of digits. Instead, the fast exponentiation (binary exponentiation or square-and-multiply) method reduces the modulus at each step, keeping numbers small. It works by expressing the exponent in binary: for each bit, square the running result, and if the bit is 1, multiply by the base. This computes a^n mod m in O(log n) multiplications instead of O(n). For example, 3^100 mod 7 requires only about 7 squarings and multiplications instead of 100, making RSA and Diffie-Hellman key exchange computationally feasible.
What is a modular multiplicative inverse and when does it exist?
The modular multiplicative inverse of a modulo m is a number x such that (a times x) mod m = 1. It exists if and only if a and m are coprime (their GCD is 1). For example, the inverse of 3 modulo 7 is 5, because 3 times 5 = 15, and 15 mod 7 = 1. The inverse can be found using the Extended Euclidean Algorithm, which solves the equation ax + my = 1 for x. If the GCD of a and m is not 1, no inverse exists because no multiple of a can produce a remainder of 1. Modular inverses are essential in cryptography for decryption (RSA uses them to compute the private key) and in solving systems of linear congruences using the Chinese Remainder Theorem.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy