Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

P-adic valuation: Difference between revisions

← Older edit
Enderr (talk | contribs)
editor
1 edit
Virajnirmal (talk | contribs)
editor
10 edits
No edit summary
 
Line 1: Line 1:
{{DISPLAYTITLE:''p''-adic valuation}}
{{DISPLAYTITLE:''p''-adic valuation}}
{{title restriction|<math>p</math>-adic valuation}}
{{title restriction|<imath>p</imath>-adic valuation}}


For some [[integer]] <math>n</math> and [[prime]] <math>p</math>, the '''<math>p</math>-adic valuation''' of n, denoted  <math>\nu_p(n)</math>, represents the largest power of <math>p</math> which [[divides]] <math>n</math>. In other words, it is the value of the exponent of <math>p</math> in the [[prime factorization]] of <math>n</math>.
For some [[integer]] <imath>n</imath> and [[prime]] <imath>p</imath>, the '''<imath>p</imath>-adic valuation''' of n, denoted  <imath>\nu_p(n)</imath>, represents the largest power of <imath>p</imath> which [[divides]] <imath>n</imath>. In other words, it is the value of the exponent of <imath>p</imath> in the [[prime factorization]] of <imath>n</imath>.


== Basic Examples ==
== Basic Examples ==
#<math>\nu_3(18)=\nu_3(2\cdot3^2)=2</math>.
#<imath>\nu_3(18)=\nu_3(2\cdot3^2)=2</imath>.
#<math>\nu_5(-5)=\nu_5(-1\cdot5^1)=1</math>.
#<imath>\nu_5(-5)=\nu_5(-1\cdot5^1)=1</imath>.
#<math>\nu_{13}(28)=\nu_{13}(2^2\cdot7\cdot13^0)=0</math>.
#<imath>\nu_{13}(28)=\nu_{13}(2^2\cdot7\cdot13^0)=0</imath>.


