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 .