ToolSphere

Modular Arithmetic Calculator

Computer science

Calculate modular remainders, inverses via extended Euclid, powers by repeated squaring, and GCD with step-by-step tables for US discrete math courses.

Modular Arithmetic Results

Exact BigInt
Remainder (a mod n)

17

17 = (0) × 60 + 17

Modular Inverse (a⁻¹ mod n)

53

gcd(17, 60) = 1

Exponentiation (aᵇ mod n)

53

4 mults, 5 squares

gcd(a, b) and lcm(a, b)

1 / lcm 731

4 division steps

Modulo 60 Arithmetic Operations
Sum (a + b): 0
Diff (a - b): 34
Prod (a × b): 11
Div (a / b): 59
Course presets:

Any positive or negative integer.

Second integer or power for aᵇ mod n.

Positive modulus (e.g. 60 or prime).

Extended Euclidean Algorithm & Modular Inverse of 17 mod 60

Inverse: 53

gcd(17, 60) = 1. Since (-7) × (17) ≡ 1 (mod 60), the modular inverse is 53.

StepQuotient (q)Remainder (r)Coeff x (a)Coeff y (n)Bezout Identity Equation
0-600160 = (0) × (17) + (1) × 60
1-171017 = (1) × (17) + (0) × 60
239-319 = (-3) × (17) + (1) × 60
3184-18 = (4) × (17) + (-1) × 60
411-721 = (-7) × (17) + (2) × 60
58060-170 = (60) × (17) + (-17) × 60
Verification: (17 × 53) mod 60 = 901 mod 60 = 1.

Modular Exponentiation: 1743 mod 60 by Repeated Squaring

Exponent binary: 101011₂

Computed 17^43 mod 60 using 4 multiplications and 5 squarings. Final result is 53.

StepPower 2ⁱBitCurrent Power mod nActionAccumulator mod n
12^0 = 1117Bit is 1: multiply accumulator by 17 mod 60 → 1717
22^1 = 2149Bit is 1: multiply accumulator by 49 mod 60 → 5353
32^2 = 401Bit is 0: skip multiplication, accumulator stays 5353
42^3 = 811Bit is 1: multiply accumulator by 1 mod 60 → 5353
52^4 = 1601Bit is 0: skip multiplication, accumulator stays 5353
62^5 = 3211Bit is 1: multiply accumulator by 1 mod 60 → 5353

Euclidean Algorithm for gcd(17, 43) and lcm(17, 43)

gcd: 1 · lcm: 731

gcd(17, 43) = 1, lcm(17, 43) = 731.

StepDividendDivisorQuotientRemainderDivision Equation
143172943 = 2 × 17 + 9
21791817 = 1 × 9 + 8
398119 = 1 × 8 + 1
481808 = 8 × 1 + 0

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Modular Arithmetic Calculator

  1. 1Enter an integer for a (the dividend, base, or first operand).
  2. 2Enter an integer for b (the second operand or exponent for modular exponentiation).
  3. 3Enter a positive integer modulus n greater than 0.
  4. 4Review the primary results card showing a mod n, modular inverses, a^b mod n, and gcd or lcm.
  5. 5Inspect the Extended Euclidean Algorithm table for Bezout coefficients and modular inverse verification.
  6. 6Follow the repeated squaring binary expansion trace for step-by-step modular powers.
  7. 7Check the Euclidean algorithm division steps to verify gcd(a, b) and lcm(a, b).

About Modular Arithmetic Calculator

What is modular arithmetic and congruence in discrete mathematics?

