Arithmetic on the integers

Depends on

• The integers as equivalence classes of pairs of naturals
• Addition of natural numbers
• Multiplication of natural numbers

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
• 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 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 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 Corollary
• If d = gcd(a,b) is nonzero then a/d and b/d are coprime Corollary
• The extended Euclidean algorithm: the same descent produces integers x, y with ax + by = gcd(a,b), so Bézout coefficients are computed and not merely shown to exist Corollary
• 2ℤ is closed under addition, negation and multiplication and is not a subring of ℤ, because it does not contain 1 Counterexample
• 6 ∣ 4 · 9 while 6 ∤ 4 and 6 ∤ 9: dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails Counterexample
• A nonempty subset of a group closed under the operation need not be a subgroup: the nonnegative integers inside (ℤ, +) Counterexample
• If 1 were admitted as a prime, uniqueness would fail: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3, lists of different lengths that no permutation matches Counterexample
• 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
• The common divisors of (0,0) are all of ℤ and have no greatest element in the order of ℤ, so gcd(0,0) cannot be defined as a maximum and is fixed by convention Counterexample
• The map n ↦ (n,0) from ℤ to ℤ × ℤ preserves addition and multiplication and does not preserve 1, so the clause f(1) = 1 is not redundant Counterexample
• Common multiple, and the least common multiple lcm(a,b), taken to be 0 when a = 0 or b = 0 Definition
• Divisibility in ℤ: d ∣ a when a = dq for some integer q Definition
• Integer powers aᵐ Definition
• Powers gⁿ: natural exponents in a monoid and integer exponents in a group, with g⁰ = e Definition
• Prime and composite integers: p is prime when p > 1 and its only positive divisors are 1 and p Definition
• The absolute value |a| of an integer Definition
• The formal Laurent series ℝ((t⁻¹)): support bounded below, valuation, leading coefficient Definition
• The p-adic valuation vₚ(a) of a nonzero integer: the greatest k ∈ ℕ with pᵏ ∣ a Definition
• (ℤ, +) is an abelian group, (ℤ, ·) is a commutative monoid that is not a group, and its group of units is {1, -1} Example
• 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
• 360 = 2³ · 3² · 5 and 84 = 2² · 3 · 7, with gcd(360,84) = 12 and lcm(360,84) = 2520 read off the exponents Example
• A product of two rings with 1 ≠ 0 always has zero divisors: (1,0)(0,1) = (0,0) in ℤ × ℤ, so a product of integral domains is never an integral domain Example
• ax + by = c has an integer solution exactly when gcd(a,b) ∣ c: 6x + 15y = 9 is solvable and 6x + 15y = 7 is not Example
• Bézout coefficients are not unique: 1071 · (-3) + 462 · 7 = 21 and 1071 · 19 + 462 · (-44) = 21, and for nonzero a, b every solution has the form (x₀ + t b/d, y₀ - t a/d) 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
• For every n ∈ ℕ there are n consecutive composite integers: with N := ∏_j<n(j+2), each of N+2, …, N+n+1 is composite Example
• For n ≥ 1 the congruence classes modulo n form an abelian group (ℤ/n, +) of order n, generated by the class of 1 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
• nℤ is a subgroup of (ℤ, +) for every n ∈ ℤ, and every subgroup of (ℤ, +) has this form Example
• ℤ is a commutative ring and an ordered ring, the published construction being an instance of the general definitions Example
• ℤ is an integral domain of characteristic 0 whose group of units is {1,-1}, so it is not a field: 2 is nonzero and not invertible Example
• ℤ sits inside ℚ as a subring that is not a subfield, so the inverse-closure clause of the subfield definition is doing work Example
• FALSE: every Fermat number 2^2ⁿ + 1 is prime False statement

…and 44 more results.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 14 results over 9 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

• T. Tao, Analysis I, 3rd ed., §4.1 (standard reference, not scraped)
• Integer — construction from pairs of naturals (Wikipedia) (standard reference, not scraped)