Alphabeta MathHow 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.
Every integer has a prime divisor; indeed the least divisor of that exceeds is prime
Statement
Let with , and put
(Divisibility in : when for some integer ). Then is nonempty and has a least element , and is prime (Prime and composite integers: is prime when and its only positive divisors are and ). In particular every integer greater than has a prime divisor.
Facts & Assumptions
Given: An integer with , and the set above.
Divisibility is reflexive and transitive (Divisibility is reflexive and transitive on , and is linear: if and then for all integers ; also implies , and ).
A nonempty set of integers with a lower bound has a unique least element (A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element).
is prime exactly when and every positive divisor of is or (Prime and composite integers: is prime when and its only positive divisors are and ).
The order on is total, antisymmetric and transitive and is compatible with addition; means together with (The integers form a totally ordered ring, Order on the integers).
The embedding is injective, preserves addition and order, and has as image exactly the nonnegative integers, with and (The naturals embed in the integers).
On : for every , since (Order on the natural numbers); exactly when (Discreteness: is the immediate successor); and (The natural numbers (von Neumann)).
Proof
in : lies in the image of , so , and because is injective and .
Discreteness: if and then . Indeed , so for some ; since ; hence in , so , and applying the order-preserving gives .
, since and ; so is nonempty.
is a lower bound for : every satisfies , hence .
By [L3] the set has a unique least element : that is, , , and for every .
and , so and , and .
Let be a positive divisor of with . Then by step 1.2, and , so .
Also and , so by transitivity; with this gives , hence .
On the other hand with gives , and because ; so . With step 4.1 and antisymmetry, .
So every positive divisor of is or , and : is prime. Since , the integer has a prime divisor.
Remarks
-
Well-ordering is used through the integer bridge, not directly. The well-ordering principle gives a least element of a nonempty subset of , whereas is a set of integers. A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element is the published lemma that crosses that gap, and its Statement covers the lower-bound case explicitly, so it is what this proof cites.
-
The bound is genuinely the least divisor above , not merely some prime divisor. That is what makes the argument work: minimality is the only reason has no proper divisor above , since any such divisor would divide as well and be smaller.
-
The hypothesis cannot be dropped. At the set is empty, since forces or ( is a commutative monoid whose group of units is ; equivalently holds exactly for and ) and neither exceeds ; so has no prime divisor, which is exactly why the empty product is the right factorisation of in Every integer is a finite product of primes: there are and a list of primes with , the case being the empty product. At every integer divides , so is the whole set of integers greater than ; it does have a least element, namely , but a statement about the divisors of is of no use below and the lemma is not claimed there.
Depends on
- Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$
- Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$
- Divisibility is reflexive and transitive on $\mathbb{Z}$, and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$; also $d \mid a$ implies $d \mid ac$, $-d \mid a$ and $d \mid -a$
- If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$; hence the set of divisors of a nonzero integer is bounded above by $|a|$
- A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element
- The absolute value $|a|$ of an integer
- Absolute value in $\mathbb{Z}$: $|a| \ge 0$; $|a| = 0$ exactly when $a = 0$; $|-a| = |a|$; $|ab| = |a|\,|b|$; $-|a| \le a \le |a|$; and $|a| \le c$ exactly when $-c \le a \le c$
- Order on the integers
- The integers form a totally ordered ring
- The natural numbers $\mathbb{N}$ (von Neumann)
- Order on the natural numbers
- The naturals embed in the integers
- Discreteness: $\sigma(n)$ is the immediate successor
Used by
- 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 Corollary
- Converse of Lagrange for finite abelian groups: every divisor occurs as a subgroup order Corollary
- Squarefree sums of two squares Corollary
- There are infinitely many primes congruent to 1 modulo 3 Corollary
- In the multiplicative monoid H = {1, 4, 7, 10, …} of positive integers one more than a multiple of 3, the element 100 has two genuinely different factorisations into irreducibles, 4 · 25 and 10 · 10 Counterexample
- FALSE: for every finite list p₀, …, pₙ₋₁ of distinct primes, p₀ ⋯ pₙ₋₁ + 1 is prime False statement
- Coprime primitively represented factors have a primitive product representation 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 positive integers a and b: a ∣ b if and only if vₚ(a) ≤ vₚ(b) for every prime p Lemma
- Powers of primes congruent to 1 modulo 4 have primitive two-square representations Lemma
- Representations of an odd integer correspond to representations of twice that integer Proposition
- The Jacobi symbol is well defined on numerator residue classes Proposition
- Φ_pʳ(t)=∑_k<pt^kpʳ⁻¹, and Φ_pʳ(t+1) is Eisenstein at p Proposition
- A finite group is solvable if and only if all its composition factors are cyclic of prime order 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 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
- 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
- For every n≥1 there are infinitely many primes p with p≡1 (mod n) 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 Theorem
- Lagrange's four-square theorem: every nonnegative integer is a sum of four integer squares Theorem
Dependency tree · two levels
40 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Fundamental theorem of arithmetic (Wikipedia) (standard reference, not scraped)
- Janssen and Lindsey, Rings with Inquiry: Primes and Factorization (standard reference, not scraped)