Integer Study Guide

📖 Core Concepts Integer (ℤ) – zero, any positive natural number, or the negation of a positive natural number. Notation – the set of all integers is written ℤ (boldface or blackboard bold). Set inclusions – ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ. Countably infinite – ℤ can be put into one‑to‑one correspondence with ℕ; its cardinality is ℵ₀. Algebraic closure – ℤ is closed under addition, subtraction, and multiplication, but not under division. Group / Monoid / Ring – (ℤ,+) is an abelian (commutative) group and cyclic (generator 1 or –1). (ℤ,·) is a commutative monoid with identity 1 (no inverses for most elements). Together they make ℤ a commutative ring with unity (the initial object in the category of rings). Integral domain – ℤ has no zero‑divisors. Not a field – only 1 and –1 have multiplicative inverses in ℤ; the smallest containing field is ℚ. Euclidean division – for any integers a, b ≠ 0, ∃ unique q, r with $$a = q\,b + r,\qquad 0 \le r < |b|.$$ Euclidean algorithm – repeatedly apply Euclidean division to find gcd(a,b). Fundamental theorem of arithmetic – every positive integer factors uniquely (up to order) into primes. Order – ℤ is a totally ordered set with no greatest or least element; the order is compatible with + and ·, making ℤ an ordered ring. Construction via pairs – represent an integer by an ordered pair of naturals \((a,b)\) (meaning “\(a-b\)”) and quotient by the relation \((a,b)\sim(c,d)\iff a+d=b+c\). --- 📌 Must Remember ℤ ⊂ ℚ ⊂ ℝ – hierarchy of number sets. Closure: +, –, × → ℤ; ÷ → may leave ℤ. Group generator: 1 (or –1) generates all of ℤ under addition. Euclidean division formula: \(a = q b + r\) with \(0 \le r < |b|\). gcd via Euclidean algorithm terminates after finitely many steps. Unique prime factorization for every \(n>0\). Integral domain ⇒ no zero‑divisors: if \(ab = 0\) then \(a=0\) or \(b=0\). ℤ is not a field – only ±1 have multiplicative inverses in ℤ. Cardinality: \(|\mathbb{Z}| = \aleph0\). --- 🔄 Key Processes Euclidean Algorithm (to compute \(\gcd(a,b)\)): Step 1: Divide larger by smaller → obtain remainder r₁. Step 2: Replace pair \((a,b)\) with \((b,r₁)\). Repeat until remainder = 0; the last non‑zero remainder is \(\gcd\). Prime Factorization: Start with smallest prime 2; divide repeatedly while remainder 0. Move to next prime (3,5,7,…) until the quotient becomes 1. Constructing an Integer from a Pair \((a,b)\): Form equivalence class \([(a,b)]\). Define addition: \((a,b)+(c,d) = (a+c,\,b+d)\). Define multiplication: \((a,b)\times(c,d) = (ac+bd,\,ad+bc)\). Define order: \((a,b) \le (c,d) \iff a+d \le b+c\). --- 🔍 Key Comparisons ℤ vs ℚ: ℤ – closed under +, –, ×; not under ÷. ℚ – closed under all four operations (field). Group (ℤ,+) vs Monoid (ℤ,·): Group: every element has an additive inverse. Monoid: has identity 1, but most elements lack multiplicative inverses. Integral domain vs Field: Integral domain: no zero‑divisors, but inverses not required. Field: every non‑zero element has a multiplicative inverse. --- ⚠️ Common Misunderstandings “Division of integers always stays in ℤ.” False; e.g., \(1 ÷ 2 = \frac12 \notin \mathbb{Z}\). “ℤ is a field because it has addition and multiplication.” Incorrect; lack of inverses (except ±1) disqualifies it. “Zero divisors exist in ℤ.” Wrong; if \(ab=0\) then at least one factor is 0. “Euclidean division works with negative divisors without adjusting the remainder range.” Remember remainder must satisfy \(0 \le r < |b|\); sign of b does not affect the range. --- 🧠 Mental Models / Intuition ℤ as the “whole number line” – think of walking left/right from 0; every step is an integer. Generator 1 – repeatedly adding 1 (or –1) reaches any integer, like climbing stairs one step at a time. Euclidean division – picture dividing a length into equal blocks (size |b|) and counting the leftover piece (remainder). Prime factorization – like breaking a LEGO structure into its indivisible bricks; order doesn’t matter, only the multiset of bricks. --- 🚩 Exceptions & Edge Cases Euclidean division when b = –1: remainder is always 0 because \(|b|=1\). Zero divisor test: only 0 can produce a zero product; any non‑zero a, b give non‑zero product. Construction via pairs: the class \([(n,0)]\) represents the natural number n; \([(0,n)]\) represents \(-n\). --- 📍 When to Use Which Use Euclidean division when you need a quotient and remainder (e.g., modular arithmetic, algorithmic gcd). Apply Euclidean algorithm to compute gcd for simplifying fractions or solving Diophantine equations. Invoke prime factorization when proving divisibility, counting divisors, or working with lcm/gcd formulas. Reference the ring/monoid structure when discussing homomorphisms into other algebraic objects (e.g., mapping ℤ → ℚ). Choose the pair construction when formally defining ℤ from ℕ in a set‑theoretic proof. --- 👀 Patterns to Recognize “Closed under …” statements always pair with the operation that stays inside ℤ (addition, subtraction, multiplication). “Not closed under division” appears alongside a counterexample like \(1 ÷ 2\). Euclidean algorithm steps always produce strictly decreasing remainders → guarantees termination. Fundamental theorem of arithmetic → whenever a problem mentions “unique factorization”, think primes. --- 🗂️ Exam Traps Distractor: “ℤ is a field because every non‑zero element has a multiplicative inverse.” – wrong; only ±1 do. Distractor: “The remainder in Euclidean division can be negative.” – false; remainder must satisfy \(0 \le r < |b|\). Distractor: “Zero is the greatest element of ℤ.” – incorrect; ℤ has no greatest or least element. Distractor: “Every integer can be written as a product of primes.” – only positive integers have the unique prime factorization; zero and negatives are handled separately (e.g., \(-1\) times a positive product). ---