# Modular Arithmetic & Congruence Solver Perform modular addition, multiplication, and exponentiation, and solve linear modular congruence equations with clear steps. --- - **Canonical URL:** https://dothecalculation.com/calculators/modular-arithmetic-calculator - **Category:** Math calculators - **Publisher:** Do The Calculation (https://dothecalculation.com) - **Cost:** Free, no account or sign-up required - **Privacy:** Runs entirely in the browser; inputs are never sent to a server - **Methodology:** https://dothecalculation.com/methodology --- ## Modular Arithmetic & Congruence Solver Solve modular addition, multiplication, modular exponentiation, and linear congruences step-by-step. - Modular exponentiation (a^b mod n) - Modular inverse solver - Clock arithmetic visualization ## Introduction to Modular Arithmetic (Clock Arithmetic) Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value called the modulus. A familiar everyday example is the 12-hour clock: if it is 9 o'clock now, then 4 hours later it is 1 o'clock instead of 13. Mathematically, we say \(9 + 4 \equiv 1 \pmod{12}\). First formalized by Carl Friedrich Gauss in 1801, modular arithmetic is a cornerstone of discrete mathematics, number theory, computer science, and modern cryptography. In modular arithmetic, we focus on the remainders of division. Two integers \(a\) and \(b\) are said to be congruent modulo \(n\) if their difference \(a - b\) is an integer multiple of \(n\). This is written as \(a \equiv b \pmod n\). The modulus \(n\) must be a positive integer greater than 1. Modular operations behave consistently under addition, subtraction, and multiplication, which allows for simplified evaluations of extremely large numbers. This calculator evaluates standard modular operations and solves advanced problems. It computes modular addition, subtraction, multiplication, modular exponentiation (which is vital for RSA encryption), modular multiplicative inverses, and linear congruences, visualizing the remainder on a circular modulo clock. ## Modular Exponentiation and Fermat's Little Theorem Modular exponentiation involves finding \(a^b \pmod n\). Since calculating \(a^b\) directly for large exponents leads to overflow errors, we use binary exponentiation (also known as square-and-multiply) to evaluate the modulus at each intermediate step. Fermat's Little Theorem is often used to simplify these calculations: if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then: $$a^{p-1} \equiv 1 \pmod p$$ This theorem helps reduce large exponents, making cryptographic protocols like RSA and Diffie-Hellman key exchanges computationally efficient. ## Modular Multiplicative Inverses and Linear Congruences The modular multiplicative inverse of an integer \(a\) modulo \(n\) is an integer \(x\) such that: $$a x \equiv 1 \pmod n$$ This inverse exists if and only if \(a\) and \(n\) are coprime (meaning their greatest common divisor \(\gcd(a, n) = 1\)). It is solved using the Extended Euclidean Algorithm. A linear congruence is an equation of the form \(ax \equiv b \pmod n\). When \(\gcd(a, n) = 1\), this calculator solves it by multiplying both sides by the modular inverse of \(a\). When \(\gcd(a, n) = d > 1\), a solution exists only if \(d\) divides \(b\) — in that case there are exactly \(d\) distinct solutions modulo \(n\), which the calculator finds by reducing the equation to \(\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}}\) and listing every solution. ## How to Use This Calculator Choose an operation (add, subtract, multiply, power, modular inverse, or a linear congruence), enter operand A and B, and set the modulus N. The calculator shows the remainder, the modular clock dial, and the full step-by-step derivation. ## Worked Example: (7 + 5) mod 12 $$7 + 5 = 12$$ $$12 \bmod 12 = 0$$ So \(7 + 5 \equiv 0 \pmod{12}\) — like a 12-hour clock, adding 5 hours to 7 o'clock wraps back around to 12 (displayed as 0). This matches the calculator's default inputs (A=7, B=5, N=12). ## Related Calculators For the Extended Euclidean Algorithm used to find modular inverses, see the [Euclidean algorithm calculator](/calculators/euclidean-algorithm-calculator). To factor the modulus itself, use the [prime factorization calculator](/calculators/prime-factorization-calculator). ## Frequently asked questions ### What is modular arithmetic? Modular arithmetic is a system of arithmetic for integers where numbers wrap around after reaching a specific value called the modulus. ### What does "mod" mean? "Mod" is the modulo operator, representing the remainder left over after dividing one integer by another. ### What is modular congruence? Two numbers a and b are congruent modulo n (a ≡ b mod n) if they have the same remainder when divided by n. ### How do you calculate modular exponentiation? Evaluate aᵇ mod n using the square-and-multiply algorithm to take remainders at each multiplication step, avoiding numeric overflow. ### What is a modular multiplicative inverse? It is an integer x such that ax ≡ 1 (mod n). It acts as the reciprocal of a in modular space, and only exists when a and n are coprime. ### When does a modular inverse exist? It exists if and only if the number a and the modulus n are coprime, meaning gcd(a, n) = 1. This calculator reports "Undefined" when that condition isn't met. ### What is a linear congruence, and can this calculator handle equations with multiple solutions? A linear congruence is an equation of the form ax ≡ b (mod n). Yes — when gcd(a, n) = d is greater than 1 and d divides b, this calculator finds and lists all d distinct solutions modulo n, not just a single one. ### What is Fermat's Little Theorem? It states that for a prime p and coprime integer a, a^(p−1) ≡ 1 (mod p). ### What are modular arithmetic applications in computer science? It is used in hash tables, random number generation, digital clock systems, and array index wrap-arounds. ### How is modular arithmetic used in cryptography? It forms the basis of public-key encryption systems like RSA, where calculations are performed modulo very large prime numbers. ### What is Euler's Totient Theorem? It generalizes Fermat's theorem, stating that a^φ(n) ≡ 1 (mod n) for any integer a coprime to n, where φ(n) is Euler's totient function. ### Can you divide in modular arithmetic? Direct division is not defined. Instead, division is performed by multiplying by the modular multiplicative inverse of the divisor — this calculator's "A⁻¹ (mod N)" mode computes exactly that inverse. ## Related concepts - **Extended Euclidean Algorithm** — The mathematical algorithm used to find modular multiplicative inverses. - **Modular Exponentiation** — Efficiently calculating powers modulo a number. - **Coprime Integers** — Numbers whose greatest common divisor is exactly 1. ## Related guides - [Scientific Notation Guide: Powers of Ten Made Practical](https://dothecalculation.com/blog/math/scientific-notation-basics) — Learn how to convert, compare, and calculate with powers of ten using worked examples and the live DTC scientific calculator. ## Related calculators - [Extended Euclidean GCD Solver](https://dothecalculation.com/calculators/euclidean-algorithm-calculator) — Compute the GCD of two numbers and find Bezout coefficients using the Extended Euclidean algorithm with clear step-by-step results. - [Circle Equation & Geometry Solver](https://dothecalculation.com/calculators/circle-solver) — Convert between standard and general circle equation forms, find centers and radii, and compute areas with this free geometry solver. - [Mixed Number Fraction Calculator](https://dothecalculation.com/calculators/mixed-number-calculator) — Add, subtract, multiply, divide, and simplify mixed number fractions with clear step-by-step conversions and instant results. - [Decimal to Fraction Calculator](https://dothecalculation.com/calculators/decimal-to-fraction-calculator) — Use our free decimal to fraction calculator to convert any decimal to a fraction. Shows step-by-step work for terminating and repeating decimals. - [Fraction to Decimal Calculator](https://dothecalculation.com/calculators/fraction-to-decimal-calculator) — Convert fractions to decimals with step-by-step long division and repeating decimal bar notation shown clearly and instantly. - [Prime Number Checker & List Generator](https://dothecalculation.com/calculators/prime-number-calculator) — Check primality, find the next prime, and generate prime numbers within a custom range using fast sieve methods instantly. --- _This mathematical solver is designed for academic, engineering, and educational analysis. Rounding errors, numerical tolerances, or algorithm constraints might apply near poles, boundary conditions, or complex coordinate spaces. Always verify critical computations independently._ --- _Source: [Do The Calculation](https://dothecalculation.com/calculators/modular-arithmetic-calculator). Quote freely with attribution and a link to this page._