TheoremStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

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 $a$ and $b$ and every prime $p$ : $v_{p} (\gcd (a, b)) = \min {v_{p} (a), v_{p} (b)}$ and $v_{p} (lcm (a, b)) = \max {v_{p} (a), v_{p} (b)}$ ; so the exponent-wise greatest common divisor is the $\gcd$ of the divisibility page and not a second notion

Statement

Let $a, b \in Z$ with $a \geq 1$ and $b \geq 1$ , write $g : = \gcd (a, b)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ) and $ℓ : = lcm (a, b)$ (Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ), and let $p$ be any prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ). Then $g \geq 1$ and $ℓ \geq 1$ , so all four valuations below are defined (The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ ), and

$v_{p} (g) = \min {v_{p} (a), v_{p} (b)}$ ;
$v_{p} (ℓ) = \max {v_{p} (a), v_{p} (b)}$ ,

the minimum and maximum being taken in $N$ , whose order is total ( $\leq$ is a linear order on $N$ ).

The exponent recipe does not define a second notion. If $d \geq 1$ satisfies $v_{p} (d) = \min {v_{p} (a), v_{p} (b)}$ for every prime $p$ , then $d = \gcd (a, b)$ ; and if $d \geq 1$ satisfies $v_{p} (d) = \max {v_{p} (a), v_{p} (b)}$ for every prime $p$ , then $d = lcm (a, b)$ .

Facts & Assumptions

Given: Integers $a, b \geq 1$ ; $g : = \gcd (a, b)$ , $ℓ : = lcm (a, b)$ ; and, for a prime $p$ , $m_{p} : = \min {v_{p} (a), v_{p} (b)}$ and $M_{p} : = \max {v_{p} (a), v_{p} (b)}$ .

[L1]

$\gcd (u, v) \geq 1$ unless $u = v = 0$ ; $\gcd (u, v)$ is a common divisor of $u$ and $v$ , and every common divisor of $u$ and $v$ divides it (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , $\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) \geq 1$ unless $a = b = 0$ , Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 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).

[L2]

For $u, v$ both nonzero, $lcm (u, v)$ is the least positive common multiple of $u$ and $v$ ; in particular $u ∣ lcm (u, v)$ and $v ∣ lcm (u, v)$ (Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L3]

$\gcd (u, v) \cdot lcm (u, v) = ∣ u v ∣$ , and every common multiple of $u$ and $v$ is a multiple of $lcm (u, v)$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ).

[L4]

For positive $u, w$ : $u ∣ w$ exactly when $v_{q} (u) \leq v_{q} (w)$ for every prime $q$ (For positive integers $a$ and $b$ : $a ∣ b$ if and only if $v_{p} (a) \leq v_{p} (b)$ for every prime $p$ ).

[L5]

For a prime $p$ and nonzero $u, w$ : $v_{p} (u w) = v_{p} (u) + v_{p} (w)$ ( $v_{p} (a b) = v_{p} (a) + v_{p} (b)$ for nonzero integers $a, b$ , and $v_{p} (a + b) \geq \min {v_{p} (a), v_{p} (b)}$ whenever $a$ , $b$ and $a + b$ are all nonzero).

[L6]

For a prime $p$ and nonzero $u$ : $p^{k} ∣ u$ exactly when $k \leq v_{p} (u)$ ; and $p^{k} \geq 1$ for every $k$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_{p} (a)} ∣ a$ and $p^{v_{p} (a) + 1} ∤ a$ ; $p^{k} ∣ a$ holds exactly for $k \leq v_{p} (a)$ ; $v_{p} (a) \geq 1$ exactly when $p ∣ a$ ; $v_{p} (1) = v_{p} (- 1) = 0$ ; and $v_{p} (p) = 1$ , Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , Semigroup and monoid, $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).

[L7]

$u ∣ w$ and $w ∣ u$ hold together exactly when $∣ u ∣ = ∣ w ∣$ (For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$ ); $∣ x ∣ = x$ for $x \geq 0$ (The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L9]

On $N$ : the order is total, so any two naturals have a minimum and a maximum ( $\leq$ is a linear order on $N$ ); addition is commutative (Addition is commutative) and cancellative (Addition is cancellative); $m \leq n$ means $m + c = n$ for some $c$ (Order on the natural numbers, Addition of natural numbers); $m < n$ exactly when $σ (m) \leq n$ , and $1 = σ (0)$ (Discreteness: $σ (n)$ is the immediate successor, The natural numbers $N$ (von Neumann)).

[L10]

$Z$ 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).

[L11]

$ι : N \to Z$ is injective and order preserving with image the nonnegative integers, $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers).

Proof

technique · direct

1.1L9L11

$0 < 1$ , and every integer $x > 0$ satisfies $x \geq 1$ : $x = ι (j)$ with $j \neq 0$ , so $1 = σ (0) \leq j$ and $ι$ preserves the order.

