The $p$-adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$) and let $a \in \mathbb{Z}$ with $a \ne 0$. Powers $p^{k}$ for $k \in \mathbb{N}$ are the natural powers of Powers $g^{n}$: natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ taken 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$ and Semigroup and monoid, so that

$p^{0} = 1, \qquad p^{\sigma(k)} = p^{k} \cdot p \quad (k \in \mathbb{N}).$

Put

$E(p,a) \;:=\; \{\, k \in \mathbb{N} \;:\; p^{k} \mid a \,\}$

(Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$). Then $E(p,a)$ has a greatest element, and the $p$-adic valuation of $a$ is

$v_p(a) \;:=\; \max E(p,a) \;\in\; \mathbb{N},$

the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$.

Why a greatest element exists. Three facts are needed, and each is proved here rather than assumed.

The set is nonempty. $p^{0} = 1$ and $1 \mid a$ for every $a$ (Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$), so $0 \in E(p,a)$.

Every power of $p$ exceeds its own exponent. We claim $p^{k} \ge 1$ and $\iota(k) < p^{k}$ for every $k \in \mathbb{N}$, where $\iota : \mathbb{N} \to \mathbb{Z}$ is the embedding of The naturals embed in the integers. Both are proved by induction (The principle of mathematical induction). At $k = 0$ we have $p^{0} = 1 \ge 1$ and $\iota(0) = 0 < 1 = p^{0}$, using $0 < 1$, which holds because $1 = \iota(1)$ is nonnegative and differs from $0 = \iota(0)$ by injectivity of $\iota$. Assume both at $k$. Since $p > 1$ we have $p - 1 > 0$, hence $p - 1 \ge 1$ by discreteness of the order on $\mathbb{Z}$ (Discreteness: $\sigma(n)$ is the immediate successor, The naturals embed in the integers: an integer $x > 0$ is $\iota(j)$ with $j \ne 0$, so $1 = \sigma(0) \le j$ and $1 \le x$). Therefore $p^{\sigma(k)} - p^{k} = p^{k}(p-1) \ge p^{k} \ge 1$, because $p^{k} \ge 1 > 0$ and positives are closed under multiplication (The integers form a totally ordered ring); so $p^{\sigma(k)} \ge p^{k} + 1 \ge 1 + 1 > 1$. The same discreteness applied to $p^{k} - \iota(k) > 0$ gives $\iota(k) + 1 \le p^{k}$, and $\iota(\sigma(k)) = \iota(k) + 1$ because $\sigma(k) = k + 1$ in $\mathbb{N}$ (Addition of natural numbers) and $\iota$ preserves addition; so $\iota(\sigma(k)) \le p^{k} < p^{k} + 1 \le p^{\sigma(k)}$. The induction is complete.

The set is bounded. Let $k \in E(p,a)$. Then $p^{k} \mid a$ with $a \ne 0$, so $|p^{k}| \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|$); and $p^{k} \ge 1 > 0$ gives $|p^{k}| = p^{k}$ (The absolute value $|a|$ of an integer, Absolute value in $\mathbb{Z}$: $|a| \ge 0$; $|a| = 0$ exactly when $a = 0$; $|-a| = |a|$; $|ab| = |a|\,|b|$; $-|a| \le a \le |a|$; and $|a| \le c$ exactly when $-c \le a \le c$). Combining with the previous paragraph, $\iota(k) < p^{k} \le |a|$. So the set of integers $\iota[E(p,a)] = \{\, \iota(k) : k \in E(p,a) \,\}$ is nonempty and bounded above by $|a|$, hence has a unique greatest element (A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element). That greatest element lies in the set, so it is $\iota(k_0)$ for some $k_0 \in E(p,a)$; and since $\iota$ is injective and preserves the order in both directions, $k_0$ is the greatest element of $E(p,a)$ and is unique. We set $v_p(a) := k_0$.

$v_p(0)$ is left undefined. Every power of $p$ divides $0$ (Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$), so $E(p,0) = \mathbb{N}$ has no greatest element and the clause above defines nothing. Every statement about $v_p$ in this library therefore carries the hypothesis $a \ne 0$ explicitly. The convention $v_p(0) := \infty$ is not adopted: it would need a value set enlarging $\mathbb{N}$ by a greatest element in which to place $\infty$, and no such set is available at this point in the reading order. The library does build a totally ordered set with a greatest element — the extended real line, whose greatest element is $+\infty$ — but it is constructed far above this page, and taking the values of $v_p$ there would make a definition about $\mathbb{Z}$ rest on the construction of $\mathbb{R}$.

• $v_p(a)$ is a natural number, not an integer. It is a von Neumann natural (The natural numbers $\mathbb{N}$ (von Neumann)), which is exactly what the exponent slot of Powers $g^{n}$: natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ takes, so $p^{v_p(a)}$ is meaningful without any translation. Where a valuation has to be subtracted from another, as in The $p$-adic valuation extends to the nonzero rationals by $v_p(a/b) := v_p(a) - v_p(b) \in \mathbb{Z}$, independently of the representation; it satisfies $v_p(xy) = v_p(x) + v_p(y)$, and $v_p(x+y) \ge \min\{v_p(x), v_p(y)\}$ whenever $x$, $y$ and $x+y$ are nonzero, the values are first carried into $\mathbb{Z}$ along $\iota$ (The naturals embed in the integers).

• These are monoid powers, and deliberately not Integer powers $a^m$. That definition is stated for an element of the ambient ordered field $\mathbb{R}$; using it here would make a statement about $\mathbb{Z}$ rest on the whole construction of the real numbers for no gain. The two agree along the embeddings $\mathbb{Z} \to \mathbb{Q} \to \mathbb{R}$, since both are defined by the same recursion $x^{0} = 1$, $x^{\sigma(k)} = x^{k} x$ and the embeddings preserve products and the constant $1$; nothing on this page depends on that observation, and it is recorded here only so the reader does not think a second notion of power has been introduced.

• The definition is by a maximum, and 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$ converts it into the form later proofs use: $p^{v_p(a)} \mid a$, $p^{v_p(a)+1} \nmid a$, and $a = p^{v_p(a)} a'$ with $p \nmid a'$.