P-adic valuation ($v_p$)

For a prime number $p$ and a nonzero integer $N$, the P-adic valuation counts the exponent of $p$ in its prime factorization:For $72=2^3\cdot 3^2$, it gives $v_2(72)=3$, $v_3(72)=2$, and $v_5(72)=0$. The sign of a nonzero integer does not change these prime exponents. Relative to an ordered factor base, the valuations supply the coordinates of its exponent vector.

The P-adic valuation extends to nonzero rational numbers by $v_p(a/b)=v_p(a)-v_p(b)$. For example, $v_5(72/25)=-2$ records a factor in the denominator instead of the numerator. Multiplication adds valuations, $v_p(xy)=v_p(x)+v_p(y)$; this is the arithmetic reason why adding exponent vectors can make a product a square. In particular, a positive integer is a square of a number precisely when all its prime exponents are even integers, the criterion used by a factor base.

The p-adic integers retain arithmetic information modulo arbitrarily high powers of one prime number $p$. They form the subringof the P-adic numbers. Their p-adic absolute value bounds the allowed denominators: $1/3$ belongs to ${\mathbb{Z}}_2$, while $1/2$ does not. The name therefore describes a local arithmetic ring, not just the ordinary integers.^[ref]

A concrete description gives an element by a compatible sequence of congruence classes:The inverse limit condition says that gaining more precision must preserve the digits already determined. Each $r_n$ is a residue modulo $p^n$; choosing its least nonnegative integer representative gives $0\le r_n<p^n$. The ordinary integer $13$ gives residues $1,1,5,13$ modulo $2,4,8,16$.

The useful feature is that one exact object organizes an unlimited family of finite modular arithmetic calculations. Addition and multiplication are performed modulo each $p^n$, and the results remain compatible. A p-adic digit expansion makes this concrete:The expansion is unique and converges in the p-adic metric; its higher powers have smaller p-adic absolute value. The digit agreement and p-adic distance criterion tells exactly which finite digits a precision bound preserves.^[ref]

The p-adic digits are the unique coefficients in $x={\sum }_{j\ge 0}{b}_j{p}^j$ for a p-adic integer $x$. Taking least nonnegative representatives of its congruence classes,so each new residue determines one more p-adic digit. For $13$ in ${\mathbb{Z}}_2$, the low-to-high digits are $1,0,1,1,0,\dots$, giving $13=1+0\cdot 2+1\cdot 4+1\cdot 8$. A finite prefix describes a whole coset, not a unique infinite expansion.

Two p-adic integers agree in their first $n$ low-order p-adic digits precisely when their difference is divisible by $p^n$. Equivalently,If the first differing digit has index $j$, the remaining leading coefficient is nonzero modulo $p$, giving exact P-adic valuation $j$ and p-adic metric $p^{-j}$. If no digit differs, the two elements are equal and their distance is zero. Truncating at $r_n$ therefore gives $|x-r_n{|}_p\le p^{-n}$, with a stricter bound possible when further digits are zero.

Let $a$ be an integer not divisible by $p$. Its modular inverse modulo $p^n$ has a unique least nonnegative representative $r_n$. Reducing the inverse equation modulo $p^n$ shows that the representatives are compatible. Since $a$ is a p-adic unit,so the sequence converges to the inverse $a^{-1}$ in ${\mathbb{Z}}_p$. This computes a fraction through finite integer operations.

For $a=3$ and $p=2$, the first eight representatives are $1,3,3,11,11,43,43,171$. Each satisfies $3r_n\equiv 1(\mathrm{mod}{2}^n)$. The resulting expansion isThe geometric series has ratio $4$, whose 2-adic absolute value is $1/4$, and its sum is $1+2/(1-4)=1/3$. In the ordinary real number absolute value, the representatives grow. Different metrics impose different meanings of a good approximation. The periodic digits here are a specific instance of the rational expansions studied in Conrad's authored note.^[ref]

The p-adic integers form a complete metric space and a discrete valuation ring. Every nonzero $x$ is uniquely $p^{k}u$ with $k=v_p(x)\ge 0$ and $u$ a p-adic unit. The prime $p$ is a uniformizer, and reduction modulo $p$ gives the residue field ${\mathbb{F}}_p$. The element $p$ has no inverse inside ${\mathbb{Z}}_p$, so the ring is not a field.

For a short ideal-classification outline, take a nonzero ideal and choose an element of smallest P-adic valuation $k$, which exists by the well-ordering principle. Its unit factor is invertible, so the ideal contains $p^k$. Every other element is divisible by $p^k$, proving that the ideal is $p^k{\mathbb{Z}}_p$. Completeness follows because ${\mathbb{Z}}_p$ is a closed subset of the complete metric space ${\mathbb{Q}}_p$. The zero ideal is separate from this nonzero-ideal classification.

The cosets $a+p^n{\mathbb{Z}}_p$ form a neighborhood basis in the additive group of p-adic integers. An open subgroup contains $p^n{\mathbb{Z}}_p$ for some $n$, so has finite index. Conversely, if the index is $m$, the finite quotient is annihilated by $m$, giving $m{\mathbb{Z}}_p\subset H$. Multiplication by the unit part of $m$ is bijective, so $m{\mathbb{Z}}_p=p^{v_p(m)}{\mathbb{Z}}_p$ is open. This proof applies to abstract subgroups without assuming beforehand that they are closed.

