Modular Arithmetic

Introduction

Modular arithmetic is the arithmetic of remainders. Instead of working with all integers, we work with a finite set of remainders when dividing by a fixed modulus. This creates a cyclical number system where arithmetic "wraps around."

Modular arithmetic is fundamental in cryptography (RSA, Diffie-Hellman), computer science (hash functions, checksums), and pure mathematics (studying prime numbers, solving Diophantine equations). The familiar 12-hour clock is an everyday example of arithmetic modulo 12.

Congruence

We say a is congruent to b modulo n written:

a≡b*(mod(n))

if n divides a−b i.e., a−b=k*n for some integer. Equivalently, a and b have the same remainder when divided by n

Examples: 17≡2*(mod(5)) (since 17−2=15=3⋅5). Also 3≡4*(mod(7)).

Properties of Congruence

Congruence is an equivalence relation:

• Reflexive: a≡a*(mod(n))

• Symmetric: a≡b⇒b≡a

• Transitive: a≡b and b≡c⇒a≡c

Arithmetic Operations

If a≡b*(mod(n)) and c≡d*(mod(n)) then:

a+c≡b+d*(mod(n))

a−c≡b−d*(mod(n))

a⋅c≡b⋅d*(mod(n))

We can add, subtract, and multiply congruences freely. Division is more delicate—we need multiplicative inverses.

Multiplicative Inverses

The multiplicative inverse of a modulo n is an integer a(−1) such that:

a⋅a(−1)≡1*(mod(n))

An inverse exists if and only if gcd(a,n)=1 When it exists, it's unique modulo n and can be found using the extended Euclidean algorithm.

Example: Find 3(−1)*(mod(7)). We need 3*x≡1*(mod(7)). Testing: 3⋅5=15=2⋅7+1≡1. So 3(−1)≡5*(mod(7)).

The Group ℤ/nℤ

The integers modulo n form the set. Under addition, this is a group of order n.

The units (elements with multiplicative inverses) form the group (ℤ/n*ℤ)∗={a:gcd(a,n)=1} under multiplication.

Euler's Totient Function

ϕ(n) counts integers from 1 to n that are coprime to n. It equals |(ℤ/n*ℤ)∗|. For prime p: ϕ(p)=p−1

For prime power: ϕ(pk)=pk−p(k−1)=p(k−1)*(p−1)

Multiplicative property: If gcd(m,n)=1 then ϕ*(m*n)=ϕ(m)*ϕ(n)

General formula: ϕ(n)=n*(∏_p*(∣_^)(n)^)(1−1/p)

Fermat's Little Theorem

If p is prime and gcd(a,p)=1 then:

a(p−1)≡1*(mod(p))

Equivalently, for any a ap≡a*(mod(p))

This gives an easy way to compute inverses: a(−1)≡a(p−2)*(mod(p))

Euler's Theorem

Generalizes Fermat's Little Theorem. If gcd(a,n)=1 then:

aϕ(n)≡1*(mod(n))

For prime n=p we get ϕ(p)=p−1 recovering Fermat's Little Theorem.

Chinese Remainder Theorem

If (n_1),(n_2),…,(n_k) are pairwise coprime, then the system:

x≡(a_1)*(mod((n_1))),x≡(a_2)*(mod((n_2))),…,x≡(a_k)*(mod((n_k)))

has a unique solution modulo N=(n_1)*(n_2)⋯(n_k)

This means ℤ/N*ℤ≅ℤ/(n_1)*ℤ×⋯×ℤ/(n_k)*ℤ as rings.

Linear Congruences

The equation a*x≡b*(mod(n)) has a solution iff d=gcd(a,n) divides b

If solvable, there are exactly d solutions modulo. When gcd(a,n)=1 there's a unique solution: x≡a(−1)*b*(mod(n))

Modular Exponentiation

Computing ak*mod(n) efficiently uses repeated squaring (fast exponentiation):

• If k is even: ak=(a(k/2))2

• If k is odd: ak=a⋅a(k−1)

This requires only O*((log_)(k)) multiplications, essential for cryptography.

RSA Cryptography

RSA is a public-key encryption system based on modular arithmetic. Key generation:

1. Choose large primes p and q compute n=p*q

2. Compute ϕ(n)=(p−1)*(q−1)

3. Choose e coprime to ϕ(n) find d≡e(−1)*(mod(ϕ(n)))

Public key: (n,e) Private key: d

Encryption: c≡me*(mod(n)) Decryption: m≡cd*(mod(n))

Security relies on the difficulty of factoring n into p and q

Primality Testing

Fermat's test: If a(n−1)≢1*(mod(n)) for some a coprime to n then n is composite.

Passing the test doesn't guarantee primality (Carmichael numbers are exceptions). Miller-Rabin is a stronger probabilistic test used in practice.

Wilson's Theorem

p is prime if and only if:

(p−1)!≡−1*(mod(p))

This is a theoretical characterization of primes (computing factorials is too slow for practical primality testing).

Quadratic Residues

a is a quadratic residue mod p if x2≡a*(mod(p)) has a solution. Exactly half of the non-zero elements mod p are quadratic residues.

Euler's criterion: a is a QR iff a((p−1)/2)≡1*(mod(p))

Summary

Modular arithmetic works with remainders: a≡b*(mod(n)) means n|(a−b) Addition, subtraction, and multiplication preserve congruence. Division requires multiplicative inverses.

Euler's totient ϕ(n) counts units; Euler's theorem says aϕ(n)≡1 when gcd(a,n)=1 The Chinese Remainder Theorem solves systems of congruences.

RSA cryptography is built on modular exponentiation and the difficulty of factoring. Modular arithmetic is essential in computer science, cryptography, and number theory.