p-adic number

Motivation[edit]

Roughly speaking, modular arithmetic modulo a positive integer n consists of "approximating" every integer by the remainder of its division by n, called its residue modulo n. The main property of modular arithmetic is that the residue modulo n of the result of a succession of operations on integers is the same as the result of the same succession of operations on residues modulo n. If one knows that the absolute value of the result is less than n/2, this allows a computation of the result which does not involve any integer larger than n.


For larger results, an old method, still in common use, consists of using several small moduli that are pairwise coprime, and applying the Chinese remainder theorem for recovering the result modulo the product of the moduli.


Another method discovered by Kurt Hensel consists of using a prime modulus p, and applying Hensel's lemma for recovering iteratively the result modulo ${\displaystyle p^{2},p^{3},\ldots ,p^{n},\ldots }$ If the process is continued infinitely, this provides eventually a result which is a p-adic number.

Definition[edit]

There are several equivalent definitions of p-adic numbers. The one that is given here is relatively elementary, since it does not involve any other mathematical concepts than those introduced in the preceding sections. Other equivalent definitions use completion of a discrete valuation ring (see § p-adic integers), completion of a metric space (see § Topological properties), or inverse limits (see § Modular properties).


A p-adic number can be defined as a normalized p-adic series. Since there are other equivalent definitions that are commonly used, one says often that a normalized p-adic series represents a p-adic number, instead of saying that it is a p-adic number.


One can say also that any p-adic series represents a p-adic number, since every p-adic series is equivalent to a unique normalized p-adic series. This is useful for defining operations (addition, subtraction, multiplication, division) of p-adic numbers: the result of such an operation is obtained by normalizing the result of the corresponding operation on series. This well defines operations on p-adic numbers, since the series operations are compatible with equivalence of p-adic series.


With these operations, p-adic numbers form a field called the field of p-adic numbers and denoted ${\displaystyle \mathbb {Q} _{p}}$ or ${\displaystyle \mathbf {Q} _{p}.}$ There is a unique field homomorphism from the rational numbers into the p-adic numbers, which maps a rational number to its p-adic expansion. The image of this homomorphism is commonly identified with the field of rational numbers. This allows considering the p-adic numbers as an extension field of the rational numbers, and the rational numbers as a subfield of the p-adic numbers.


The valuation of a nonzero p-adic number x, commonly denoted ${\displaystyle v_{p}(x),}$ is the exponent of p in the first nonzero term of every p-adic series that represents x. By convention, ${\displaystyle v_{p}(0)=\infty ;}$ that is, the valuation of zero is ${\displaystyle \infty .}$ This valuation is a discrete valuation. The restriction of this valuation to the rational numbers is the p-adic valuation of ${\displaystyle \mathbb {Q} ,}$ that is, the exponent v in the factorization of a rational number as ${\displaystyle {\tfrac {n}{d}}p^{v},}$ with both n and d coprime with p.

The p-adic integers are the p-adic numbers with a nonnegative valuation.


A p-adic integer can be represented as a sequence


of residues x_e mod p^e for each integer e, satisfying the compatibility relations ${\displaystyle x_{i}\equiv x_{j}~(\operatorname {mod} p^{i})}$ for i < j.


Every integer is a p-adic integer (including zero, since ${\displaystyle 0<\infty }$). The rational numbers of the form ${\textstyle {\tfrac {n}{d}}p^{k}}$ with d coprime with p and ${\displaystyle k\geq 0}$ are also p-adic integers (for the reason that d has an inverse mod p^e for every e).


The p-adic integers form a commutative ring, denoted ${\displaystyle \mathbb {Z} _{p}}$ or ${\displaystyle \mathbf {Z} _{p}}$, that has the following properties.


The last property provides a definition of the p-adic numbers that is equivalent to the above one: the field of the p-adic numbers is the field of fractions of the completion of the localization of the integers at the prime ideal generated by p.

The p-adic valuation allows defining an absolute value on p-adic numbers: the p-adic absolute value of a nonzero p-adic number x is


where ${\displaystyle v_{p}(x)}$ is the p-adic valuation of x. The p-adic absolute value of ${\displaystyle 0}$ is ${\displaystyle |0|_{p}=0.}$ This is an absolute value that satisfies the strong triangle inequality since, for every x and y one has


