Alphabeta MathHow 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.
If and then ; and if , and then
Statement
Let .
- If and , then .
- If , and , then .
Facts & Assumptions
Given: Integers .
and are coprime exactly when , and this holds exactly when for some (Coprime integers: , and are coprime if and only if for some integers ; and in that case the only common divisors of and are and , Common divisor, and the greatest common divisor , with the convention ).
Divisibility is reflexive and transitive; if and then for all ; and implies (Divisibility is reflexive and transitive on , and is linear: if and then for all integers ; also implies , and ).
means for some (Divisibility in : when for some integer ).
is a commutative ring: addition and multiplication are associative and commutative, , and multiplication distributes over addition (The integers form a commutative ring, Arithmetic on the integers).
Proof
Claim 1. Assume and , and fix with .
Claim 2. Assume , and . Write with .
Multiplying by gives , using associativity, commutativity and distributivity.
Now , hence by [L3]; and , hence by [L3]. Applying linearity to these two with coefficients and gives .
Then , and by [L2], so claim 1 applied with , , in place of , , gives .
Write ; then , so .
Remarks
-
No primality is used. Claim 1 is exactly the statement usually met as Euclid's lemma with prime; what the proof needs is coprimality of with , and primality of enters only later, as a way of guaranteeing that coprimality. This is why the lemma is homed here rather than with the primes.
-
Coprimality is essential in both claims. Without it, while divides neither factor ( while and : dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails ↗); and , but .
Depends on
- Coprime integers: $\gcd(a,b) = 1$
- $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$
- $\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) \ge 1$ unless $a = b = 0$
- Common divisor, and the greatest common divisor $\gcd(a,b)$, with the convention $\gcd(0,0) := 0$
- Divisibility is reflexive and transitive on $\mathbb{Z}$, and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$; also $d \mid a$ implies $d \mid ac$, $-d \mid a$ and $d \mid -a$
- Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$
- The integers form a commutative ring
- Arithmetic on the integers
Used by
- For prime p and d≥1, the congruence xᵈ≡1 (mod p) has gcd(d,p-1) nonzero solutions Corollary
- 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
- The Dirichlet function 1_ℚ, and Thomae's function t with t(x) = 1/q at a rational x = p/q in lowest terms with q ≥ 1 and t(x) = 0 at every irrational x Definition
- 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
- For a finite pairwise-coprime list of positive integers, the product divides every common multiple, and each initial product is coprime to every remaining modulus Lemma
- For odd prime p and s≥1, (1+pˢu)ᵖ≡1+pˢ⁺¹u (mod pˢ⁺²) Lemma
- In a cyclic group of order m, gᵃ has order m/gcd(a,m) Lemma
- Two essentially different two-square representations factor an odd integer Lemma
- Classification of groups of order pq for primes p<q Theorem
- Euclid's lemma: if p is prime and p ∣ ab then p ∣ a or p ∣ b 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 every odd prime p and k≥1, (ℤ/pᵏℤ)^× is cyclic of order pᵏ⁻¹(p-1) Theorem
- Rational root theorem Theorem
Dependency tree · two levels
30 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Euclid's lemma (Wikipedia) (standard reference, not scraped)
- Coprime integers (Wikipedia) (standard reference, not scraped)