1.2L9

For naturals $x, y$ the minimum and maximum exist by totality, and $\min {x, y} + \max {x, y} = x + y$ : if $x \leq y$ the left side is $x + y$ , and if $y \leq x$ it is $y + x = x + y$ .

2.1step 1.1L1L2L10

$a > 0$ and $b > 0$ , so $a \neq 0$ , $b \neq 0$ and $(a, b) \neq (0, 0)$ ; hence $g \geq 1$ , and $ℓ$ is the least positive common multiple of $a$ and $b$ , so $ℓ \geq 1$ . All of $a, b, g, ℓ$ are nonzero and their valuations are defined.

3.1step 2.1step 1.2L1L4

$g ∣ a$ and $g ∣ b$ , so $v_{p} (g) \leq v_{p} (a)$ and $v_{p} (g) \leq v_{p} (b)$ by [L4]; hence $v_{p} (g) \leq m_{p}$ .

3.2step 2.1step 1.2L1L6

Conversely $m_{p} \leq v_{p} (a)$ and $m_{p} \leq v_{p} (b)$ , so $p^{m_{p}} ∣ a$ and $p^{m_{p}} ∣ b$ by [L6]; thus $p^{m_{p}}$ is a common divisor of $a$ and $b$ and therefore divides $g$ . Since $g \neq 0$ , [L6] applied to $g$ gives $m_{p} \leq v_{p} (g)$ .

3.3step 2.1L3L5L7L10

$a b > 0$ , so $∣ a b ∣ = a b$ , and [L3] gives $g ℓ = a b$ . Applying [L5] to the nonzero pairs $(g, ℓ)$ and $(a, b)$ gives $v_{p} (g) + v_{p} (ℓ) = v_{p} (a b) = v_{p} (a) + v_{p} (b)$ .

4.1step 3.1step 3.2L9

Clause 1: $v_{p} (g) = m_{p}$ , by antisymmetry of the order on $N$ .

5.1step 1.2step 4.1step 3.3L9

Clause 2: substituting step 4.1 and step 1.2, $m_{p} + v_{p} (ℓ) = v_{p} (a) + v_{p} (b) = m_{p} + M_{p}$ , so $v_{p} (ℓ) = M_{p}$ by cancellation of addition on $N$ .

5.2step 2.1step 4.1L4L7

Clause 3, first half. Let $d \geq 1$ satisfy $v_{p} (d) = m_{p}$ for every prime $p$ . Then $v_{p} (d) = v_{p} (g)$ for every $p$ by step 4.1, so $d ∣ g$ and $g ∣ d$ by [L4], hence $∣ d ∣ = ∣ g ∣$ ; both are positive, so $d = g$ .

6.1step 2.1step 5.1L4L7

Clause 3, second half, by the same argument with step 5.1 in place of step 4.1: $v_{p} (d) = M_{p} = v_{p} (ℓ)$ for every $p$ forces $d ∣ ℓ$ and $ℓ ∣ d$ , hence $d = ℓ$ .

7.1step 4.1step 5.1step 5.2step 6.1∎

Clauses 1, 2 and 3 are established.

Remarks

This is the agreement item for the two pages. The exponent-wise recipe $\min$ for $\gcd$ and $\max$ for $lcm$ is a computation of the $\gcd$ and $lcm$ defined on the divisibility page, not a rival definition: clause 3 says any positive integer with the right valuations is that $\gcd$ , respectively that $lcm$ . Nothing here redefines either symbol.
The identity $\min + \max =$ sum recovers the product formula. Adding clauses 1 and 2 gives $v_{p} (g) + v_{p} (ℓ) = v_{p} (a) + v_{p} (b) = v_{p} (a b)$ for every $p$ , which is $g ℓ = ∣ a b ∣$ of Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ 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 $v_{p} (ℓ)$ from above. The independent bound $M_{p} \leq v_{p} (ℓ)$ , from $a ∣ ℓ$ and $b ∣ ℓ$ , also follows from [L2] and [L4] and agrees.
Both arguments are restricted to positive integers, and the restriction is not cosmetic. $v_{p} (0)$ is undefined (The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ ), so the pair $(0, 0)$ — the one where the $\gcd$ convention lives — is out of scope entirely, and a negative argument is handled first by $\gcd (a, b) = \gcd (∣ a ∣, ∣ b ∣)$ ( $\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) \geq 1$ unless $a = b = 0$ ).
The minimum and maximum are taken in $N$ , through the totality of its order ( $\leq$ is a linear order on $N$ ), 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 $N$ .

For positive integers $a$ and $b$ and every prime $p$ : $v_{p} (\gcd (a, b)) = \min {v_{p} (a), v_{p} (b)}$ and $v_{p} (lcm (a, b)) = \max {v_{p} (a), v_{p} (b)}$ ; so the exponent-wise greatest common divisor is the $\gcd$ of the divisibility page and not a second notion

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources