Modular Arithmetic

Introduction

Modular arithmetic: arithmetic system with integers wrapping around a fixed modulus. Central to discrete mathematics and number theory. Mechanism: integers taken modulo n yield finite residue classes. Applications: cryptography, computer science, coding theory, algorithms, and more. Enables simplification of problems involving divisibility, cyclic structures, and periodicity.

"Modular arithmetic is the arithmetic of remainders, fundamental both in theory and in practical computation." -- Kenneth H. Rosen

Definition and Notation

Modulus and Congruence

Definition: For integer n > 1, two integers a and b are congruent modulo n if n divides (a - b). Notation: a ≡ b (mod n). Meaning: a and b leave the same remainder when divided by n.

Equivalence Relation

Congruence modulo n forms an equivalence relation: reflexive, symmetric, transitive. Partitions integers into equivalence classes called residue classes.

Residue Notation

Canonical representative: usually the least non-negative integer in the class. Residue set: {0, 1, 2, ..., n-1}.

Basic Properties

Closure

Modular addition, subtraction, multiplication closed in residue classes modulo n.

Compatibility with 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)

Reduction

Any integer can be replaced by its residue modulo n without changing congruence relations.

Congruence Relations

Definition Recap

a ≡ b (mod n) ⇔ n | (a - b). Fundamental to modular arithmetic.

Properties

Equivalence relation properties: reflexivity, symmetry, transitivity. Enables partitioning into residue classes.

Solving Congruences

Linear congruences of form ax ≡ b (mod n): solution exists iff gcd(a, n) divides b. Extended Euclidean algorithm used for solutions.

Residue Classes and Systems

Residue Class Definition

Set of integers congruent to a modulo n. Denoted [a]_n or simply a mod n.

Complete Residue System

Set of n integers, each representing a distinct residue class modulo n. Example: {0, 1, 2, ..., n-1}.

Reduced Residue System

Subset of complete system containing integers coprime to n. Size given by Euler's totient function φ(n).

Modular Arithmetic Operations

Addition and Subtraction

(a + b) mod n = remainder of (a + b)/n. Similarly for subtraction.

Multiplication

(a × b) mod n = remainder of product divided by n.

Exponentiation

Repeated multiplication modulo n. Efficient via modular exponentiation algorithms.

Applications

Cryptography

Modular arithmetic underpins RSA, Diffie-Hellman, Elliptic Curve Cryptography. Enables key exchange, encryption, signatures.

Computer Science

Hash functions, random number generation, cyclic data structures, checksums use modular arithmetic for wrap-around behavior.

Number Theory

Solving Diophantine equations, primality testing, factorization algorithms rely on modular arithmetic.

Modular Inverses and Division

Definition

Modular inverse of a modulo n is an integer x such that ax ≡ 1 (mod n).

Existence Criteria

Inverse exists iff gcd(a, n) = 1 (a and n coprime).

Computation

Extended Euclidean algorithm computes inverses efficiently.

function modInverse(a, n): (g, x, _) = extendedGCD(a, n) if g ≠ 1: return "No inverse" else: return x mod n

Chinese Remainder Theorem

Statement

System of simultaneous congruences with pairwise coprime moduli has unique solution modulo product of moduli.

Implications

Enables decomposition of modular problems into smaller moduli. Used in cryptography and computational number theory.

Example

Solve:x ≡ 2 (mod 3)x ≡ 3 (mod 5)x ≡ 2 (mod 7)Solution: x ≡ 23 (mod 105)

Computational Algorithms

Modular Exponentiation

Fast exponentiation method reducing intermediate results modulo n. Complexity: O(log e) for a^e mod n.

Extended Euclidean Algorithm

Computes gcd and modular inverses. Essential for solving linear congruences.

Algorithm Example: Modular Exponentiation

function modExp(base, exponent, modulus): result = 1 base = base mod modulus while exponent > 0: if exponent mod 2 == 1: result = (result × base) mod modulus exponent = exponent >> 1 base = (base × base) mod modulus return result

Advanced Topics

Euler's Theorem

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

Fermat's Little Theorem

Special case for prime modulus p: a^(p-1) ≡ 1 (mod p) for a not divisible by p.

Quadratic Residues

Study of solutions to x^2 ≡ a (mod n). Related to Legendre and Jacobi symbols.

References

• K. H. Rosen, Elementary Number Theory and Its Applications, 6th ed., Pearson, 2010, pp. 45-89.
• R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, 1994, pp. 12-58.
• J. H. Silverman, A Friendly Introduction to Number Theory, 4th ed., Pearson, 2013, pp. 101-140.
• T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976, pp. 22-70.
• D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997, pp. 220-270.