== Properties ==
== Properties ==
* For positive integers <math>x</math> and <math>y</math>, <cmath>\nu_p(xy)=\nu_p(x)+\nu_p(y).</cmath> This property follows from the fact that <math>p^ap^b=p^{a+b}</math>.
* For positive integers <imath>x</imath> and <imath>y</imath>, <cmath>\nu_p(xy)=\nu_p(x)+\nu_p(y).</cmath> This property follows from the fact that <imath>p^ap^b=p^{a+b}</imath>.
* Furthermore, <cmath>\nu_p(x+y)\geq\min{\nu_p(x)+\nu_p(y)}.</cmath> This follows because we can factor out <math>\min{\nu_p(x)+\nu_p(y)}</math> copies of <math>p</math> from the sum <math>x+y</math>. Note that equality holds if <math>\nu_p(x)\neq\nu_p(y)</math>, because, in this case, after factoring out <math>\min{\nu_p(x)+\nu_p(y)}</math> copies of <math>p</math> from the sum <math>x+y</math>, the remaining factor cannot be congruent to <math>0</math> [[modulo]] <math>p</math>, because one of the terms will be congruent to <math>0\pmod p</math>, while the other will not (because all common factors of <math>p</math> have already been factored out).
* Furthermore, <cmath>\nu_p(x+y)\geq\min{\nu_p(x)+\nu_p(y)}.</cmath> This follows because we can factor out <imath>\min{\nu_p(x)+\nu_p(y)}</imath> copies of <imath>p</imath> from the sum <imath>x+y</imath>. Note that equality holds if <imath>\nu_p(x)\neq\nu_p(y)</imath>, because, in this case, after factoring out <imath>\min{\nu_p(x)+\nu_p(y)}</imath> copies of <imath>p</imath> from the sum <imath>x+y</imath>, the remaining factor cannot be congruent to <imath>0</imath> [[modulo]] <imath>p</imath>, because one of the terms will be congruent to <imath>0\pmod p</imath>, while the other will not (because all common factors of <imath>p</imath> have already been factored out).
* If <math>n</math> is a positive integer, because <math>n\geq p^{\nu_p(n)}</math>, we deduce that <cmath>\nu_p(n)\leq \log_pn,</cmath> because [[logarithms]] are [[Sequence#Monotone Sequences|monotone increasing]] for all bases greater than <math>1</math>, which includes all primes.
* If <imath>n</imath> is a positive integer, because <imath>n\geq p^{\nu_p(n)}</imath>, we deduce that <cmath>\nu_p(n)\leq \log_pn,</cmath> because [[logarithms]] are [[Sequence#Monotone Sequences|monotone increasing]] for all bases greater than <imath>1</imath>, which includes all primes.
* [[Lifting the Exponent]]: A series of identities, among which the most prominent is: <cmath>\nu_p (x^n-y^n)=\nu_p (x-y)+\nu_p (n)</cmath> for odd primes <math>p</math> if <math>p|(x-y)</math>.
* [[Lifting the Exponent]]: A series of identities, among which the most prominent is: <cmath>\nu_p (x^n-y^n)=\nu_p (x-y)+\nu_p (n)</cmath> for odd primes <imath>p</imath> if <imath>p|(x-y)</imath>.
* [[Legendre's Formula]]: <math>\nu_p (n!)=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor</math>.
* [[Legendre's Formula]]: <imath>\nu_p (n!)=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor</imath>.


== Extension to Rational Numbers ==
== Extension to Rational Numbers ==
<math>\nu_p(0)</math> is defined to be [[infinite]].
<imath>\nu_p(0)</imath> is defined to be [[infinite]].


Furthermore, as seen in the properties above, <cmath>\nu_p(xy)=\nu_p(x)+\nu_p(y).</cmath> From this inspiration, we can define fractional inputs as follows: <cmath>\nu_p\left(\frac xy\right)=\nu_p(x)-\nu_p(y).</cmath> Note that it does not matter if <math>\tfrac xy</math> is simplified or not, because
Furthermore, as seen in the properties above, <cmath>\nu_p(xy)=\nu_p(x)+\nu_p(y).</cmath> From this inspiration, we can define fractional inputs as follows: <cmath>\nu_p\left(\frac xy\right)=\nu_p(x)-\nu_p(y).</cmath> Note that it does not matter if <imath>\tfrac xy</imath> is simplified or not, because
\begin{align*}
\begin{align*}
\nu_p\left(\frac{kx}{ky}\right) &= \nu_p(kx)-\nu_p(ky) \\
\nu_p\left(\frac{kx}{ky}\right) &= \nu_p(kx)-\nu_p(ky) \\

Latest revision as of 16:39, 9 November 2025

The title of this article has been capitalized due to technical restrictions. The correct title should be $p$-adic valuation.

For some integer $n$ and prime $p$, the $p$-adic valuation of n, denoted $\nu_p(n)$, represents the largest power of $p$ which divides $n$. In other words, it is the value of the exponent of $p$ in the prime factorization of $n$.

Basic Examples

  1. $\nu_3(18)=\nu_3(2\cdot3^2)=2$.
  2. $\nu_5(-5)=\nu_5(-1\cdot5^1)=1$.
  3. $\nu_{13}(28)=\nu_{13}(2^2\cdot7\cdot13^0)=0$.

Properties

  • For positive integers $x$ and $y$, \[\nu_p(xy)=\nu_p(x)+\nu_p(y).\] This property follows from the fact that $p^ap^b=p^{a+b}$.
  • Furthermore, \[\nu_p(x+y)\geq\min{\nu_p(x)+\nu_p(y)}.\] This follows because we can factor out $\min{\nu_p(x)+\nu_p(y)}$ copies of $p$ from the sum $x+y$. Note that equality holds if $\nu_p(x)\neq\nu_p(y)$, because, in this case, after factoring out $\min{\nu_p(x)+\nu_p(y)}$ copies of $p$ from the sum $x+y$, the remaining factor cannot be congruent to $0$ modulo $p$, because one of the terms will be congruent to $0\pmod p$, while the other will not (because all common factors of $p$ have already been factored out).
  • If $n$ is a positive integer, because $n\geq p^{\nu_p(n)}$, we deduce that \[\nu_p(n)\leq \log_pn,\] because logarithms are monotone increasing for all bases greater than $1$, which includes all primes.
  • Lifting the Exponent: A series of identities, among which the most prominent is: \[\nu_p (x^n-y^n)=\nu_p (x-y)+\nu_p (n)\] for odd primes $p$ if $p|(x-y)$.
  • Legendre's Formula: $\nu_p (n!)=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor$.

Extension to Rational Numbers

$\nu_p(0)$ is defined to be infinite.

Furthermore, as seen in the properties above, \[\nu_p(xy)=\nu_p(x)+\nu_p(y).\] From this inspiration, we can define fractional inputs as follows: \[\nu_p\left(\frac xy\right)=\nu_p(x)-\nu_p(y).\] Note that it does not matter if $\tfrac xy$ is simplified or not, because \begin{align*} \nu_p\left(\frac{kx}{ky}\right) &= \nu_p(kx)-\nu_p(ky) \\ &= (\nu_p(k)+\nu_p(x))-(\nu_p(k)+\nu_p(y)) \\ &=\nu_p(x)-\nu_p(y) \\ &=\nu_p\left(\frac xy\right). \end{align*}

See Also

This article is a stub. Help us out by expanding it.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=P-adic_valuation&oldid=268105"