GCD Calculator
Calculate the Greatest Common Divisor (GCD) of two or more numbers using the Euclidean algorithm. Also known as GCF or HCF.
Modular Arithmetic Calculator
Calculate modular arithmetic operations: a mod n, modular addition, subtraction, multiplication, and exponentiation.
Any integer (negative allowed)
Must be > 0
17 mod 5⧉
2
17 = 3 * 5 + 2
Quotient⧉
3
floor(17 / 5) = 3
Modular Inverse⧉
3
17 * 3 = 1 (mod 5)
Euler's Totient phi(n)⧉
4
4 integers in [1, 5] are coprime to 5
GCD(a, n)⧉
1
17 and 5 are coprime
17^3 mod 5⧉
3
Modular exponentiation (square-and-multiply)
Fermat's Test⧉
Passes
17^4 mod 5 = 1 (Fermat verified)
Remainder Position (0 to 4)
2 / 4
Congruence Class [2] (mod 5)
-13-8-32712172227...
All integers congruent to 2 (mod 5)
Multiplication Table (mod 12)
2-15 for readability
| * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 2 | 0 | 2 | 4 | 6 | 8 | 10 | 0 | 2 | 4 | 6 | 8 | 10 |
| 3 | 0 | 3 | 6 | 9 | 0 | 3 | 6 | 9 | 0 | 3 | 6 | 9 |
| 4 | 0 | 4 | 8 | 0 | 4 | 8 | 0 | 4 | 8 | 0 | 4 | 8 |
| 5 | 0 | 5 | 10 | 3 | 8 | 1 | 6 | 11 | 4 | 9 | 2 | 7 |
| 6 | 0 | 6 | 0 | 6 | 0 | 6 | 0 | 6 | 0 | 6 | 0 | 6 |
| 7 | 0 | 7 | 2 | 9 | 4 | 11 | 6 | 1 | 8 | 3 | 10 | 5 |
| 8 | 0 | 8 | 4 | 0 | 8 | 4 | 0 | 8 | 4 | 0 | 8 | 4 |
| 9 | 0 | 9 | 6 | 3 | 0 | 9 | 6 | 3 | 0 | 9 | 6 | 3 |
| 10 | 0 | 10 | 8 | 6 | 4 | 2 | 0 | 10 | 8 | 6 | 4 | 2 |
| 11 | 0 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Green = 1 (inverse pairs) / Red = 0 (zero divisors)
Powers of 17 mod 5
| k | 17^k | 17^k mod 5 | Trail |
|---|---|---|---|
| 0 | 1 | 1 | |
| 1 | 17 | 2 | |
| 2 | 289 | 4 | |
| 3 | 4,913 | 3 | |
| 4 | 83,521 | 1 <- order | |
| 5 | 1,419,857 | 2 | |
| 6 | 24,137,569 | 4 |
Modular Arithmetic Properties
| Property | Formula | Example with a=17, n=5 |
|---|---|---|
| Remainder | a mod n | 2 |
| Addition | (a + a) mod n | 4 |
| Multiplication | (a * a) mod n | 4 |
| Additive inverse | (n - a mod n) mod n | 3 |
| Totient identity | a^phi(n) mod n (if coprime) | 1 |
Planning notes, formulas, and examples
About the Modular Arithmetic Calculator
The Modular Arithmetic Calculator computes a mod n (the remainder when a is divided by n) and performs modular addition, subtraction, and multiplication. Modular arithmetic is "clock arithmetic" — numbers wrap around after reaching the modulus.
Modular arithmetic is foundational in number theory, cryptography (RSA, Diffie-Hellman), computer science (hash functions, checksums), and everyday life (12-hour clocks, days of the week).
This calculator handles positive and negative numbers, always returning a non-negative result. It also performs modular exponentiation (a^b mod n), which is crucial in public-key cryptography.
When This Page Helps
Modular arithmetic with large numbers, especially exponentiation, is computationally intensive. This calculator handles all operations including modular exponentiation.
How to Use the Inputs
- Enter the number a.
- Enter the modulus n.
- View a mod n (the remainder).
- See the quotient and verify: a = quotient × n + remainder.
- For modular exponentiation, enter the exponent b.
Formula used
a mod n = a − n × floor(a/n)
Properties:
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a × b) mod n = ((a mod n) × (b mod n)) mod nExample Calculation
Result: 2
17 mod 5: 17 = 3 × 5 + 2. The remainder is 2. Equivalently, 17 and 2 are congruent modulo 5.
Tips & Best Practices
- a mod n always gives a result between 0 and n−1.
- Negative numbers: (−7) mod 5 = 3, because −7 = (−2)×5 + 3.
- Modular arithmetic preserves addition and multiplication.
- The 12-hour clock is mod 12 arithmetic.
- ISBN check digits use mod 11 or mod 10 arithmetic.
- RSA encryption uses modular exponentiation with very large numbers.
Modular Arithmetic in Cryptography
RSA encryption computes c = m^e mod n for encryption and m = c^d mod n for decryption. The security relies on the difficulty of factoring n into its prime components.
Clock Arithmetic
A 12-hour clock is mod 12: 10 o'clock + 5 hours = 3 o'clock. Days of the week cycle with mod 7. Calendar calculations routinely use modular arithmetic.
Modular Inverse
a has a modular inverse mod n if gcd(a, n) = 1. The inverse a⁻¹ satisfies a × a⁻¹ ≡ 1 (mod n). Extended Euclidean algorithm computes it.
Professionals in data science, engineering, and finance apply these calculations daily to model complex systems and test analytical hypotheses.
Sources & Methodology
Last updated:
Frequently Asked Questions
Modular arithmetic is a system where numbers "wrap around" after reaching a certain value (the modulus). It is like clock arithmetic: 10 + 5 = 3 on a 12-hour clock.
a mod n gives the remainder when a is divided by n. For example, 17 mod 5 = 2 because 17 = 3×5 + 2.
This calculator always returns a non-negative result. For −7 mod 5, the answer is 3 (not −2), because −7 = (−2)×5 + 3.
Computing a^b mod n efficiently, even for very large a, b, and n. It is the core operation in RSA encryption and can be computed using the square-and-multiply algorithm.
a ≡ b (mod n) means a and b have the same remainder when divided by n. For example, 17 ≡ 2 (mod 5).
Hash tables, checksums, circular buffers, random number generators, and cryptographic algorithms all rely on modular arithmetic. Sharing these results with team members or stakeholders promotes alignment and supports more informed decision-making across the organization.
More in this topic
Prime Number Checker
Check if any number is prime using trial division up to its square root. Determine primality and see the smallest factor if composite.
Absolute Value Calculator
Calculate the absolute value of any number. Find the distance from zero, solve absolute value equations, and understand |x| notation.