Moreover, if ${\displaystyle |x|_{p}\neq |y|_{p},}$ one has ${\displaystyle |x+y|_{p}=\max(|x|_{p},|y|_{p}).}$


This makes the p-adic numbers a metric space, and even an ultrametric space, with the p-adic distance defined by ${\displaystyle d_{p}(x,y)=|x-y|_{p}.}$


As a metric space, the p-adic numbers form the completion of the rational numbers equipped with the p-adic absolute value. This provides another way for defining the p-adic numbers. However, the general construction of a completion can be simplified in this case, because the metric is defined by a discrete valuation (in short, one can extract from every Cauchy sequence a subsequence such that the differences between two consecutive terms have strictly decreasing absolute values; such a subsequence is the sequence of the partial sums of a p-adic series, and thus a unique normalized p-adic series can be associated to every equivalence class of Cauchy sequences; so, for building the completion, it suffices to consider normalized p-adic series instead of equivalence classes of Cauchy sequences).


As the metric is defined from a discrete valuation, every open ball is also closed. More precisely, the open ball ${\displaystyle B_{r}(x)=\{y\mid d_{p}(x,y)<r\}}$ equals the closed ball ${\displaystyle B_{p^{-v}}[x]=\{y\mid d_{p}(x,y)\leq p^{-v}\},}$ where v is the least integer such that ${\displaystyle p^{-v}<r.}$ Similarly, ${\displaystyle B_{r}[x]=B_{p^{-w}}(x),}$ where w is the greatest integer such that ${\displaystyle p^{-w}>r.}$


This implies that the p-adic numbers form a locally compact space, and the p-adic integers—that is, the ball ${\displaystyle B_{1}[0]=B_{p}(0)}$—form a compact space.

Modular properties[edit]

The quotient ring ${\displaystyle \mathbb {Z} _{p}/p^{n}\mathbb {Z} _{p}}$ may be identified with the ring ${\displaystyle \mathbb {Z} /p^{n}\mathbb {Z} }$ of the integers modulo ${\displaystyle p^{n}.}$ This can be shown by remarking that every p-adic integer, represented by its normalized p-adic series, is congruent modulo ${\displaystyle p^{n}}$ with its partial sum ${\textstyle \sum _{i=0}^{n-1}a_{i}p^{i},}$ whose value is an integer in the interval ${\displaystyle [0,p^{n}-1].}$ A straightforward verification shows that this defines a ring isomorphism from ${\displaystyle \mathbb {Z} _{p}/p^{n}\mathbb {Z} _{p}}$ to ${\displaystyle \mathbb {Z} /p^{n}\mathbb {Z} .}$


The inverse limit of the rings ${\displaystyle \mathbb {Z} _{p}/p^{n}\mathbb {Z} _{p}}$ is defined as the ring formed by the sequences ${\displaystyle a_{0},a_{1},\ldots }$ such that ${\displaystyle a_{i}\in \mathbb {Z} /p^{i}\mathbb {Z} }$ and ${\textstyle a_{i}\equiv a_{i+1}{\pmod {p^{i}}}}$ for every i.


The mapping that maps a normalized p-adic series to the sequence of its partial sums is a ring isomorphism from ${\displaystyle \mathbb {Z} _{p}}$ to the inverse limit of the ${\displaystyle \mathbb {Z} _{p}/p^{n}\mathbb {Z} _{p}.}$ This provides another way for defining p-adic integers (up to an isomorphism).


This definition of p-adic integers is specially useful for practical computations, as allowing building p-adic integers by successive approximations.


For example, for computing the p-adic (multiplicative) inverse of an integer, one can use Newton's method, starting from the inverse modulo p; then, each Newton step computes the inverse modulo ${\textstyle p^{n^{2}}}$ from the inverse modulo ${\textstyle p^{n}.}$


The same method can be used for computing the p-adic square root of an integer that is a quadratic residue modulo p. This seems to be the fastest known method for testing whether a large integer is a square: it suffices to test whether the given integer is the square of the value found in ${\displaystyle \mathbb {Z} _{p}/p^{n}\mathbb {Z} _{p}}$. Applying Newton's method to find the square root requires ${\textstyle p^{n}}$ to be larger than twice the given integer, which is quickly satisfied.


Hensel lifting is a similar method that allows to "lift" the factorization modulo p of a polynomial with integer coefficients to a factorization modulo ${\textstyle p^{n}}$ for large values of n. This is commonly used by polynomial factorization algorithms.