ExampleConstruction: AI-generatedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28

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.

$360 = 2^{3} \cdot 3^{2} \cdot 5$ and $84 = 2^{2} \cdot 3 \cdot 7$ , with $\gcd(360,84) = 12$ and $\operatorname{lcm}(360,84) = 2520$ read off the exponents

Example

Powers are the natural powers of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\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 $k \in \mathbb{N}$ the symbol $k$ inside $\mathbb{Z}$ means $\iota(k)$ , the embedding of The naturals embed in the integers.

$360 \;=\; 2^{3} \cdot 3^{2} \cdot 5, \qquad 84 \;=\; 2^{2} \cdot 3 \cdot 7 .$

Reading these against the injective list of primes $p = (2,3,5,7)$ , which contains every prime divisor of both numbers, For $n \ge 1$ and any injective list $p : r \to \mathbb{Z}$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ; the exponents are determined by $n$ , and $v_q(n) = 0$ for every prime $q$ outside the list identifies the exponents as valuations (The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ):

$p$	$2$	$3$	$5$	$7$
$v_p(360)$	$3$	$2$	$1$	$0$
$v_p(84)$	$2$	$1$	$0$	$1$
$\min$	$2$	$1$	$0$	$0$
$\max$	$3$	$2$	$1$	$1$

By 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(\operatorname{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 the minimum row is the valuation vector of $\gcd(360,84)$ and the maximum row that of $\operatorname{lcm}(360,84)$ , so

$\gcd(360,84) \;=\; 2^{2} \cdot 3 \;=\; 12, \qquad \operatorname{lcm}(360,84) \;=\; 2^{3} \cdot 3^{2} \cdot 5 \cdot 7 \;=\; 2520 .$

Two independent checks are carried out below: the Euclidean algorithm of The Euclidean algorithm: for $a \in \mathbb{Z}$ and $b > 0$ the remainder descent from $(a,b)$ terminates, and the last nonzero remainder is $\gcd(a,b)$ returns $12$ from the descent $360 = 4 \cdot 84 + 24$ , $84 = 3 \cdot 24 + 12$ , $24 = 2 \cdot 12 + 0$ ; and $12 \cdot 2520 = 30240 = 360 \cdot 84$ , as 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|$ requires.

Facts & Assumptions

Given: The integers $360$ , $84$ , $12$ and $2520$ , and the primes $2$ , $3$ , $5$ , $7$ .

[L1]

$\mathbb{Z}$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , and multiplication distributes over addition (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals); its order is total, antisymmetric and transitive (The integers form a totally ordered ring, Order on the integers, The naturals embed in the integers).

[L2]

$g^{0} = 1$ and $g^{\sigma(k)} = g^{k} g$ in $(\mathbb{Z},\cdot,1)$ ; and $g^{m+n} = g^{m}g^{n}$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , Exponent laws in a group: $g^{m+n} = g^{m}g^{n}$ and $(g^{m})^{n} = g^{mn}$ for all $m, n \in \mathbb{Z}$ , and $(gh)^{n} = g^{n}h^{n}$ when $g$ and $h$ commute, 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$ , The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L3]

For $n \ge 1$ and an injective list $p$ of primes containing every prime divisor of $n$ : $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ , the exponents are determined by $n$ , and $v_q(n) = 0$ for a prime $q$ off the list (For $n \ge 1$ and any injective list $p : r \to \mathbb{Z}$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ; the exponents are determined by $n$ , and $v_q(n) = 0$ for every prime $q$ outside the list, The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$ , Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product, The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ , 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$ , $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).

[L4]

For positive $a, b$ and every prime $p$ : $v_p(\gcd(a,b)) = \min\{v_p(a),v_p(b)\}$ and $v_p(\operatorname{lcm}(a,b)) = \max\{v_p(a),v_p(b)\}$ ; and a positive integer with those valuations is the $\gcd$ , respectively the $\operatorname{lcm}$ (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(\operatorname{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, Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ , Common multiple, and the least common multiple $\operatorname{lcm}(a,b)$ , taken to be $0$ when $a = 0$ or $b = 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).

[L5]

For $a \in \mathbb{Z}$ and $b > 0$ there is exactly one pair $(q,r)$ with $a = qb + r$ and $0 \le r < b$ , and $b \mid a$ exactly when $r = 0$ (Division with remainder in $\mathbb{Z}$ : for $a \in \mathbb{Z}$ and $b > 0$ there are unique $q, r \in \mathbb{Z}$ with $a = qb + r$ and $0 \le r < b$ , Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , 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$ ).

[L6]

The remainder descent from $(a,b)$ with $b > 0$ terminates and its last nonzero remainder is $\gcd(a,b)$ (The Euclidean algorithm: for $a \in \mathbb{Z}$ and $b > 0$ the remainder descent from $(a,b)$ terminates, and the last nonzero remainder is $\gcd(a,b)$ ).

[L7]

$\gcd(a,b)\operatorname{lcm}(a,b) = |ab|$ (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|$ ).

[L9]

If $q$ is prime and $q \mid uv$ then $q \mid u$ or $q \mid v$ (Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ).

[L8]

An integer $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ); and a divisor $d$ of a nonzero $a$ satisfies $|d| \le |a|$ (If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$ ; hence the set of divisors of a nonzero integer is bounded above by $|a|$ ).

Verification

technique · direct

1.1

The two products are correct: $2^{3} = 8$ , $3^{2} = 9$ , and $8 \cdot 9 = 72$ with $72 \cdot 5 = 360$ ; likewise $2^{2} = 4$ , $4 \cdot 3 = 12$ and $12 \cdot 7 = 84$ .

L1L2algebra

1.2

$2$ , $3$ , $5$ and $7$ are prime, and they are pairwise distinct. Each exceeds $1$ ; and a positive divisor $d$ of such a number $a$ satisfies $1 \le d \le a$ by [L8], so the candidates are the finitely many integers in that range, and each is settled by its remainder under [L5]: $2 = 1 \cdot 2 + 0$ has only $1$ and $2$ as candidates; for $3$ the extra candidate $2$ gives $3 = 1 \cdot 2 + 1$ ; for $5$ the extra candidates $2, 3, 4$ give remainders $1$ , $2$ , $1$ ; and for $7$ the extra candidates $2,3,4,5,6$ give remainders $1$ , $1$ , $3$ , $2$ , $1$ . In each case no divisor other than $1$ and the number itself survives.

L1L5L8algebra

2.1

The list $p = (2,3,5,7)$ is injective and consists of primes, and it contains every prime divisor of $360$ and of $84$ . Injectivity and primality are step 1.2. For the covering: if $q$ is prime and $q \mid 360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5$ , repeated use of [L9] gives $q \mid 2$ , $q \mid 3$ or $q \mid 5$ , and $q$ being a positive divisor of a prime with $q > 1$ forces $q$ to be that prime; likewise $q \mid 84 = 2 \cdot 2 \cdot 3 \cdot 7$ forces $q \in \{2,3,7\}$ .

step 1.1step 1.2L8L9

3.1

By [L3] applied to $360$ with this list, the exponents in step 1.1 are the valuations: $v_2(360) = 3$ , $v_3(360) = 2$ , $v_5(360) = 1$ , $v_7(360) = 0$ .

step 1.1step 2.1L3

3.2

By [L3] applied to $84$ : $v_2(84) = 2$ , $v_3(84) = 1$ , $v_5(84) = 0$ , $v_7(84) = 1$ .

step 1.1step 2.1L3

4.1

Taking minima entrywise gives $2, 1, 0, 0$ , and $2^{2} \cdot 3^{1} \cdot 5^{0} \cdot 7^{0} = 4 \cdot 3 = 12$ ; by [L3] the valuations of $12$ against this list are exactly those exponents, so $12$ has the valuation vector of $\gcd(360,84)$ and therefore equals it by [L4].

step 3.1step 3.2L1L2L3L4

4.2

Taking maxima entrywise gives $3, 2, 1, 1$ , and $2^{3} \cdot 3^{2} \cdot 5 \cdot 7 = 72 \cdot 35 = 2520$ ; the same argument gives $\operatorname{lcm}(360,84) = 2520$ .

step 3.1step 3.2L1L2L3L4

5.1

First check, the Euclidean algorithm. $4 \cdot 84 = 336$ and $336 + 24 = 360$ with $0 \le 24 < 84$ ; $3 \cdot 24 = 72$ and $72 + 12 = 84$ with $0 \le 12 < 24$ ; $2 \cdot 12 = 24$ and $24 + 0 = 24$ with $0 \le 0 < 12$ . By the uniqueness in [L5] these are the divisions of the descent, whose last nonzero remainder is $12$ , so $\gcd(360,84) = 12$ by [L6], agreeing with step 4.1.

step 4.1L1L5L6algebra

5.2

Second check, the product formula. $12 \cdot 2520 = 30240$ and $360 \cdot 84 = 30240$ , and $360 \cdot 84 > 0$ so $|360 \cdot 84| = 360 \cdot 84$ ; this is [L7], agreeing with steps 4.1 and 4.2.

step 4.1step 4.2L1L7algebra

6.1

The factorisations, the valuation table, and both values of $\gcd$ and $\operatorname{lcm}$ are verified, and the two independent checks agree.

step 4.1step 4.2step 5.1step 5.2∎

Remarks

The cross-check is the point of the example. The Euclidean algorithm: for $a \in \mathbb{Z}$ and $b > 0$ the remainder descent from $(a,b)$ terminates, and the last nonzero remainder is $\gcd(a,b)$ computes $\gcd(360,84)$ without ever mentioning a prime, and the exponent recipe computes it without ever performing a division; they return the same integer because 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(\operatorname{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 proves the recipe identifies the $\gcd$ of Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ rather than defining a rival.
Which method is practical is a separate question. Factoring $360$ and $84$ is easy because they are small; for large integers the Euclidean algorithm is the only one of the two that runs, since no factorisation is needed. Nothing here claims anything about the cost of either procedure.
The exponent $0$ columns matter. $v_5(84) = 0$ and $v_7(360) = 0$ are what make the same list serve both numbers, and clause 2 of For $n \ge 1$ and any injective list $p : r \to \mathbb{Z}$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ; the exponents are determined by $n$ , and $v_q(n) = 0$ for every prime $q$ outside the list is the statement that every prime off the list contributes $0$ as well.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 101 results over 29 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

Fundamental theorem of arithmetic (Wikipedia) (standard reference, not scraped)
P-adic valuation (Wikipedia) (standard reference, not scraped)

360=23⋅32⋅5360 = 2^{3} \cdot 3^{2} \cdot 5360=23⋅32⋅5 and 84=22⋅3⋅784 = 2^{2} \cdot 3 \cdot 784=22⋅3⋅7, with gcd⁡(360,84)=12\gcd(360,84) = 12gcd(360,84)=12 and lcm⁡(360,84)=2520\operatorname{lcm}(360,84) = 2520lcm(360,84)=2520 read off the exponents