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.
For positive integers and and every prime : and ; so the exponent-wise greatest common divisor is the of the divisibility page and not a second notion
Statement
Let with and , write (Common divisor, and the greatest common divisor , with the convention ) and (Common multiple, and the least common multiple , taken to be when or ), and let be any prime (Prime and composite integers: is prime when and its only positive divisors are and ). Then and , so all four valuations below are defined (The -adic valuation of a nonzero integer: the greatest with ), and
- ;
- ,
the minimum and maximum being taken in , whose order is total ( is a linear order on ).
- The exponent recipe does not define a second notion. If satisfies for every prime , then ; and if satisfies for every prime , then .
Facts & Assumptions
Given: Integers ; , ; and, for a prime , and .
unless ; is a common divisor of and , and every common divisor of and divides it (Common divisor, and the greatest common divisor , with the convention , is symmetric and unchanged by signs: ; moreover , , , and unless , Every common divisor of and divides ; consequently exactly when , , , and every common divisor of and divides — a characterisation that holds at as well).
For both nonzero, is the least positive common multiple of and ; in particular and (Common multiple, and the least common multiple , taken to be when or ).
, and every common multiple of and is a multiple of (Every common multiple of and is a multiple of , and ).
For positive : exactly when for every prime (For positive integers and : if and only if for every prime ).
For a prime and nonzero : ( for nonzero integers , and whenever , and are all nonzero).
For a prime and nonzero : exactly when ; and for every (For a prime and a nonzero integer : and ; holds exactly for ; exactly when ; ; and , Powers : natural exponents in a monoid and integer exponents in a group, with , Semigroup and monoid, is a commutative monoid whose group of units is ; equivalently holds exactly for and ).
On : the order is total, so any two naturals have a minimum and a maximum ( is a linear order on ); addition is commutative (Addition is commutative) and cancellative (Addition is cancellative); means for some (Order on the natural numbers, Addition of natural numbers); exactly when , and (Discreteness: is the immediate successor, The natural numbers (von Neumann)).
is a commutative ring; its order is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication; a product of two nonzero integers is nonzero and cancellation holds (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals, The integers form a totally ordered ring, Order on the integers, The integers have no zero divisors; multiplicative cancellation).
is injective and order preserving with image the nonnegative integers, , (The naturals embed in the integers).
Proof
, and every integer satisfies : with , so and preserves the order.
For naturals the minimum and maximum exist by totality, and : if the left side is , and if it is .
and , so , and ; hence , and is the least positive common multiple of and , so . All of are nonzero and their valuations are defined.
and , so and by [L4]; hence .
Conversely and , so and by [L6]; thus is a common divisor of and and therefore divides . Since , [L6] applied to gives .
, so , and [L3] gives . Applying [L5] to the nonzero pairs and gives .
Clause 1: , by antisymmetry of the order on .
Clause 2: substituting step 4.1 and step 1.2, , so by cancellation of addition on .
Clause 3, first half. Let satisfy for every prime . Then for every by step 4.1, so and by [L4], hence ; both are positive, so .
Clause 3, second half, by the same argument with step 5.1 in place of step 4.1: for every forces and , hence .
Clauses 1, 2 and 3 are established.
Remarks
-
This is the agreement item for the two pages. The exponent-wise recipe for and for is a computation of the and defined on the divisibility page, not a rival definition: clause 3 says any positive integer with the right valuations is that , respectively that . Nothing here redefines either symbol.
-
The identity sum recovers the product formula. Adding clauses 1 and 2 gives for every , which is of Every common multiple of and is a multiple of , and read through valuations. That is a consistency check, and in this proof the implication was used in the other direction: the product formula is what pins from above. The independent bound , from and , also follows from [L2] and [L4] and agrees.
-
Both arguments are restricted to positive integers, and the restriction is not cosmetic. is undefined (The -adic valuation of a nonzero integer: the greatest with ), so the pair — the one where the convention lives — is out of scope entirely, and a negative argument is handled first by ( is symmetric and unchanged by signs: ; moreover , , , and unless ).
-
The minimum and maximum are taken in , through the totality of its order ( is a linear order on ), and not through the library's Maximum and minimum of a set, which is stated for real numbers. Valuations are natural numbers and there is no reason to leave .
Depends on
- For positive integers $a$ and $b$: $a \mid b$ if and only if $v_p(a) \le v_p(b)$ for every prime $p$
- $v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$, and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$, $b$ and $a+b$ are all nonzero
- For a prime $p$ and a nonzero integer $a$: $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$; $v_p(a) \ge 1$ exactly when $p \mid a$; $v_p(1) = v_p(-1) = 0$; and $v_p(p) = 1$
- The $p$-adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$
- Common divisor, and the greatest common divisor $\gcd(a,b)$, with the convention $\gcd(0,0) := 0$
- Every common divisor of $a$ and $b$ divides $\gcd(a,b)$; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$, $d \mid a$, $d \mid b$, and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well
- $\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 multiple, and the least common multiple $\operatorname{lcm}(a,b)$, taken to be $0$ when $a = 0$ or $b = 0$
- Every common multiple of $a$ and $b$ is a multiple of $\operatorname{lcm}(a,b)$, and $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |ab|$
- Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$
- $\le$ is a linear order on $\mathbb{N}$
- Addition is commutative
- Addition is cancellative
- Powers $g^{n}$: natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$
- Semigroup and monoid
- $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$
- For integers $a$ and $b$ the following are equivalent: $a \mid b$ and $b \mid a$; $b = ua$ for a unit $u$; $|a| = |b|$. Being associates is an equivalence relation whose class of $a$ is $\{a, -a\}$
- The absolute value $|a|$ of an integer
- Absolute value in $\mathbb{Z}$: $|a| \ge 0$; $|a| = 0$ exactly when $a = 0$; $|-a| = |a|$; $|ab| = |a|\,|b|$; $-|a| \le a \le |a|$; and $|a| \le c$ exactly when $-c \le a \le c$
- The integers have no zero divisors; multiplicative cancellation
- The integers as equivalence classes of pairs of naturals
- Arithmetic on the integers
- Order on the integers
- The integers form a commutative ring
- The integers form a totally ordered ring
- The natural numbers $\mathbb{N}$ (von Neumann)
- Order on the natural numbers
- Addition of natural numbers
- The naturals embed in the integers
- Discreteness: $\sigma(n)$ is the immediate successor
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 101 results over 32 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
- Greatest common divisor (Wikipedia) (standard reference, not scraped)
- Least common multiple (Wikipedia) (standard reference, not scraped)
- Carnegie Mellon University notes: Modern arithmetic (standard reference, not scraped)
- Harris Kwong, A Spiral Workbook for Discrete Mathematics: Fundamental Theorem of Arithmetic (standard reference, not scraped)