Modular arithmetic, often called clock arithmetic, is a system of arithmetic for integers where numbers wrap around upon reaching a certain value called the modulus. In US university computer science and discrete mathematics courses (such as Berkeley CS 70, MIT 6.042J, or standard curricula following Kenneth Rosen's Discrete Mathematics and Its Applications), modular arithmetic is the foundational language of algorithm analysis, number theory, hashing, and modern public-key cryptography.

Two integers a and b are defined to be congruent modulo n, written as a ≡ b (mod n), if their difference (a - b) is an integer multiple of the modulus n. Equivalently, a ≡ b (mod n) means that a and b leave the exact same remainder when divided by n. The Division Algorithm states that for any integer a and positive integer n, there exist unique integers q (the quotient) and r (the remainder) such that:

a = q × n + r, where 0 ≤ r < n

Here, r is the canonical remainder, denoted a mod n. For example, dividing 17 by 60 gives 17 = 0 × 60 + 17, so 17 mod 60 = 17.

The negative modulo trap: programming language % vs mathematical modulo

One of the most frequent sources of bugs in homework assignments and competitive programming is assuming that the remainder operator in languages like C, C++, Java, and JavaScript computes the true mathematical modulo.

In C, C++, Java, and JavaScript, the % operator is a remainder operator, not a modulo operator. It truncates towards zero. When dividing -17 by 5:

  • Truncating division yields a quotient of -3 and a remainder of -2, because -17 = (-3) × 5 + (-2).
  • However, the mathematical Division Algorithm strictly requires 0 ≤ r < n. The remainder cannot be negative.
  • Rewriting -17 with a non-negative remainder gives -17 = (-4) × 5 + 3.
  • Therefore, in mathematics and discrete math courses, -17 mod 5 = 3, not -2.

This calculator uses true mathematical modulo across all inputs: if a % n is negative, it automatically normalizes the remainder to ((a % n) + n) % n, guaranteeing a result in the range [0, n - 1].

The Extended Euclidean Algorithm: finding modular inverses and Bezout coefficients

In standard arithmetic, every non-zero real number a has a multiplicative inverse 1 / a such that a × (1 / a) = 1. In modular arithmetic modulo n, division is defined through the modular multiplicative inverse. An integer x is the modular inverse of a modulo n if:

a × x ≡ 1 (mod n)

This equivalence means that a × x - 1 is a multiple of n, so there exists an integer y such that:

a × x + n × y = 1

This equation is a special case of Bezout's identity, which states that for any integers a and n, there exist integers x and y (called Bezout coefficients) such that a × x + n × y = gcd(a, n).

A modular inverse exists if and only if gcd(a, n) = 1 (meaning a and n are relatively prime, or coprime). If gcd(a, n) > 1, no modular inverse can ever exist, because any linear combination a × x + n × y must be a multiple of gcd(a, n), which cannot equal 1.

Worked example: finding 17⁻¹ mod 43

Consider finding the modular inverse of a = 17 modulo n = 43:

  1. Start with Row 0: r0 = 43, x0 = 0, y0 = 1
  2. Row 1: r1 = 17, x1 = 1, y1 = 0
  3. Divide 43 by 17: quotient q = 2, remainder r = 43 - 2 × 17 = 9. Update x = 0 - 2 × 1 = -2, and y = 1 - 2 × 0 = 1.
  4. Divide 17 by 9: quotient q = 1, remainder r = 17 - 1 × 9 = 8. Update x = 1 - 1 × (-2) = 3, and y = 0 - 1 × 1 = -1.
  5. Divide 9 by 8: quotient q = 1, remainder r = 9 - 1 × 8 = 1. Update x = -2 - 1 × 3 = -5, and y = 1 - 1 × (-1) = 2.
  6. Divide 8 by 1: quotient q = 8, remainder r = 0. The algorithm terminates.

The last non-zero remainder is 1, confirming gcd(17, 43) = 1. Bezout's identity gives:
(-5) × 17 + 2 × 43 = 1

Taking this equation modulo 43:
(-5) × 17 ≡ 1 (mod 43)

To find the canonical positive inverse in [0, 42], reduce -5 modulo 43:
-5 mod 43 = 38

Verifying: 17 × 38 = 646 = 15 × 43 + 1 ≡ 1 (mod 43). Thus, 17⁻¹ ≡ 38 (mod 43).

Modular exponentiation by repeated squaring (binary exponentiation)

Computing powers like 3¹³ mod 7 or cryptographic values like gᵃ mod p with 2048-bit numbers cannot be done by computing aᵇ as a massive integer and then taking the remainder. The number 3¹³ is small (1,594,323), but 3¹⁰⁰⁰ has 478 decimal digits, and cryptographic powers have thousands of bits, which would exhaust memory and CPU resources.

Instead, discrete mathematics uses modular exponentiation by repeated squaring (also known as binary exponentiation), which computes aᵇ mod n in O(log b) multiplications:

  1. Express the exponent b in binary. For example, 13 = 1101₂ = 8 + 4 + 1 = 2³ + 2² + 2⁰.
  2. Compute repeated squarings of the base modulo n:
    • 3¹ mod 7 = 3
    • 3² mod 7 = 9 mod 7 = 2
    • 3⁴ mod 7 = 2² mod 7 = 4
    • 3⁸ mod 7 = 4² mod 7 = 16 mod 7 = 2
  3. Multiply the running accumulator by the powers corresponding to bits that are 1:
    • Bit 0 is 1: accumulator = (1 × 3) mod 7 = 3
    • Bit 1 is 0: skip multiplication, accumulator stays 3
    • Bit 2 is 1: accumulator = (3 × 4) mod 7 = 12 mod 7 = 5
    • Bit 3 is 1: accumulator = (5 × 2) mod 7 = 10 mod 7 = 3

Final result: 3¹³ mod 7 = 3. We computed the power using only 3 squarings and 3 multiplications, rather than 12 successive multiplications.

Applications in computer science and public-key cryptography

Modular arithmetic is the cornerstone of computer security:

  • RSA Cryptography: Key generation chooses two large primes p and q, sets n = p × q, and selects a public exponent e coprime to (p - 1)(q - 1). The private key d is computed as the modular inverse d = e⁻¹ mod ((p - 1)(q - 1)) using the Extended Euclidean Algorithm. Encryption computes c = mᵉ mod n, and decryption computes m = cᵈ mod n via repeated squaring.
  • Diffie-Hellman Key Exchange: Relies on modular exponentiation gᵃ mod p and the hardness of the discrete logarithm problem.
  • Hashing and Checksums: Hash tables and cyclic redundancy checks use prime moduli to distribute keys evenly and minimize collisions.

Guides and tutorials

Frequently asked questions

What is the difference between JavaScript's % operator and mathematical modulo?

In JavaScript, Java, C, and C++, the % operator computes the truncated remainder, which preserves the sign of the dividend. For example, -17 % 5 returns -2. In mathematics and discrete mathematics courses, the remainder must always be non-negative: 0 ≤ r < n. Therefore, -17 mod 5 is 3, because -17 = (-4) × 5 + 3. This calculator implements true mathematical modulo.

When does a modular multiplicative inverse exist?

An integer a has a modular inverse modulo n if and only if gcd(a, n) = 1 (meaning a and n are coprime or relatively prime). If gcd(a, n) = d > 1, no integer x can satisfy a × x ≡ 1 (mod n), because a × x + n × y is always a multiple of d and can never equal 1.

How does the Extended Euclidean Algorithm find modular inverses?

The Euclidean algorithm finds gcd(a, n) by repeated division. The Extended Euclidean Algorithm tracks Bezout coefficients x and y at each step such that a × x + n × y = gcd(a, n). When gcd(a, n) = 1, this gives a × x + n × y = 1. Reducing both sides modulo n yields a × x ≡ 1 (mod n), so x (normalized into [0, n - 1]) is the modular inverse.

Why is repeated squaring faster than multiplying b times?

Multiplying a base b times requires O(b) operations, which is impossible when b has hundreds of digits. Repeated squaring expresses b in binary and squares the base at each bit position, reducing the complexity to O(log b) multiplications. For example, computing a power with an exponent of 1,000,000 takes only about 20 squarings instead of one million multiplications.

Can an exponent be negative in modular exponentiation?

Yes, provided the base a has a modular inverse modulo n (gcd(a, n) = 1). The negative power a^(-b) mod n is computed as (a^(-1))^b mod n. If gcd(a, n) ≠ 1, negative modular powers are undefined because the inverse does not exist.

How is modular division defined?

In modular arithmetic, division (a / b) mod n is defined as multiplying a by the modular inverse of b: a × b^(-1) mod n. Modular division is only defined when gcd(b, n) = 1. Unlike real number division, modular division yields an integer result in [0, n - 1].

Does this calculator handle large numbers without overflow?

Yes. The calculator uses JavaScript's native BigInt data type, providing arbitrary-precision integer arithmetic without 64-bit floating point precision limits. You can compute modular inverses, GCDs, and powers for large numbers with complete accuracy.

What is Bezout's identity?

Bezout's identity states that for any non-zero integers a and b, there exist integers x and y such that a × x + b × y = gcd(a, b). The integers x and y are called Bezout coefficients. They can be found using the Extended Euclidean Algorithm and are essential for solving linear Diophantine equations and finding modular inverses.

What is the relationship between GCD and LCM?

For any two positive integers a and b, their product equals the product of their greatest common divisor and least common multiple: a × b = gcd(a, b) × lcm(a, b). Therefore, once gcd(a, b) is computed using the Euclidean algorithm, lcm(a, b) is calculated directly as (a × b) / gcd(a, b).

Why is modular arithmetic used in RSA cryptography?

RSA encryption relies on Euler's Totient Theorem in modular arithmetic. Messages are encrypted as c = m^e mod n and decrypted as m = c^d mod n, where e × d ≡ 1 (mod φ(n)). Modular arithmetic keeps ciphertext within fixed bounds and makes reversing the operation computationally infeasible without knowing the prime factors of n.

Have a suggestion for Modular Arithmetic Calculator?Share your feedback ↗