Modular Arithmetic Calculator
Perform modular arithmetic operations including modular exponentiation and inverse. Enter values for instant results with step-by-step formulas.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Modular Arithmetic Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: a mod m = r, where a = m x q + r and 0 <= r < m
Worked example — 7^13 mod 11 = 2 | Computed in 4 steps instead of 13
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 Step 1: result=1, base=7 Bit 1 (1): result = 1 x 7 = 7 mod 11 = 7, base = 7^2 = 49 mod 11 = 5 Bit 2 (0): base = 5^2 = 25 mod 11 = 3 Bit 3 (1): result = 7 x 3 = 21 mod 11 = 10, base = 3^2 = 9 mod 11 = 9 Bit 4 (1): result = 10 x 9 = 90 mod 11 = 2 7^13 mod 11 = 2 Verify: 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: 43 = 17 x 2 + 9 17 = 9 x 1 + 8 9 = 8 x 1 + 1 8 = 1 x 8 + 0 GCD = 1, so inverse exists Back-substitute: 1 = 9 - 8 x 1 1 = 9 - (17 - 9) = 2 x 9 - 17 1 = 2(43 - 2 x 17) - 17 = 2 x 43 - 5 x 17 So 17 x (-5) = 1 mod 43, and -5 mod 43 = 38 Verify: 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.
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) states that if you have a system of simultaneous congruences with pairwise coprime moduli, there exists a unique solution modulo the product of all the moduli. For example, x congruent to 2 mod 3 and x congruent to 3 mod 5 has the unique solution x = 8 mod 15. The theorem dates back to the third century Chinese mathematician Sun Tzu. In practice, CRT is used to speed up RSA decryption by performing computations modulo p and q separately (which is faster since the numbers are smaller) and combining the results. CRT also appears in signal processing, polynomial interpolation, and solving scheduling problems where events have different periodic cycles.
How does modular arithmetic apply to checksums and error detection?
Modular arithmetic is the basis for many checksum and error detection algorithms used in everyday technology. ISBN-10 book numbers use mod 11 to detect single-digit errors and transpositions. Credit card numbers use the Luhn algorithm with mod 10 to catch common transcription errors. UPC barcodes use mod 10 check digits. Bank routing numbers use a weighted mod 10 checksum. These systems work by computing a weighted sum of all digits and checking that the result satisfies a specific modular condition. If any single digit is changed, the checksum will fail with high probability. The mathematical properties of modular arithmetic guarantee that specific types of errors (single-digit changes, adjacent transpositions) are always detected.
What are congruence classes and how do they partition integers?
A congruence class modulo m is the set of all integers that have the same remainder when divided by m. For modulus 5, there are exactly 5 congruence classes: the set of integers congruent to 0 (multiples of 5), those congruent to 1, to 2, to 3, and to 4. Every integer belongs to exactly one congruence class, so the classes partition all integers into m disjoint, infinite sets. The congruence class of a modulo m is denoted [a] and consists of all numbers of the form a + km where k is any integer. Arithmetic on congruence classes is well-defined: adding or multiplying any representatives from two classes always produces a result in the same class, which is what makes modular arithmetic consistent and useful.
What is Fermat Little Theorem and how is it used?
Fermat Little Theorem states that if p is a prime number and a is any integer not divisible by p, then a^(p-1) is congruent to 1 modulo p. Equivalently, a^p is congruent to a modulo p for all integers a. For example, 2^6 = 64 is congruent to 1 mod 7 (since 7 is prime and 6 = 7-1). This theorem is used in primality testing: if a^(n-1) is not congruent to 1 mod n for some base a, then n is definitely not prime. This is the basis of the Miller-Rabin primality test. Fermat theorem also simplifies modular exponentiation: to compute 2^100 mod 7, note that 2^6 is congruent to 1 mod 7, so 2^100 = 2^(6 times 16 + 4) is congruent to 2^4 = 16 is congruent to 2 mod 7.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Modular Arithmetic Visualizer
Calculate modular arithmetic visualizer with inputs, formulas, and instant results.
🧮Clock Arithmetic Calculator
Calculate clock arithmetic with inputs, formulas, and instant results.
🧮Arithmetic Sequence Calculator
Calculate arithmetic sequence with inputs, formulas, and instant results.
🧮Arithmetic Progression Calculator
Calculate nth term, sum, and properties of arithmetic sequences and series.
🧮Big Number Calculator
Perform arithmetic operations on extremely large numbers beyond standard calculator limits.
🧮Annulus Area Calculator
Calculate annulus area with inputs, formulas, and instant results.
🧮Area Calculator
Calculate area with inputs, formulas, and instant results.
🧮Area of a Rectangle Calculator
Calculate the area, perimeter, and diagonal of a rectangle. Find missing sides from known area. Convert between metric and imperial area units.