LemmaStatement: AI-adaptedProof: 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.

For positive integers $a$ and $b$ : $a \mid b$ if and only if $v_p(a) \le v_p(b)$ for every prime $p$

Statement

Let $a, b \in \mathbb{Z}$ with $a \ge 1$ and $b \ge 1$ , and let $v_p$ be the $p$ -adic valuation of The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ . Then

$a \mid b \qquad \Longleftrightarrow \qquad v_p(a) \le v_p(b) \ \text{ for every prime } p .$

Both valuations are defined, since $a$ and $b$ are nonzero.

Facts & Assumptions

Given: The property $R(k)$ : "for every $b \ge 1$ , if $\iota(k) \ge 1$ and $v_p(\iota(k)) \le v_p(b)$ for every prime $p$ , then $\iota(k) \mid b$ ", where $\iota : \mathbb{N} \to \mathbb{Z}$ is the embedding of The naturals embed in the integers.

[L1]

For a prime $p$ and nonzero $u, v$ : $uv \ne 0$ and $v_p(uv) = v_p(u) + v_p(v)$ ( $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).

[L2]

For a prime $p$ and nonzero $u$ : $v_p(u) \ge 1$ exactly when $p \mid u$ (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$ ).

[L3]

Every integer $> 1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime); every prime satisfies $q > 1$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L4]

Strong induction on $\mathbb{N}$ (Strong (complete) induction).

[L5]

$d \mid u$ means $u = dc$ for some $c$ ; divisibility is reflexive and transitive, and $d \mid u$ implies $d \mid uc$ (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]

A product of two nonzero integers is nonzero (The integers have no zero divisors; multiplicative cancellation).

[L7]

On $\mathbb{N}$ : $m \le n$ means $m + c = n$ for some $c$ , so $m \le m + n$ always (Order on the natural numbers, Addition of natural numbers); $m + x \le m + y$ holds exactly when $x \le y$ (Order is compatible with addition); $m < n$ exactly when $\sigma(m) \le n$ , and $1 = \sigma(0)$ (Discreteness: $\sigma(n)$ is the immediate successor, The natural numbers $\mathbb{N}$ (von Neumann)).

[L8]

$\mathbb{Z}$ is a commutative ring; its order is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication (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).

[L9]

$\iota$ is injective, preserves addition, multiplication and order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ (The naturals embed in the integers).

Proof

technique · induction

1.1

$0 < 1$ , since $1 = \iota(1)$ is nonnegative and differs from $0 = \iota(0)$ ; and every integer $x > 0$ satisfies $x \ge 1$ , because $x = \iota(j)$ with $j \ne 0$ , so $1 = \sigma(0) \le j$ and $\iota$ preserves the order.

L7L9

1.2

The forward implication. Suppose $a \mid b$ and fix $c$ with $b = ac$ . Then $c \ne 0$ , since $b \ne 0$ , so [L1] gives $v_p(b) = v_p(a) + v_p(c) \ge v_p(a)$ for every prime $p$ .

L1L5L7L8

1.3

Let $k \in \mathbb{N}$ and assume $R(j)$ for every $j < k$ .

2.1

$R(0)$ holds vacuously: $\iota(0) = 0$ and $0 \ge 1$ is false.

basestep 1.1L9

2.2

Put $a := \iota(k)$ and suppose $a \ge 1$ , and let $b \ge 1$ satisfy $v_p(a) \le v_p(b)$ for every prime $p$ . If $a = 1$ then $a \mid b$ , so assume $a > 1$ .

step 1.1L5L8

3.1

Fix a prime $q$ with $q \mid a$ , and fix $a_1$ with $a = q a_1$ . Then $v_q(a) \ge 1$ , hence $v_q(b) \ge 1$ by hypothesis, so $q \mid b$ ; fix $b_1$ with $b = q b_1$ .

step 2.2L2L3L5choose

4.1

$a_1 \ge 1$ and $b_1 \ge 1$ : they are nonzero because $a$ and $b$ are, and if $a_1 < 0$ then $q a_1 < 0$ contradicting $a > 0$ , so $a_1 > 0$ and hence $a_1 \ge 1$ ; the same argument applies to $b_1$ .

step 1.1step 3.1L6L8

5.1

$a_1 < a$ : since $q > 1$ we have $q - 1 > 0$ , and $a_1 > 0$ , so $a - a_1 = (q-1)a_1 > 0$ .

step 3.1step 4.1L3L8

5.2

For every prime $p$ : $v_p(q) + v_p(a_1) = v_p(a) \le v_p(b) = v_p(q) + v_p(b_1)$ , so $v_p(a_1) \le v_p(b_1)$ by cancellation of $v_p(q)$ in the order of $\mathbb{N}$ .

step 2.2step 3.1step 4.1L1L7

6.1

Write $a_1 = \iota(j)$ ; then $j < k$ , since otherwise $k \le j$ and the order-preserving $\iota$ would give $a \le a_1$ , contradicting step 5.1. By step 1.3 applied to $j$ , together with steps 4.1 and 5.2, $a_1 \mid b_1$ .

step 1.3step 4.1step 5.1step 5.2L9

7.1

Hence $b = q b_1 = q(a_1 c) = (q a_1) c = a c$ for the $c$ with $b_1 = a_1 c$ , so $a \mid b$ and $R(k)$ holds.

step 3.1step 6.1L5L8

8.1

Steps 2.2 and 7.1 cover both possibilities for $a$ , so $R$ at $k$ follows from $R$ below $k$ ; with step 2.1, strong induction gives $R(k)$ for every $k$ . Since a positive integer $a$ is $\iota(k)$ for a unique $k$ , that is the reverse implication, and step 1.2 is the forward one.

step 1.2step 2.1step 2.2step 7.1L4L9discharge-induction∎

Remarks

No canonical factorisation is needed. The reverse implication is often proved by writing both integers over a common list of primes and comparing exponents; the descent used here peels off one prime divisor at a time and needs only additivity of $v_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) and the existence of a prime divisor. The factorisation route is available too, via 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, and gives the same statement.
Positivity is a real hypothesis, and only mildly so. $v_p$ is undefined at $0$ , so the pair must avoid it; signs are harmless, since $a \mid b$ is unchanged by replacing either argument by its negative (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$ ) and $v_p(-u) = v_p(u)$ for the same reason. The statement is therefore about $|a|$ and $|b|$ in substance.
The valuation criterion is the shape the $\gcd$ and $\operatorname{lcm}$ formulas need, and 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 uses exactly this lemma to check the characterisation of $\gcd$ proved on the divisibility page.

Depends on

Used by

Dependency tree · next 3 levels

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

P-adic valuation (Wikipedia) (standard reference, not scraped)
Carnegie Mellon University notes: Modern arithmetic (standard reference, not scraped)

For positive integers aaa and bbb: a∣ba \mid ba∣b if and only if vp(a)≤vp(b)v_p(a) \le v_p(b)vp​(a)≤vp​(b) for every prime ppp