LemmaStatement: AI-adaptedProof: AI-generatedprecheck 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 ∣ b$ if and only if $v_{p} (a) \leq v_{p} (b)$ for every prime $p$

Statement

Let $a, b \in Z$ with $a \geq 1$ and $b \geq 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 N$ with $p^{k} ∣ a$ . Then

$a ∣ b ⟺ v_{p} (a) \leq v_{p} (b) for every prime p .$

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

Facts & Assumptions

Given: The property $R (k)$ : "for every $b \geq 1$ , if $ι (k) \geq 1$ and $v_{p} (ι (k)) \leq v_{p} (b)$ for every prime $p$ , then $ι (k) ∣ b$ ", where $ι : N \to Z$ is the embedding of The naturals embed in the integers.

[L1]

For a prime $p$ and nonzero $u, v$ : $u v \neq 0$ and $v_{p} (u v) = v_{p} (u) + v_{p} (v)$ ( $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).

[L2]

For a prime $p$ and nonzero $u$ : $v_{p} (u) \geq 1$ exactly when $p ∣ u$ (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$ , The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ 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 $N$ (Strong (complete) induction).

[L5]

$d ∣ u$ means $u = d c$ for some $c$ ; divisibility is reflexive and transitive, and $d ∣ u$ implies $d ∣ u c$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L6]

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

[L7]

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

[L8]

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

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

Proof

technique · induction

1.1

$0 < 1$ , since $1 = ι (1)$ is nonnegative and differs from $0 = ι (0)$ ; and every integer $x > 0$ satisfies $x \geq 1$ , because $x = ι (j)$ with $j \neq 0$ , so $1 = σ (0) \leq j$ and $ι$ preserves the order.

L7L9

1.2

The forward implication. Suppose $a ∣ b$ and fix $c$ with $b = a c$ . Then $c \neq 0$ , since $b \neq 0$ , so [L1] gives $v_{p} (b) = v_{p} (a) + v_{p} (c) \geq v_{p} (a)$ for every prime $p$ .

L1L5L7L8

1.3

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

2.1

$R (0)$ holds vacuously: $ι (0) = 0$ and $0 \geq 1$ is false.

basestep 1.1L9

2.2

Put $a : = ι (k)$ and suppose $a \geq 1$ , and let $b \geq 1$ satisfy $v_{p} (a) \leq v_{p} (b)$ for every prime $p$ . If $a = 1$ then $a ∣ b$ , so assume $a > 1$ .

step 1.1L5L8

3.1

Fix a prime $q$ with $q ∣ a$ , and fix $a_{1}$ with $a = q a_{1}$ . Then $v_{q} (a) \geq 1$ , hence $v_{q} (b) \geq 1$ by hypothesis, so $q ∣ b$ ; fix $b_{1}$ with $b = q b_{1}$ .

step 2.2L2L3L5choose

4.1

$a_{1} \geq 1$ and $b_{1} \geq 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} \geq 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) \leq v_{p} (b) = v_{p} (q) + v_{p} (b_{1})$ , so $v_{p} (a_{1}) \leq v_{p} (b_{1})$ by cancellation of $v_{p} (q)$ in the order of $N$ .

step 2.2step 3.1step 4.1L1L7

6.1

Write $a_{1} = ι (j)$ ; then $j < k$ , since otherwise $k \leq j$ and the order-preserving $ι$ would give $a \leq a_{1}$ , contradicting step 5.1. By step 1.3 applied to $j$ , together with steps 4.1 and 5.2, $a_{1} ∣ 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 ∣ 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 $ι (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} (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) and the existence of a prime divisor. The factorisation route is available too, via For $n \geq 1$ and any injective list $p : r \to 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 ∣ b$ is unchanged by replacing either argument by its negative (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - 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 $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} (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 · two levels

58 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

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

For positive integers aa and bb: a∣ba∣b if and only if vp(a)≤vp(b)vp​(a)≤vp​(b) for every prime pp