Modular Arithmetic Calculator
Perform modular arithmetic operations including modular exponentiation and inverse. Enter values for instant results with step-by-step formulas.
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.
What is the Euler totient function and how does it relate to modular arithmetic?
The Euler totient function phi(n) counts how many integers from 1 to n are coprime to n (share no common factor with n other than 1). For a prime p, phi(p) = p - 1 because all integers from 1 to p-1 are coprime to p. For a product of two primes p and q, phi(pq) = (p-1)(q-1). Euler theorem states that if a and n are coprime, then a^phi(n) is congruent to 1 mod n. This generalizes Fermat little theorem (where n is prime). The totient function is crucial in RSA cryptography: the public and private keys are constructed so that their product is congruent to 1 modulo phi(n), enabling encryption and decryption. Computing phi(n) is easy if you know the prime factorization of n, but hard otherwise.
How is modular arithmetic used in RSA encryption?
RSA encryption relies heavily on modular arithmetic. Two large primes p and q are chosen, and their product n = p times q forms the modulus. The totient phi(n) = (p-1)(q-1) is computed. A public exponent e is chosen coprime to phi(n), and the private key d is the modular inverse of e modulo phi(n). To encrypt a message M, compute C = M^e mod n. To decrypt, compute M = C^d mod n. This works because of Euler theorem: M^(ed) is congruent to M mod n since ed is congruent to 1 mod phi(n). The security rests on the difficulty of factoring n to recover p and q, which would reveal phi(n) and allow computing d. Modern RSA uses 2048-bit or larger keys where factoring n is computationally infeasible.