Modular Arithmetic Calculator

Modular Arithmetic Fundamentals

Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value called the modulus.

Basic Concepts

Modular Operations

Basic Properties

• Addition: (a + b) mod m = ((a mod m) + (b mod m)) mod m
• Subtraction: (a - b) mod m = ((a mod m) - (b mod m) + m) mod m
• Multiplication: (a × b) mod m = ((a mod m) × (b mod m)) mod m
• Exponentiation: (a^b) mod m can be computed efficiently using repeated squaring

Modular Inverse

The modular inverse of a modulo m is a number x such that (a × x) ≡ 1 (mod m).

• Exists if and only if gcd(a, m) = 1
• Can be found using the Extended Euclidean Algorithm
• Unique modulo m when it exists

Advanced Topics

Chinese Remainder Theorem

If m₁, m₂, ..., mₖ are pairwise coprime, then the system of congruences:

• x ≡ a₁ (mod m₁)
• x ≡ a₂ (mod m₂)
• ...
• x ≡ aₖ (mod mₖ)

has a unique solution modulo M = m₁ × m₂ × ... × mₖ.

Euler's Theorem

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.

Fermat's Little Theorem

If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p).

Applications

• Cryptography: RSA encryption, Diffie-Hellman key exchange
• Computer Science: Hash functions, pseudo-random number generation
• Number Theory: Solving Diophantine equations, primality testing
• Coding Theory: Error-correcting codes, checksums
• Algebra: Group theory, ring theory
• Calendar Calculations: Day of week calculations

Algorithms

Fast Modular Exponentiation

Computes a^b mod m efficiently using binary representation of the exponent:

1. Initialize result = 1
2. While b > 0:
3.   If b is odd: result = (result × a) mod m
4.   a = (a × a) mod m
5.   b = b ÷ 2
6. Return result

Extended Euclidean Algorithm

Finds integers x and y such that ax + by = gcd(a, b):

1. If b = 0: return (a, 1, 0)
2. Otherwise: (g, x₁, y₁) = extgcd(b, a mod b)
3. Return (g, y₁, x₁ - (a ÷ b) × y₁)

Common Patterns

• Clock Arithmetic: 12-hour and 24-hour time systems
• Periodic Functions: Sine, cosine with period 2π
• Cyclic Groups: Rotations, symmetries
• Hash Tables: Index calculation with modular arithmetic
• Computer Graphics: Texture wrapping, angle calculations