What does the notation a congruent to b mod n mean?

It means n divides the difference a minus b, equivalently a and b leave the same remainder on division by n.

Why does RSA rely on Euler's theorem?

RSA encryption and decryption are modular exponentiations whose composition returns the original message precisely because Euler's theorem guarantees the relevant exponent acts as the identity modulo the key.

Congruences and Modular Arithmetic

Modular arithmetic studies integers up to divisibility by a fixed modulus, turning the integers into the finite ring Z/nZ and giving number theory its most flexible computational tool.

Definition

Two integers are congruent modulo n if their difference is divisible by n. Modular arithmetic is the arithmetic of the resulting residue classes, which form the commutative ring Z/nZ.

Scope

This topic covers the congruence relation and residue classes, arithmetic in Z/nZ, linear and polynomial congruences, the Chinese remainder theorem, Fermat's little theorem and Euler's theorem, the structure of the unit group, primitive roots, and the order of elements. It is the language in which most of elementary and computational number theory is expressed.

Core questions

When does a linear congruence ax congruent to b mod n have solutions, and how many?
How does the Chinese remainder theorem decompose Z/nZ into a product over prime-power moduli?
Why do Fermat's little theorem and Euler's theorem hold, and what do they say about the order of units?
For which moduli does a primitive root exist, making the unit group cyclic?

Key theories

Chinese remainder theorem: If the moduli are pairwise coprime, a system of simultaneous congruences has a unique solution modulo the product; equivalently Z/nZ is isomorphic to the product of Z over its prime-power factors.
Fermat's little theorem and Euler's theorem: For a coprime to n, a raised to the totient of n is congruent to one modulo n; the prime case (Fermat) underlies primality tests and the general case underlies RSA.
Primitive roots and group structure: The multiplicative group of units mod n is cyclic exactly when n is one, two, four, an odd prime power, or twice one; a generator is a primitive root, giving a discrete logarithm.

Clinical relevance

Modular arithmetic is the computational engine of cryptography (RSA, Diffie-Hellman, elliptic-curve schemes), checksums and error detection (ISBN, hash functions), and pseudorandom number generation, making it the most widely deployed part of number theory.

History

Although special cases appear in ancient Chinese and Indian mathematics (the remainder problem named for the former), the systematic theory of congruences was introduced by Gauss in the Disquisitiones Arithmeticae (1801), where he established the notation and proved the central structural results.

Key figures

Carl Friedrich Gauss
Pierre de Fermat
Leonhard Euler

Seminal works

irelandRosen1990

Frequently asked questions

What does the notation a congruent to b mod n mean?: It means n divides the difference a minus b, equivalently a and b leave the same remainder on division by n.
Why does RSA rely on Euler's theorem?: RSA encryption and decryption are modular exponentiations whose composition returns the original message precisely because Euler's theorem guarantees the relevant exponent acts as the identity modulo the key.