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\mathrm{\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,p^{\sigma (k)}=p^k\cdot p(k\in \mathbb{N})\mathrm{.}$

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\mathrm{\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\mathrm{\ne }0$, so $\mathrm{\mid }{p}^k\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }$ (If $d\mid a$ and $a\mathrm{\ne }0$ then $d\mathrm{\ne }0$ and $\mathrm{\mid }d\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }$; hence the set of divisors of a nonzero integer is bounded above by $\mathrm{\mid }a\mathrm{\mid }$); and $p^k\ge 1>0$ gives $\mathrm{\mid }{p}^k\mathrm{\mid }=p^k$ (The absolute value $\mathrm{\mid }a\mathrm{\mid }$ of an integer, Absolute value in $\mathbb{Z}$: $\mathrm{\mid }a\mathrm{\mid }\ge 0$; $\mathrm{\mid }a\mathrm{\mid }=0$ exactly when $a=0$; $\mathrm{\mid }-a\mathrm{\mid }=\mathrm{\mid }a\mathrm{\mid }$; $\mathrm{\mid }ab\mathrm{\mid }=\mathrm{\mid }a\mathrm{\mid }\mathrm{\mid }b\mathrm{\mid }$; $-\mathrm{\mid }a\mathrm{\mid }\le a\le \mathrm{\mid }a\mathrm{\mid }$; and $\mathrm{\mid }a\mathrm{\mid }\le c$ exactly when $-c\le a\le c$). Combining with the previous paragraph, $\iota (k)<p^k\le \mathrm{\mid }a\mathrm{\mid }$. So the set of integers $\iota [E(p,a)]=\{\iota (k):k\in E(p,a)\}$ is nonempty and bounded above by $\mathrm{\mid }a\mathrm{\mid }$, 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\mathrm{\ne }0$ explicitly. The convention $v_p(0):=\mathrm{\infty }$ is not adopted: it would need a value set enlarging $\mathbb{N}$ by a greatest element in which to place $\mathrm{\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 $+\mathrm{\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\mathrm{/}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}^{\mathrm{\prime }}$ with $p\nmid a^{\mathrm{\prime }}$.