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.
The absolute value of an integer
Definition
Let (The integers as equivalence classes of pairs of naturals). The absolute value of is
where is the order of Order on the integers and is the additive inverse supplied by The integers form a commutative ring for the operations of Arithmetic on the integers.
Why the two clauses define a function. The order on is total and antisymmetric (The integers form a totally ordered ring), so for each exactly one of and holds: totality gives at least one of and , and if both hold then by antisymmetry, in which case and fails, since means together with . The two clauses therefore never both apply and never both fail, and is a single element of because additive inverses are unique in a commutative ring: if and then .
At the boundary, by the first clause, and the second clause also gives whenever : for that is the definition, and for both readings give .
Remarks
-
This is not a second notion of absolute value. The library's other absolute value, Absolute value in an ordered field, is stated for an ordered field. The structure the construction of supplies is that of a totally ordered commutative ring (The integers form a commutative ring, The integers form a totally ordered ring), and multiplicative inverses are no part of it, so Absolute value in an ordered field does not apply here and the definition above is a new object rather than a redefinition of an existing one. (That is genuinely not a field, rather than merely not presented as one, is is a commutative monoid whose group of units is ; equivalently holds exactly for and below: its only invertible elements are and .) A general form for an ordered ring would cover both cases at once, but the definition of an ordered ring comes much later in the reading order than this page, so it is not available to reach for.
-
The two agree along the embedding of in . Write for the injective, order-preserving and arithmetic-preserving map of The integers embed in the rationals. Then is the absolute value of in the sense of Absolute value in an ordered field, the check being the same case split: preserves the order and reflects it (if but not , then by totality, so , whence and by injectivity), so exactly when , and because preserves addition. Nothing on this page rests on this observation; it is recorded so that a reader meeting twice knows the two notations are consistent, and every result below is proved for from the integer definition alone.
-
Why an absolute value is load-bearing here and not a convenience. The published division algorithm Division with remainder in : for and there are unique with and is stated for a positive divisor, so every use of it below must first replace a divisor by a positive integer, and is what that replacement produces.
Depends on
Used by
- Division with remainder for any nonzero divisor: for a ∈ ℤ and b ≠ 0 there are unique q, r ∈ ℤ with a = qb + r and 0 ≤ r < |b| Corollary
- Every common divisor of a and b divides gcd(a,b); consequently d = gcd(a,b) exactly when d ≥ 0, d ∣ a, d ∣ b, and every common divisor of a and b divides d — a characterisation that holds at (a,b) = (0,0) as well 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 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 d = gcd(a,b) is nonzero then a/d and b/d are coprime Corollary
- Common divisor, and the greatest common divisor gcd(a,b), with the convention gcd(0,0) := 0 Definition
- Common multiple, and the least common multiple lcm(a,b), taken to be 0 when a = 0 or b = 0 Definition
- Coprime integers: gcd(a,b) = 1 Definition
- Prime and composite integers: p is prime when p > 1 and its only positive divisors are 1 and p Definition
- The p-adic valuation vₚ(a) of a nonzero integer: the greatest k ∈ ℕ with pᵏ ∣ a Definition
- 12ℤ + 18ℤ = 6ℤ and 12ℤ ∩ 18ℤ = 36ℤ, the arithmetic of gcd and lcm read off the subgroups of (ℤ,+) Example
- 2 is prime, and it is the only even prime: every even integer n > 2 is composite Example
- Consecutive Fibonacci numbers are coprime, and for every m ∈ ℕ the Euclidean algorithm on (Fₘ₊₃, Fₘ₊₂) takes exactly m+1 divisions, with quotient 1 in the first m of them and quotient 2 in the last Example
- Eisenstein proves xⁿ-2 irreducible over ℚ for every positive n Example
- gcd at the boundary: gcd(a,0) = |a|, gcd(0,0) = 0, and the convention gcd(0,0) = 0 is exactly what makes gcd(ca,cb) = |c|gcd(a,b) true at c = 0 Example
- gcd(1071, 462) = 21 by the Euclidean algorithm, with the back-substitution giving 21 = 7 · 462 - 3 · 1071 Example
- No rational squares to 3 or to 6, and none cubes to 2: three instances of the rational-root corollary Example
- Reduction modulo 2 proves x³+17x+391 irreducible over ℚ Example
- The integers are a Euclidean domain with Euclidean function δ(b)=|b| Example
- The polynomial x²-2 is irreducible over ℚ Example
- FALSE: For all integers a and b, gcd(a,b) · lcm(a,b) = ab False statement
- (ℤ, ·, 1) is a commutative monoid whose group of units is {1, -1}; equivalently u ∣ 1 holds exactly for u = 1 and u = -1 Lemma
- Absolute value in ℤ: |a| ≥ 0; |a| = 0 exactly when a = 0; |-a| = |a|; |ab| = |a| |b|; -|a| ≤ a ≤ |a|; and |a| ≤ c exactly when -c ≤ a ≤ c Lemma
- Every integer n > 1 has a prime divisor; indeed the least divisor of n that exceeds 1 is prime Lemma
- For integers a and b the following are equivalent: a ∣ b and b ∣ a; b = ua for a unit u; |a| = |b|. Being associates is an equivalence relation whose class of a is {a, -a} Lemma
- gcd is symmetric and unchanged by signs: gcd(a,b) = gcd(b,a) = gcd(|a|,|b|); moreover gcd(a,0) = |a|, gcd(a,1) = 1, gcd(a,a) = |a|, and gcd(a,b) ≥ 1 unless a = b = 0 Lemma
- gcd(ca, cb) = |c| gcd(a,b) for all integers a, b, c, the identity holding at c = 0 and at (a,b) = (0,0) as well Lemma
- If d ∣ a and a ≠ 0 then d ≠ 0 and |d| ≤ |a|; hence the set of divisors of a nonzero integer is bounded above by |a| Lemma
- Bézout's identity: for integers a, b not both zero, gcd(a,b) is the least positive element of { ax + by : x, y ∈ ℤ }; in particular ax + by = gcd(a,b) has an integer solution Theorem
- Every common multiple of a and b is a multiple of lcm(a,b), and gcd(a,b) · lcm(a,b) = |ab| 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 Theorem
- The Euclidean algorithm: for a ∈ ℤ and b > 0 the remainder descent from (a,b) terminates, and the last nonzero remainder is gcd(a,b) Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 36 results over 14 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Absolute value (Wikipedia) (standard reference, not scraped)