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.1

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

L9L11

1.2

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.1

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

step 1.1L1L2L10

3.1

$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}$ .

step 2.1step 1.2L1L4

3.2

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

step 2.1step 1.2L1L6

3.3

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

step 2.1L3L5L7L10

4.1

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

step 3.1step 3.2L9

5.1

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

step 1.2step 4.1step 3.3L9

5.2

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

step 2.1step 4.1L4L7

6.1

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 = ℓ$ .

step 2.1step 5.1L4L7

7.1

Clauses 1, 2 and 3 are established.

step 4.1step 5.1step 5.2step 6.1∎

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

Depends on

Used by

Dependency tree · two levels

76 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

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)