Moduloimisen

Moduloimisen, or modular arithmetic, is a branch of number theory that studies integers through their residues modulo a fixed positive integer n. For integers a and n with n > 0, the remainder r = a mod n is the unique integer with 0 ≤ r < n such that a ≡ r (mod n). Equivalently, a ≡ b (mod n) means n divides a−b. The set of residues modulo n forms a ring Z/nZ under addition and multiplication.

Operations are performed modulo n: (a ± b) mod n and (a × b) mod n. Congruence respects these operations: if a ≡ b (mod n) and c ≡ d (mod n), then a ± c ≡ b ± d (mod n) and a × c ≡ b × d (mod n). Negative residues can be converted to a standard representative in 0,…,n−1.

Inverses exist with the caveat: an integer a has a multiplicative inverse modulo n if and only if gcd(a, n) = 1. The inverse is found via the extended Euclidean algorithm. Modular equations a × x ≡ b (mod n) may have zero, one, or multiple solutions depending on gcd(a, n).

Applications include cryptography (RSA and elliptic-curve cryptography rely on modular exponentiation), computer algorithms, hashing, and clock arithmetic. A common operation is modular exponentiation, computing a^k mod n efficiently via exponentiation by squaring.

Historically, modular arithmetic was developed in the 19th century, with significant contributions from Gauss. Today it provides the theoretical foundation for many areas of mathematics and practical systems such as digital security and error detection.