📂Number Theory

P-adic Numbers in Number Theory

Definition ¹

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 ²

• [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]³

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}$.

■