Alphabeta Math

Primes, Euclid's Lemma and the Fundamental Theorem of Arithmetic

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.

✓ 16 results · all verified · 9 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 7 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
Number Theory
Real Analysis
Set Theory
2 · Logical flowchart

3 · Items

Definition

Prime and composite integers: p is prime when p > 1 and its only positive divisors are 1 and p

Lemma

For a prime p and any integer a, gcd(p,a) is p when p ∣ a and 1 otherwise; so p ∤ a makes p and a coprime

Theorem

Euclid's lemma: if p is prime and p ∣ ab then p ∣ a or p ∣ b

Corollary

For an integer p > 1: p is prime if and only if, for all integers a and b, p ∣ ab implies p ∣ a or p ∣ b

Corollary

If a prime p divides a finite product ∏_i<n aᵢ of integers then p ∣ aᵢ for some i < n; at n = 0 the product is 1 and the hypothesis cannot hold

Lemma

Every integer n > 1 has a prime divisor; indeed the least divisor of n that exceeds 1 is prime

Theorem

Every integer n ≥ 1 is a finite product of primes: there are r ∈ ℕ and a list p : r → ℤ of primes with n = ∏_i<r pᵢ, the case n = 1 being the empty product

Theorem

The fundamental theorem of arithmetic: every integer n ≥ 1 is a product of primes, and the factorisation is unique up to order — if ∏_i<r pᵢ = ∏_j<s qⱼ with every pᵢ and qⱼ prime, then r = s and qᵢ = p_π(i) for some π ∈ Sym(r)

Corollary

Every nonzero integer n is u ∏_i<r pᵢ with u ∈ {1,-1} and every pᵢ prime; u and r are determined by n, and the list is determined up to a permutation

Theorem

Euclid's theorem: for every n ∈ ℕ and every list p : n → ℤ of primes there is a prime not among p₀, …, pₙ₋₁; consequently the set of primes is not finite

Definition

The p-adic valuation vₚ(a) of a nonzero integer: the greatest k ∈ ℕ with pᵏ ∣ a

Lemma

For a prime p and a nonzero integer a: p^vₚ(a) ∣ a and p^vₚ(a)+1 ∤ a; pᵏ ∣ a holds exactly for k ≤ vₚ(a); vₚ(a) ≥ 1 exactly when p ∣ a; vₚ(1) = vₚ(-1) = 0; and vₚ(p) = 1

Lemma

vₚ(ab) = vₚ(a) + vₚ(b) for nonzero integers a, b, and vₚ(a+b) ≥ min{vₚ(a), vₚ(b)} whenever a, b and a+b are all nonzero

Theorem

For n ≥ 1 and any injective list p : r → ℤ of primes containing every prime divisor of n, one has n = ∏_i<r pᵢ^ v_pᵢ(n); the exponents are determined by n, and v_q(n) = 0 for every prime q outside the list

Lemma

For positive integers a and b: a ∣ b if and only if vₚ(a) ≤ vₚ(b) for every prime p

Theorem

For positive integers a and b and every prime p: vₚ(gcd(a,b)) = min{vₚ(a), vₚ(b)} and vₚ(lcm(a,b)) = max{vₚ(a), vₚ(b)}; so the exponent-wise greatest common divisor is the gcd of the divisibility page and not a second notion

Lemma

The p-adic valuation extends to the nonzero rationals by vₚ(a/b) := vₚ(a) - vₚ(b) ∈ ℤ, independently of the representation; it satisfies vₚ(xy) = vₚ(x) + vₚ(y), and vₚ(x+y) ≥ min{vₚ(x), vₚ(y)} whenever x, y and x+y are nonzero

Corollary

A rational root of xᵏ = m is an integer: if k ≥ 1, m ∈ ℤ, x ∈ ℚ and xᵏ is the image of m, then x is the image of an integer

Sources