P-adic Numbers in Number Theory
Definition 1
A $p$-adic valuation for a prime number $p$ and an integer $a \in \mathbb{Z}$ is defined as follows with respect to $v_{p}$ and is represented as $a$ of $p$-adic valuation. $$ v_{p} (a) := \sup \left\{ e \in \mathbb{Z} : p^{e} \mid a \right\} $$
Theorem 2
- [0]: For every prime number $p$ $$ v_{p} (0) = \infty $$
- [1]: $$v_{p} (xy) = v_{p}(x) + v_{p}(y)$$
- [2]: $$v_{p} (x+y) \ge \min \left\{ v_{p} (x) , v_{p} (y) \right\}$$
- [3]: If $n \in \mathbb{N}$, $x , y \in \mathbb{Z}$, and prime number $p$ is $$ \gcd (n,p) = 1 \\ p \mid (x \mp y) \\ p \nmid x \\ p \nmid y $$ then $$ v_{p} \left( x^{n} \pm y^{n} \right) = v_{p} \left( x \pm y \right) $$
- [4]: If $x , y \in \mathbb{Z}$, prime number $p \ne 2$ is $$ p \mid (x - y) \\ p \nmid x \\ p \nmid y $$ then $$ v_{p} \left( x^{p} - y^{p} \right) = v_{p} \left( x - y \right) +1 $$
- $b \mid a$ represents that $b$ is a divisor of $a$.
- The term valuation means assigning a value, which could be directly translated into Korean as 값매김, but since both terms are somewhat lacking, it is recommended to use the English term Valuation.
Description
When I was taking an undergraduate course in cryptography, I noticed that the textbook used the form of quotient ring rather than the ring of integers modulo $p$, and I asked the professor why. He answered that it was to differentiate it from the research on $p$-adic numbers, which is a major branch in number theory. Studying the $p$-adic numbers might as well be opening a big curtain in the field of number theory.
Simply put, a $p$-adic valuation of a given natural number is nothing but looking at how many powers of $p$ are multiplied. For example, for a prime number $p = 3$, the $3$-adic valuation of $63 = 3^{2} \cdot 7^{1}$ is $v_{3} (63) = 2$, and $v_{7} (63) = 1$. On the other hand, for invisible numbers when factoring, for example, the $2$-adic valuation is trivially $2^{0} \mid 63$, so it’s $v_{2} (63) = 0$.
Proof
[0]
The fact that $b$ is a divisor of $a$, that is, $b \mid a$, means that there exists an integer $k \in \mathbb{Z}$ that satisfies $a k = b$. For all $e \in \mathbb{Z}$, there exists $ k = 0$ that satisfies $p^{e} \cdot k = 0$, so $\sup \left\{ e \in \mathbb{Z} : p^{e} \mid 0 \right\} = \infty$.
■
[1]
$v_{p}(a)$ is counting the power of $p$ in $a$, so naturally $v_{p} (xy) = v_{p}(x) + v_{p}(y)$ holds.
■
[2]
Let’s represent some $X,Y \in$ as the following for $x,y$. $$ x := p^{v_{p} (x) } X \\ y := p^{v_{p} (y) } Y $$ Without losing generality, if we set it as $v_{p} (x) \ge v_{p} (y)$, then $$ x+y = p^{v_{p}(y) } \left( p^{v_{p}(x) - v_{p}(y)} X + Y \right) $$ Therefore, we obtain at least $v_{p} (x+y) \ge v_{p}(y)$.
■
[3]3
Part 1.
If we factorize $x^{n} - y^{n}$, $$ x^{n} - y^{n} = (x-y) \left( x^{n-1} + x^{n-2} y + \cdots x y^{n-2} + y^{n-1} \right) $$ According to the definition of $v_{p}$, unless the second factor $\sum_{t = 0}^{n-1} x^{(n - 1)-t} y^{t}$ includes $p$ as a divisor, $v_{p} \left( x^{n} - y^{n} \right)$ or $ v_{p} \left( x - y \right)$ are the same. Writing this as an equation gives us: $$ v_{p} \left( x^{n} - y^{n} \right) = v_{p} \left( x - y \right) $$
Part 2. $v_{p} \left( x^{n} - y^{n} \right) = v_{p} \left( x - y \right)$
Since we assume $p \mid (x-y)$, we have $x - y \equiv 0 \pmod{p}$, namely $x \equiv y \pmod{p}$, so $$ \begin{align*} \sum_{t = 0}^{n-1} x^{(n - 1)-t} y^{t} \equiv& \sum_{t = 0}^{n-1} x^{(n - 1)-t} x^{t} \\ \equiv& n\cdot x^{n-1} \pmod{p} \end{align*} $$ However, assuming $p \nmid x$ and $\gcd (n,p) = 1$ gives $$ \sum_{t = 0}^{n-1} x^{(n - 1)-t} y^{t} \not\equiv 0 \pmod{p} $$ Therefore, we obtain the following: $$ v_{p} \left( x^{n} - y^{n} \right) = v_{p} \left( x - y \right) $$
Part 3. $v_{p} \left( x^{n} + y^{n} \right) = v_{p} \left( x + y \right)$
It does not go beyond a change in sign from the equation obtained in Part 2. Substituting $-y$ instead of $y$ gives $$ v_{p} \left( x^{n} - (-y)^{n} \right) = v_{p} \left( x - (-y) \right) $$ Thus, the following is obtained: $$ v_{p} \left( x^{n} + y^{n} \right) = v_{p} \left( x + y \right) $$
■
[4]
Part 1.
$$ v_{p} \left( x^{p} - y^{p} \right) = v_{p} \left( x - y \right) +1 $$ This means that when you factorize $(x-y)$ and $\left( x^{p} - y^{p} \right)$, $p$ is exactly added by $1$. To demonstrate this, let’s factorize $x^{p} - y^{p}$ in the same manner as in Proof [3]. $$ x^{p} - y^{p} = (x-y) \left( x^{p-1} + x^{p-2} y + \cdots x y^{p-2} + y^{p-1} \right) $$ That $p$ is exactly multiplied by $1$ means the second factor $\sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$ appears as a multiple of $p$ but not as a multiple of $p^{2}$. $$ p \mid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t} \\ p^{2} \nmid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t} $$
Part 2. $p \mid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$
Since we assume $p \mid (x-y)$, we have $x - y \equiv 0 \pmod{p}$, namely $x \equiv y \pmod{p}$, so $$ \begin{align*} \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t} \equiv& \sum_{t = 0}^{p-1} x^{(p - 1)-t} x^{t} \\ \equiv& p\cdot x^{p-1} \\ \equiv& 0 \pmod{p} \end{align*} $$ Therefore, it’s $p \mid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$.
Part 3. $p^{2} \nmid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$
Since it’s $x \equiv y \pmod{p}$, any $k \in \mathbb{Z}$ can be set as $y = x + kp$. Fixing the index as $t = 1, \cdots , p-1$ and expanding $x^{(p - 1)-t} y^{t}$ over $x$ gives us in $\pmod{p^{2}}$ $$ \begin{align*} x^{(p - 1)-t} y^{t} \equiv& x^{(p - 1)-t} \left( x + kp \right)^{t} \\ \equiv& x^{(p-1)-t} \left( x^{t} + t x^{t-1} kp + {{ t(t-1) } \over { 2 }} x^{t-2} k^{2} \cdot p^{2} + \cdots \right) \\ \equiv& x^{(p-1)-t} \left( x^{t} + t x^{t-1} kp \right) + O \left( p^{2} \right) \\ \equiv& x^{p-1} + tkpx^{p-2} \pmod{p^{2}} \end{align*} $$ Returning to the original series gives $$ \begin{align*} \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t} \equiv& \sum_{t = 0}^{p-1} \left[ x^{p-1} + tkpx^{p-2} \right] \\ \equiv& p x^{p-1} + {{ p(p-1) } \over { 2 }} kpx^{p-2} \\ \equiv& p x^{p-1} + {{ p-1 } \over { 2 }} k x^{p-2} \cdot p^{2} \\ \equiv& p x^{p-1} \pmod{p^{2}} \\ \not \equiv& 0 \pmod{p^{2}} \end{align*} $$ Therefore, it’s $p^{2} \mid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$.
■