P-adic valuation

Let p be a prime number.

The p-adic valuation of an integer ${\displaystyle n}$ is defined to be

${\displaystyle \nu _{p}(n)={\begin{cases}\mathrm {max} \{k\in \mathbb {N} _{0}:p^{k}\mid n\}&{\text{if }}n\neq 0\\\infty &{\text{if }}n=0,\end{cases}}}$

where ${\displaystyle \mathbb {N} _{0}}$ denotes the set of natural numbers (including zero) and ${\displaystyle m\mid n}$ denotes divisibility of ${\displaystyle n}$ by ${\displaystyle m}$. In particular, ${\displaystyle \nu _{p}}$ is a function ${\displaystyle \nu _{p}\colon \mathbb {Z} \to \mathbb {N} _{0}\cup \{\infty \}}$.^[2]

For example, ${\displaystyle \nu _{2}(-12)=2}$, ${\displaystyle \nu _{3}(-12)=1}$, and ${\displaystyle \nu _{5}(-12)=0}$ since ${\displaystyle |{-12}|=12=2^{2}\cdot 3^{1}\cdot 5^{0}}$.

The notation ${\displaystyle p^{k}\parallel n}$ is sometimes used to mean ${\displaystyle k=\nu _{p}(n)}$.^[3]

If ${\displaystyle n}$ is a positive integer, then

${\displaystyle \nu _{p}(n)\leq \log _{p}n}$;

this follows directly from ${\displaystyle n\geq p^{\nu _{p}(n)}}$.

The p-adic valuation can be extended to the rational numbers as the function

${\displaystyle \nu _{p}:\mathbb {Q} \to \mathbb {Z} \cup \{\infty \}}$^[4][5]

defined by

${\displaystyle \nu _{p}\left({\frac {r}{s}}\right)=\nu _{p}(r)-\nu _{p}(s).}$

For example, ${\displaystyle \nu _{2}{\bigl (}{\tfrac {9}{8}}{\bigr )}=-3}$ and ${\displaystyle \nu _{3}{\bigl (}{\tfrac {9}{8}}{\bigr )}=2}$ since ${\displaystyle {\tfrac {9}{8}}=2^{-3}\cdot 3^{2}}$.

Some properties are:

${\displaystyle \nu _{p}(r\cdot s)=\nu _{p}(r)+\nu _{p}(s)}$

${\displaystyle \nu _{p}(r+s)\geq \min {\bigl \{}\nu _{p}(r),\nu _{p}(s){\bigr \}}}$

Moreover, if ${\displaystyle \nu _{p}(r)\neq \nu _{p}(s)}$, then

${\displaystyle \nu _{p}(r+s)=\min {\bigl \{}\nu _{p}(r),\nu _{p}(s){\bigr \}}}$

where ${\displaystyle \min }$ is the minimum (i.e. the smaller of the two).

Legendre's formula shows that ${\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty {}}{\left\lfloor {\frac {n}{p^{i}}}\right\rfloor {}}}$.

For any positive integer n, ${\displaystyle n={\frac {n!}{(n-1)!}}}$ and so ${\displaystyle \nu _{p}(n)=\nu _{p}(n!)-\nu _{p}((n-1)!)}$.

Therefore, ${\displaystyle \nu {}_{p}(n)=\sum _{i=1}^{\infty {}}{{\bigg (}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor {}-\left\lfloor {\frac {n-1}{p^{i}}}\right\rfloor {}{\bigg )}}}$.

This infinite sum can be reduced to ${\displaystyle \sum _{i=1}^{\lfloor {\log _{p}{(n)}\rfloor {}}}{{\bigg (}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor {}-\left\lfloor {\frac {n-1}{p^{i}}}\right\rfloor {}{\bigg )}}}$.

This formula can be extended to negative integer values to give:

${\displaystyle \nu {}_{p}(n)=\sum _{i=1}^{\lfloor {\log _{p}{(|n|)}\rfloor {}}}{{\bigg (}\left\lfloor {\frac {|n|}{p^{i}}}\right\rfloor {}-\left\lfloor {\frac {|n|-1}{p^{i}}}\right\rfloor {}{\bigg )}}}$

The p-adic absolute value (or p-adic norm,^[6] though not a norm in the sense of analysis) on ${\displaystyle \mathbb {Q} }$ is the function

${\displaystyle |\cdot |_{p}\colon \mathbb {Q} \to \mathbb {R} _{\geq 0}}$

defined by

${\displaystyle |r|_{p}=p^{-\nu _{p}(r)}.}$

Thereby, ${\displaystyle |0|_{p}=p^{-\infty }=0}$ for all ${\displaystyle p}$ and for example, ${\displaystyle |{-12}|_{2}=2^{-2}={\tfrac {1}{4}}}$ and ${\displaystyle {\bigl |}{\tfrac {9}{8}}{\bigr |}_{2}=2^{-(-3)}=8.}$

The p-adic absolute value satisfies the following properties.

Non-negativity	${\displaystyle |r|_{p}\geq 0}$
Positive-definiteness	${\displaystyle |r|_{p}=0\iff r=0}$
Multiplicativity	${\displaystyle |rs|_{p}=|r|_{p}|s|_{p}}$
Non-Archimedean	${\displaystyle |r+s|_{p}\leq \max \left(|r|_{p},|s|_{p}\right)}$

From the multiplicativity ${\displaystyle |rs|_{p}=|r|_{p}|s|_{p}}$ it follows that ${\displaystyle |1|_{p}=1=|-1|_{p}}$ for the roots of unity ${\displaystyle 1}$ and ${\displaystyle -1}$ and consequently also ${\displaystyle |{-r}|_{p}=|r|_{p}.}$ The subadditivity ${\displaystyle |r+s|_{p}\leq |r|_{p}+|s|_{p}}$ follows from the non-Archimedean triangle inequality ${\displaystyle |r+s|_{p}\leq \max \left(|r|_{p},|s|_{p}\right)}$.

The choice of base p in the exponentiation ${\displaystyle p^{-\nu _{p}(r)}}$ makes no difference for most of the properties, but supports the product formula:

${\displaystyle \prod _{0,p}|r|_{p}=1}$

where the product is taken over all primes p and the usual absolute value, denoted ${\displaystyle |r|_{0}}$. This follows from simply taking the prime factorization: each prime power factor ${\displaystyle p^{k}}$ contributes its reciprocal to its p-adic absolute value, and then the usual Archimedean absolute value cancels all of them.

A metric space can be formed on the set ${\displaystyle \mathbb {Q} }$ with a (non-Archimedean, translation-invariant) metric

${\displaystyle d\colon \mathbb {Q} \times \mathbb {Q} \to \mathbb {R} _{\geq 0}}$

defined by

${\displaystyle d(r,s)=|r-s|_{p}.}$

The completion of ${\displaystyle \mathbb {Q} }$ with respect to this metric leads to the set ${\displaystyle \mathbb {Q} _{p}}$ of p-adic numbers.

• p-adic number
• Valuation (algebra)
• Archimedean property
• Multiplicity (mathematics)
• Ostrowski's theorem
• Legendre's formula, for the ${\displaystyle p}$-adic valuation of ${\displaystyle n!}$
• Lifting-the-exponent lemma, for the ${\displaystyle p}$-adic valuation of ${\displaystyle a^{n}-b^{n}}$