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.
Absolute value in : ; exactly when ; ; ; ; and exactly when
Statement
Let and let be as in The absolute value of an integer. Then
- ;
- if and only if ;
- ;
- ;
- ;
- if and only if .
Facts & Assumptions
Given: Integers , and the absolute value of The absolute value of an integer.
is a commutative ring: addition and multiplication are associative and commutative, , , multiplication distributes over addition, and every has an additive inverse ; we write for . Its standard consequences are used freely: , , , and (The integers form a commutative ring, Arithmetic on the integers).
The order on is total, antisymmetric and transitive, is compatible with addition ( implies ), and positives are closed under multiplication ( and imply ); means together with (The integers form a totally ordered ring, Order on the integers).
when , and when ; the second clause covers as well, since (The absolute value of an integer).
Proof
For every : if and only if , and if and only if . Adding to gives , and adding to gives back ; the second equivalence is the same computation with and interchanged, using .
If and then . If or then ; otherwise and , so because positives are closed under multiplication.
By totality, at least one of and holds, and correspondingly or ; this is the case split used throughout, and it is exhaustive.
Case : .
Case : , and by step 1.1, so .
If then by the first clause. Conversely, if then in the case we get , and in the case we get , whence . This is claim 2.
Claim 3. If then by step 1.1, so . If then by step 1.1, so .
Claim 4, case and : by step 1.2, so .
Claim 4, case and : by step 1.1, so by step 1.2, hence by step 1.1 again; therefore .
Claim 4, case and : the same computation with the factors interchanged, using commutativity of multiplication, gives .
Claim 4, case and : and by step 1.1, so by step 1.2, hence .
Claim 5. If then , so ; and by step 1.1, so by transitivity. If then and by step 1.1, so by transitivity; and .
Claim 6, from right to left: suppose . If then . If then , and adding to gives , that is .
Claim 1 holds: in both cases.
The four sign combinations of step 2.4 to step 2.7 exhaust the possibilities by totality, so claim 4 holds for all .
Claim 6, from left to right: suppose . Then by step 2.8 and transitivity. Adding to gives , and by step 2.8, so by transitivity.
Every one of the six claims is now established, claim 6 by its two halves.
Remarks
-
Claim 6 is stated with on both sides deliberately, and the strict form follows from it: holds exactly when . From left to right, and by claim 5. From right to left, gives by claim 6, and is impossible, since is or and both and are excluded by the two strict inequalities.
-
The list does not include the triangle inequality, which is not used anywhere on this page. What the proofs below actually reach for is claim 1, claim 2, claim 4 and the bound of claim 5; claim 3 is used once, in the identification of the associate classes, and claim 6 is recorded for completeness rather than because something later needs it.
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 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
- 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: 37 results over 15 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)