Alphabeta Math

Congruences, the Integers Modulo n and the Chinese Remainder Theorem

About this page
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 19 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 19 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
Combinatorics
Number Theory
Real Analysis
Set Theory
2 · Logical flowchart

3 · Items

Definition

Congruence modulo an integer: a≡ b (mod n) when n∣(a-b), including the moduli 0 and 1

Lemma

Congruence modulo every integer is an equivalence relation on ℤ

Lemma

Congruent integers may be added, subtracted and multiplied: representative changes preserve both arithmetic operations

Definition

The congruence class [a]ₙ and the quotient set ℤ/n

Theorem

For n≥ 1, every class in ℤ/n has one representative r with 0≤ r<n, so |ℤ/n|=n; while ℤ/0 is in bijection with ℤ

Definition

Addition and multiplication on ℤ/n by [a]ₙ+[b]ₙ=[a+b]ₙ and [a]ₙ[b]ₙ=[ab]ₙ

Theorem

For every natural n, (ℤ/n,+) is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold

Definition

The unit group (ℤ/n)^× and Euler's totient φ(n)=|(ℤ/n)^×| for n≥1

Theorem

For n≥1, [a]ₙ is a unit if and only if gcd(a,n)=1

Corollary

φ(1)=1, and φ(p)=p-1 for every prime p

Lemma

For a prime p and k≥1, multiplication by p bijects the standard representatives modulo pᵏ⁻¹ with the representatives modulo pᵏ divisible by p

Theorem

For a prime p and k≥1, φ(pᵏ)=pᵏ-pᵏ⁻¹

Lemma

If n≥1, d=gcd(a,n) and d∣ b, then ax≡ b (mod n) reduces to a congruence with coprime coefficient modulo n/d

Theorem

For n≥1, ax≡ b (mod n) is solvable exactly when gcd(a,n)∣ b, and then has exactly gcd(a,n) solution classes modulo n

Lemma

For a finite pairwise-coprime list of positive integers, the product divides every common multiple, and each initial product is coprime to every remaining modulus

Lemma

For coprime positive m,n, every pair of residue classes modulo m and n has a unique simultaneous class modulo mn

Theorem

Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication

Corollary

Euler's totient is multiplicative: gcd(m,n)=1 implies φ(mn)=φ(m)φ(n) for positive m,n

Theorem

Euler's product formula φ(n)=n∏_p∣ n(1-1/p)=∏_pᵏ∥ n(pᵏ-pᵏ⁻¹) for n≥1, stated through a finite injective list of its prime divisors

Theorem

For every positive integer n, ∑_d∣ n, d>0φ(d)=n

Theorem

For every prime p, the two operations on ℤ/p make it a field

Lemma

In (ℤ/p)^×, inversion pairs every class except [1]ₚ and [-1]ₚ, which are the only self-inverse classes

Theorem

Wilson's theorem: for every prime p, (p-1)!≡-1 (mod p)

Sources