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.
Divisibility is reflexive and transitive on , and is linear: if and then for all integers ; also implies , and
Statement
Let and let be divisibility (Divisibility in : when for some integer ). Then
- reflexivity: ;
- transitivity: and imply ;
- linearity: and imply ; in particular and ;
- implies ;
- implies and .
Consequently the four statements , , and are equivalent.
Facts & Assumptions
Given: Integers .
means for some ; exhibits (Divisibility in : when for some integer ).
is a commutative ring: addition and multiplication are associative and commutative, , , multiplication distributes over addition, and every has an additive inverse , with , and ; we write for (The integers form a commutative ring, Arithmetic on the integers).
Proof
Reflexivity: , so .
Transitivity: suppose and . Then by associativity, so .
Linearity: suppose and . Then by associativity, commutativity and distributivity, so .
Clause 4: suppose . Then , so .
Clause 5: suppose . Then , so ; and , so .
The two special cases in clause 3: taking gives , and taking , gives .
The four equivalent forms: clause 5 gives and ; applying each to in place of , or to in place of , and using , gives the reverse implications, so all four statements are equivalent.
Clauses 1 to 5 and the two consequences are established.
Remarks
-
Linearity is the workhorse of the whole page. Every later argument that a common divisor of and divides some combination of them — Bézout's identity, the Euclidean step, the coprimality criterion — is clause 3 applied once.
-
Divisibility ignores signs, and that is why can be normalised. Clause 5 says the divisors of and of are the same set, so holds exactly when , whichever of the two values takes (The absolute value of an integer). That is the observation behind in is symmetric and unchanged by signs: ; moreover , , , and unless .
Depends on
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
- 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
- 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
- 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
- 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
- Common multiple, and the least common multiple lcm(a,b), taken to be 0 when a = 0 or b = 0 Definition
- Prime and composite integers: p is prime when p > 1 and its only positive divisors are 1 and p Definition
- The divisibility poset of positive integers 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
- 360 = 2³ · 3² · 5 and 84 = 2² · 3 · 7, with gcd(360,84) = 12 and lcm(360,84) = 2520 read off the exponents 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
- 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
- FALSE: every Fermat number 2^2ⁿ + 1 is prime False statement
- FALSE: For all integers a and b, gcd(a,b) · lcm(a,b) = ab False statement
- FALSE: for every finite list p₀, …, pₙ₋₁ of distinct primes, p₀ ⋯ pₙ₋₁ + 1 is prime False statement
- FALSE: n² + n + 41 is prime for every natural number n False statement
- a and b are coprime if and only if ax + by = 1 for some integers x, y; and in that case the only common divisors of a and b are 1 and -1 Lemma
- Congruence modulo every integer is an equivalence relation on ℤ Lemma
- Congruent integers may be added, subtracted and multiplied: representative changes preserve both arithmetic operations Lemma
- Every integer n > 1 has a prime divisor; indeed the least divisor of n that exceeds 1 is prime Lemma
- For a prime p and a nonzero integer a: p^vₚ(a) ∣ a and p^vₚ(a)+1 ∤ a; pᵏ ∣ a holds exactly for k ≤ vₚ(a); vₚ(a) ≥ 1 exactly when p ∣ a; vₚ(1) = vₚ(-1) = 0; and vₚ(p) = 1 Lemma
- For a prime p and any integer a, gcd(p,a) is p when p ∣ a and 1 otherwise; so p ∤ a makes p and a coprime Lemma
- For coprime positive m,n, every pair of residue classes modulo m and n has a unique simultaneous class modulo mn 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
- For positive integers a and b: a ∣ b if and only if vₚ(a) ≤ vₚ(b) for every prime p 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 a = qb + r then a, b and b, r have exactly the same common divisors, so gcd(a,b) = gcd(b,r) Lemma
- If gcd(a,b) = 1 and a ∣ bc then a ∣ c; and if a ∣ c, b ∣ c and gcd(a,b) = 1 then ab ∣ c Lemma
- If n≥1, d=gcd(a,n) and d∣ b, then ax≡ bpmod n reduces to a congruence with coprime coefficient modulo n/d Lemma
- vₚ(ab) = vₚ(a) + vₚ(b) for nonzero integers a, b, and vₚ(a+b) ≥ min{vₚ(a), vₚ(b)} whenever a, b and a+b are all nonzero 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
- Euclid's lemma: if p is prime and p ∣ ab then p ∣ a or p ∣ b 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
- Every common multiple of a and b is a multiple of lcm(a,b), and gcd(a,b) · lcm(a,b) = |ab| 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
…and 5 more results.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 34 results over 16 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
- Divisor (Wikipedia) (standard reference, not scraped)