Highest power of p dividing a given number
In number theory , the p -adic valuation or p -adic order of an integer n is the exponent of the highest power of the prime number p that divides n . It is denoted ν p ( n ) {\displaystyle \nu _{p}(n)} . Equivalently, ν p ( n ) {\displaystyle \nu _{p}(n)} is the exponent to which p {\displaystyle p} appears in the prime factorization of n {\displaystyle n} .
The p -adic valuation is a valuation and gives rise to an analogue of the usual absolute value . Whereas the completion of the rational numbers with respect to the usual absolute value results in the real numbers R {\displaystyle \mathbb {R} } , the completion of the rational numbers with respect to the p {\displaystyle p} -adic absolute value results in the p -adic numbers Q p {\displaystyle \mathbb {Q} _{p}} .[ 1]
Distribution of natural numbers by their 2-adic valuation, labeled with corresponding powers of two in decimal. Zero has an infinite valuation. Definition and properties [ edit ] Let p be a prime number .
The p -adic valuation of an integer n {\displaystyle n} is defined to be
ν p ( n ) = { m a x { k ∈ N 0 : p k ∣ n } if n ≠ 0 ∞ if n = 0 , {\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 N 0 {\displaystyle \mathbb {N} _{0}} denotes the set of natural numbers (including zero) and m ∣ n {\displaystyle m\mid n} denotes divisibility of n {\displaystyle n} by m {\displaystyle m} . In particular, ν p {\displaystyle \nu _{p}} is a function ν p : Z → N 0 ∪ { ∞ } {\displaystyle \nu _{p}\colon \mathbb {Z} \to \mathbb {N} _{0}\cup \{\infty \}} .[ 2]
For example, ν 2 ( − 12 ) = 2 {\displaystyle \nu _{2}(-12)=2} , ν 3 ( − 12 ) = 1 {\displaystyle \nu _{3}(-12)=1} , and ν 5 ( − 12 ) = 0 {\displaystyle \nu _{5}(-12)=0} since | − 12 | = 12 = 2 2 ⋅ 3 1 ⋅ 5 0 {\displaystyle |{-12}|=12=2^{2}\cdot 3^{1}\cdot 5^{0}} .
The notation p k ∥ n {\displaystyle p^{k}\parallel n} is sometimes used to mean k = ν p ( n ) {\displaystyle k=\nu _{p}(n)} .[ 3]
If n {\displaystyle n} is a positive integer, then
ν p ( n ) ≤ log p n {\displaystyle \nu _{p}(n)\leq \log _{p}n} ; this follows directly from n ≥ p ν p ( n ) {\displaystyle n\geq p^{\nu _{p}(n)}} .
The p -adic valuation can be extended to the rational numbers as the function
ν p : Q → Z ∪ { ∞ } {\displaystyle \nu _{p}:\mathbb {Q} \to \mathbb {Z} \cup \{\infty \}} [ 4] [ 5] defined by
ν p ( r s ) = ν p ( r ) − ν p ( s ) . {\displaystyle \nu _{p}\left({\frac {r}{s}}\right)=\nu _{p}(r)-\nu _{p}(s).} For example, ν 2 ( 9 8 ) = − 3 {\displaystyle \nu _{2}{\bigl (}{\tfrac {9}{8}}{\bigr )}=-3} and ν 3 ( 9 8 ) = 2 {\displaystyle \nu _{3}{\bigl (}{\tfrac {9}{8}}{\bigr )}=2} since 9 8 = 2 − 3 ⋅ 3 2 {\displaystyle {\tfrac {9}{8}}=2^{-3}\cdot 3^{2}} .
Some properties are:
ν p ( r ⋅ s ) = ν p ( r ) + ν p ( s ) {\displaystyle \nu _{p}(r\cdot s)=\nu _{p}(r)+\nu _{p}(s)} ν p ( r + s ) ≥ min { ν p ( r ) , ν p ( s ) } {\displaystyle \nu _{p}(r+s)\geq \min {\bigl \{}\nu _{p}(r),\nu _{p}(s){\bigr \}}} Moreover, if ν p ( r ) ≠ ν p ( s ) {\displaystyle \nu _{p}(r)\neq \nu _{p}(s)} , then
ν p ( r + s ) = min { ν p ( r ) , ν p ( s ) } {\displaystyle \nu _{p}(r+s)=\min {\bigl \{}\nu _{p}(r),\nu _{p}(s){\bigr \}}} where min {\displaystyle \min } is the minimum (i.e. the smaller of the two).
Legendre's formula shows that:
ν p ( n ! ) = ∑ i = 1 ∞ ⌊ n p i ⌋ {\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty {}}{\lfloor {\frac {n}{p^{i}}}\rfloor {}}} . For any positive integer n , n = n ! ( n − 1 ) ! {\displaystyle n={\frac {n!}{(n-1)!}}} and ν p ( n ) = ν p ( n ! ) − ν p ( ( n − 1 ) ! ) {\displaystyle \nu _{p}(n)=\nu _{p}(n!)-\nu _{p}((n-1)!)} .
Therefore, ν p ( n ) = ∑ i = 1 ∞ ( ⌊ n p i ⌋ − ⌊ n − 1 p i ⌋ ) {\displaystyle \nu {}_{p}(n)=\sum _{i=1}^{\infty {}}{{\bigg (}\lfloor {\frac {n}{p^{i}}}\rfloor {}-\lfloor {\frac {n-1}{p^{i}}}\rfloor {}{\bigg )}}} .
This infinite sum can be reduced to ∑ i = 1 ⌊ log p ( n ) ⌋ ( ⌊ n p i ⌋ − ⌊ n − 1 p i ⌋ ) {\displaystyle \sum _{i=1}^{\lfloor {\log _{p}{(n)}\rfloor {}}}{{\bigg (}\lfloor {\frac {n}{p^{i}}}\rfloor {}-\lfloor {\frac {n-1}{p^{i}}}\rfloor {}{\bigg )}}} .
This formula can be extended to negative integer values to give:
ν p ( n ) = ∑ i = 1 ⌊ log p ( | n | ) ⌋ ( ⌊ | n | p i ⌋ − ⌊ | n | − 1 p i ⌋ ) {\displaystyle \nu {}_{p}(n)=\sum _{i=1}^{\lfloor {\log _{p}{(|n|)}\rfloor {}}}{{\bigg (}\lfloor {\frac {|n|}{p^{i}}}\rfloor {}-\lfloor {\frac {|n|-1}{p^{i}}}\rfloor {}{\bigg )}}}
p -adic absolute value[ edit ]
The p -adic absolute value (or p -adic norm,[ 6] though not a norm in the sense of analysis) on Q {\displaystyle \mathbb {Q} } is the function
| ⋅ | p : Q → R ≥ 0 {\displaystyle |\cdot |_{p}\colon \mathbb {Q} \to \mathbb {R} _{\geq 0}} defined by
| r | p = p − ν p ( r ) . {\displaystyle |r|_{p}=p^{-\nu _{p}(r)}.} Thereby, | 0 | p = p − ∞ = 0 {\displaystyle |0|_{p}=p^{-\infty }=0} for all p {\displaystyle p} and for example, | − 12 | 2 = 2 − 2 = 1 4 {\displaystyle |{-12}|_{2}=2^{-2}={\tfrac {1}{4}}} and | 9 8 | 2 = 2 − ( − 3 ) = 8. {\displaystyle {\bigl |}{\tfrac {9}{8}}{\bigr |}_{2}=2^{-(-3)}=8.}
The p -adic absolute value satisfies the following properties.
Non-negativity | r | p ≥ 0 {\displaystyle |r|_{p}\geq 0} Positive-definiteness | r | p = 0 ⟺ r = 0 {\displaystyle |r|_{p}=0\iff r=0} Multiplicativity | r s | p = | r | p | s | p {\displaystyle |rs|_{p}=|r|_{p}|s|_{p}} Non-Archimedean | r + s | p ≤ max ( | r | p , | s | p ) {\displaystyle |r+s|_{p}\leq \max \left(|r|_{p},|s|_{p}\right)}
From the multiplicativity | r s | p = | r | p | s | p {\displaystyle |rs|_{p}=|r|_{p}|s|_{p}} it follows that | 1 | p = 1 = | − 1 | p {\displaystyle |1|_{p}=1=|-1|_{p}} for the roots of unity 1 {\displaystyle 1} and − 1 {\displaystyle -1} and consequently also | − r | p = | r | p . {\displaystyle |{-r}|_{p}=|r|_{p}.} The subadditivity | r + s | p ≤ | r | p + | s | p {\displaystyle |r+s|_{p}\leq |r|_{p}+|s|_{p}} follows from the non-Archimedean triangle inequality | r + s | p ≤ max ( | r | p , | s | p ) {\displaystyle |r+s|_{p}\leq \max \left(|r|_{p},|s|_{p}\right)} .
The choice of base p in the exponentiation p − ν p ( r ) {\displaystyle p^{-\nu _{p}(r)}} makes no difference for most of the properties, but supports the product formula:
∏ 0 , p | r | p = 1 {\displaystyle \prod _{0,p}|r|_{p}=1} where the product is taken over all primes p and the usual absolute value, denoted | r | 0 {\displaystyle |r|_{0}} . This follows from simply taking the prime factorization : each prime power factor p k {\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 Q {\displaystyle \mathbb {Q} } with a (non-Archimedean , translation-invariant ) metric
d : Q × Q → R ≥ 0 {\displaystyle d\colon \mathbb {Q} \times \mathbb {Q} \to \mathbb {R} _{\geq 0}} defined by
d ( r , s ) = | r − s | p . {\displaystyle d(r,s)=|r-s|_{p}.} The completion of Q {\displaystyle \mathbb {Q} } with respect to this metric leads to the set Q p {\displaystyle \mathbb {Q} _{p}} of p -adic numbers.
^ ^ Ireland, K.; Rosen, M. (2000). A Classical Introduction to Modern Number Theory . New York: Springer-Verlag. p. 3. [ISBN missing ] ^ Niven, Ivan ; Zuckerman, Herbert S.; Montgomery, Hugh L. (1991). An Introduction to the Theory of Numbers (5th ed.). John Wiley & Sons . p. 4. ISBN 0-471-62546-9 . ^ with the usual order relation, namely ∞ > n {\displaystyle \infty >n} , and rules for arithmetic operations, ∞ + n = n + ∞ = ∞ {\displaystyle \infty +n=n+\infty =\infty } , on the extended number line. ^ Khrennikov, A.; Nilsson, M. (2004). p -adic Deterministic and Random Dynamics . Kluwer Academic Publishers. p. 9. [ISBN missing ] ^ Murty, M. Ram (2001). Problems in analytic number theory . Graduate Texts in Mathematics. Vol. 206. Springer-Verlag, New York. pp. 147–148. doi :10.1007/978-1-4757-3441-6 . ISBN 0-387-95143-1 . MR 1803093 .