A 7-adic integer is an element of the p-adic integers for $p=7$, equivalently a compatible sequence of residues modulo $7^r$. Its p-adic digits lie in $\{0,1,\dots ,6\}$. For example, $10=3+1\cdot 7$ has low-to-high digits $3,1,0,\dots$.

A 2-adic integer is an element of the p-adic integers for $p=2$, equivalently a compatible sequence of residues modulo $2^r$. Its binary p-adic digits begin with its parity. The highlighted residue-tree path for $13$ begins $1,0,1,1$, while modular inversion converges to a p-adic inverse computes the infinite expansion of $1/3$.

An element $\alpha \in {\mathbb{Z}}_p$ topologically generates the additive group of ${\mathbb{Z}}_p$ exactly when $\alpha \not\equiv 0(\mathrm{mod}p)$, equivalently when $\alpha$ is a p-adic unit. In that case its image generates every cyclic quotient $\mathbb{Z}/p^n\mathbb{Z}$.

The 2-adic valuation is the P-adic valuation at the prime number $p=2$.

For a nonnegative integer $n$ and a prime number $p$, the Legendre formula computes the prime exponent in a factorial without forming that huge product:Here $\lfloor x\rfloor$ is the floor function. The sum is finite: every term with $p^j>n$ is zero. When $n=0$, all terms vanish, agreeing with $0!=1$ and $v_p(1)=0$. The prime number hypothesis matters: a composite number does not give the same P-adic valuation or additive prime exponent. For example, the floor sum with $n=6,p=4$ is one, whereas $4^2$ divides $6!=720$.

Why count multiples repeatedly? Each multiple of $p$ in $1,\dots ,n$ contributes one factor of $p$; each multiple of $p^2$ contributes another; and so on. A factor $m$ with P-adic valuation $a$ occurs in exactly the first $a$ counts. Adding those contributions proves the formula.^[ref]

For the original example $n=50,p=3$,The five multiples $9,18,27,36,45$ each contribute a second factor of three. The factor $27$ contributes a third, so it appears in all three rows. Equivalently, among $1,\dots ,50$ there are eleven factors of P-adic valuation one, four of valuation two, and one of valuation three: $11+2\cdot 4+3\cdot 1=22$. Thus $3^{22}$ divides $50!$, while $3^{23}$ does not.

Repeated Euclidean division provides a practical evaluation: replace $q$ by $\lfloor q/p\rfloor$, starting from $q=n$, and add each new quotient until it is zero. This uses only the successive quotients $16,5,1,0$ for the example. The same calculation handles divisibility of binomial coefficients, where the P-adic valuations of the denominator factorials are subtracted.

For a nonnegative integer $n$ and integer base $p\ge 2$, write its base-p expansion asThe base-$p$ digit sum is $d_p(n)={\sum }_r{\alpha }_r$, with $d_p(0)=0$. When $p$ is a prime number, the Legendre formula becomesTo see the connection, divide the base-p expansion by $p^j$ and discard the fractional part. Swapping the resulting finite sums and using a finite geometric series givesIn particular, $50=1\cdot 27+2\cdot 9+1\cdot 3+2=(1212{)}_3$, so $d_3(50)=6$ and $v_3(50!)=(50-6)/2=22$. The leading numeral digit contributes thirteen, the next contributes eight, the next one, and the units contribute zero. Thus the base-p digit sum compresses the same contribution ledger into information already present in positional notation.

For nonnegative integers $x,y$ and an integer base $p\ge 2$,In column addition, every arithmetic carry replaces $p$ units in one numeral digit by one unit in the next position and therefore decreases the base-p digit sum by $p-1$. Count each outgoing carry separately, including each step of a chain. There is equality precisely when there are no carries. For prime number bases, Kummer's theorem turns this digit-sum deficit into a prime exponent.

For a prime number $p$ and integers $0\le k\le n$, the P-adic valuation of the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ equals the number of arithmetic carries in the base-$p$ addition of $k$ and $n-k$.^[ref] Indeed, subtract the two denominator factorial valuations in the Legendre formula:Each arithmetic carry accounts for one unit of this quotient by subadditivity of the base-p digit sum. In particular, the binomial coefficient is divisible by $p$ exactly when at least one carry occurs.

For $n=50,k=17,p=3$, the factorial counts giveThe matching base-p expansions are $17=(0122{)}_3$ and $33=(1020{)}_3$. Their units add to two; the next column gives $2+2=4=1+3$, sending one carry into the nines column. That column then gives $1+0+1=2$, and no further carry occurs. The result is $(1212{)}_3=50$. The base-p digit sums check the same result: $(5+3-6)/(3-1)=1$. Consequently $\left(\genfrac{}{}{0ex}{}{50}{17}\right)$ is divisible by three but not by nine.

If $k\ge 1$ and $k+2\le p\le 2k+1$ is prime, thenIndeed, neither $(k+1)!$ nor $k!$ contains a factor $p$, while $(2k+1)!$ contains $p$ exactly once because $2p>2k+1$.