Modular Arithmetic Calculator

Calculate modular arithmetic operations including modulo, modular inverse, and modular exponentiation for cryptography and number theory.

What is Modular Arithmetic?

Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value (the modulus). It's often described as "clock arithmetic."

The expression a mod m gives the remainder when a is divided by m. For example, 17 mod 5 = 2 because 17 = 3 × 5 + 2.

Basic Operations

Modular arithmetic supports all basic operations:

• Addition: (a + b) mod m = ((a mod m) + (b mod m)) mod m
• Subtraction: (a - b) mod m = ((a mod m) - (b mod m)) mod m
• Multiplication: (a × b) mod m = ((a mod m) × (b mod m)) mod m

Modular Exponentiation

Modular exponentiation computes a^b mod m efficiently using the square-and-multiply algorithm. This is crucial for RSA encryption.

For example, 3^5 mod 7 = 243 mod 7 = 5.

Modular Inverse

The modular inverse of a modulo m is a number x such that:

a × x ≡ 1 (mod m)

A modular inverse exists only when a and m are coprime (gcd(a, m) = 1). It's calculated using the Extended Euclidean Algorithm.

For example, the inverse of 3 mod 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7).

Applications of Modular Arithmetic

Modular arithmetic is fundamental in many areas:

• Cryptography: RSA encryption, Diffie-Hellman key exchange
• Computer Science: Hash functions, checksums, random number generation
• Number Theory: Prime testing, factorization algorithms
• Coding Theory: Error detection and correction codes
• Music Theory: Twelve-tone technique and pitch class
• Calendar Calculations: Day of week algorithms