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
During AMC testing, the AoPS Wiki is in read-only mode and no edits can be made.

Difference between revisions of "P-adic valuation"

(Created page with "{{title restriction|<math>p</math>-adic valuation}} For some integer <math>n</math> and prime <math>p</math>, the '''<math>p</math>-adic valuation''' of n, denoted <...")
 
(→‎Basic Examples)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
{{DISPLAYTITLE:''p''-adic valuation}}
 
{{title restriction|<math>p</math>-adic valuation}}
 
{{title restriction|<math>p</math>-adic valuation}}
  
Line 5: Line 6:
 
== Basic Examples ==
 
== Basic Examples ==
 
#<math>\nu_3(18)=\nu_3(2\cdot3^2)=2</math>.
 
#<math>\nu_3(18)=\nu_3(2\cdot3^2)=2</math>.
−
#<math>\nu_5(-5)=\nu_5(-1\cdot5^1)=5</math>.
+
#<math>\nu_5(-5)=\nu_5(-1\cdot5^1)=1</math>.
 
#<math>\nu_{13}(28)=\nu_{13}(2^2\cdot7\cdot13^0)=0</math>.
 
#<math>\nu_{13}(28)=\nu_{13}(2^2\cdot7\cdot13^0)=0</math>.
  
Line 27: Line 28:
  
 
== See Also ==
 
== See Also ==
−
*[[Lifting the Exponent]]
+
* [[Lifting the Exponent]]
−
*[[Legendre's Formula]]
+
* [[Legendre's Formula]]
−
*[[p-adic number]]
+
* [[p-adic number]]
 +
 
 
[[Category: Number theory]]
 
[[Category: Number theory]]
 +
[[Category:Definition]]
 +
{{stub}}

Latest revision as of 23:05, 1 October 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://artofproblemsolving.com/wiki/index.php?title=P-adic_valuation&oldid=262148"