수론에서의 p-진수
정의 1
소수 $p$ 와 정수 $a \in \mathbb{Z}$ 에 대해 다음과 같이 정의된 $v_{p}$ 를 $a$ 의 $p$-진수 부치$p$-adic Valuation라 한다. $$ v_{p} (a) := \sup \left\{ e \in \mathbb{Z} : p^{e} \mid a \right\} $$
정리 2
- [0]: 모든 소수 $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]: $n \in \mathbb{N}$, $x , y \in \mathbb{Z}$, 소수 $p$ 가 $$ \gcd (n,p) = 1 \\ p \mid (x \mp y) \\ p \nmid x \\ p \nmid y $$ 를 만족하면 $$ v_{p} \left( x^{n} \pm y^{n} \right) = v_{p} \left( x \pm y \right) $$
- [4]: $x , y \in \mathbb{Z}$, 소수 $p \ne 2$ 가 $$ p \mid (x - y) \\ p \nmid x \\ p \nmid y $$ 를 만족하면 $$ v_{p} \left( x^{p} - y^{p} \right) = v_{p} \left( x - y \right) +1 $$
- $b \mid a$ 는 $b$ 가 $a$ 의 약수임을 나타낸다.
- 부치賦値 란 값을 준다는 의미로, 순우리말로는 값매김이라도 순화된다. 둘 다 별로이므로 영어 그대로 Valuation 이라 읽는 것을 권장한다.
설명
학부 암호론을 들을 시절, 교재에서 모듈로 $p$ 의 정수환을 나타낼 때 $\mathbb{Z}_{p}$ 가 아니라 굳이 몫환꼴인 $\mathbb{Z} / p \mathbb{Z}$ 을 사용하는 걸 보고 왜 그런지 교수님께 질문을 드린 적이 있다. 당시 교수님은 $\mathbb{Z}_{p}$ 가 정수론에서는 $p$-진수의 연구라고 하는 큰 분과에서 주로 사용되기 때문에 그와 구분하기 위하기 위함이라고 답해주셨다. 진수를 공부한다는 것은 그만큼 정수론의 큰 막을 여는 일이 될지도 모르겠다.
$p$-진수 부치라는 것은 쉽게 말해 주어진 자연수에서 $p$ 의 거듭제곱이 몇승으로 곱해져있는지를 보는 것과 다름 없다. 가령 소수 $p = 3$ 에 대해서 $63 = 3^{2} \cdot 7^{1}$ 의 $3$-진수 부치는 $v_{3} (63) = 2$ 고, $v_{7} (63) = 1$ 이다. 한편 소인수분해를 했을 때 보이지 않는 수, 예로써 $2$-진수 부치는 자명하게도 $2^{0} \mid 63$ 이므로 $v_{2} (63) = 0$ 이다.
증명
[0]
$b$ 가 $a$ 의 약수라는 것, 다시 말해 $b \mid a$ 이라는 것은 $a k = b$ 를 만족시키는 정수 $k \in \mathbb{Z}$ 가 존재한다는 것이다. 모든 $e \in \mathbb{Z}$ 에 대해 $p^{e} \cdot k = 0$ 를 만족시키는 $ k = 0$ 이 존재하므로 $\sup \left\{ e \in \mathbb{Z} : p^{e} \mid 0 \right\} = \infty$ 이다.
■
[1]
$v_{p}(a)$ 는 $a$ 에서 $p$ 의 거듭제곱을 세는 것이므로, 당연히 $v_{p} (xy) = v_{p}(x) + v_{p}(y)$ 이 성립한다.
■
[2]
어떤 $X,Y \in$ 에 대해 $x,y$ 를 다음과 같이 나타내보자. $$ x := p^{v_{p} (x) } X \\ y := p^{v_{p} (y) } Y $$ 일반성을 잃지 않고, $v_{p} (x) \ge v_{p} (y)$ 라고 두면 $$ x+y = p^{v_{p}(y) } \left( p^{v_{p}(x) - v_{p}(y)} X + Y \right) $$ 따라서 적어도 $v_{p} (x+y) \ge v_{p}(y)$ 를 얻는다.
■
[3]3
Part 1.
$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) $$ 여기서 $v_{p}$ 의 정의에 따라 두번째 인수 $\sum_{t = 0}^{n-1} x^{(n - 1)-t} y^{t}$ 가 $p$ 를 약수로 가지지만 않으면 $v_{p} \left( x^{n} - y^{n} \right)$ 이나 $ v_{p} \left( x - y \right)$ 이나 같다. 이를 수식으로 적으면 다음과 같다. $$ 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)$
$p \mid (x-y)$ 라고 가정했으므로 $x - y \equiv 0 \pmod{p}$ 이고, 즉 $x \equiv y \pmod{p}$ 이므로 $$ \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*} $$ 그런데 $p \nmid x$ 이고 $\gcd (n,p) = 1$ 이라고 가정했으므로 $$ \sum_{t = 0}^{n-1} x^{(n - 1)-t} y^{t} \not\equiv 0 \pmod{p} $$ 따라서 다음을 얻는다. $$ 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)$
이미 Part 2.에서 얻은 등식에서 부호만 바뀌는 것에 지나지 않는다. $y$ 대신 $-y$ 를 대입하면 $$ v_{p} \left( x^{n} - (-y)^{n} \right) = v_{p} \left( x - (-y) \right) $$ 즉, 다음을 얻는다. $$ 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 $$ 라는 것은 $(x-y)$ 와 $\left( x^{p} - y^{p} \right)$ 를 소인수분해 했을 때 $p$ 가 정확히 $1$ 만큼 더 곱해져있다는 것과 동치다. 이를 보이기 위해 **증명[3]**과 마찬가지로 $x^{p} - y^{p}$ 을 인수분해해보자. $$ x^{p} - y^{p} = (x-y) \left( x^{p-1} + x^{p-2} y + \cdots x y^{p-2} + y^{p-1} \right) $$ $p$ 가 정확히 $1$ 만큼 더 곱해져있다는 것은 두번째 인수 $\sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$ 가 다음과 같이 $p$ 의 배수로는 나타나되 $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}$
$p \mid (x-y)$ 라고 가정했으므로 $x - y \equiv 0 \pmod{p}$ 이고, 즉 $x \equiv y \pmod{p}$ 이므로 $$ \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*} $$ 따라서 $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}$
$x \equiv y \pmod{p}$ 이므로 어떤 $k \in \mathbb{Z}$ 에 대해 $y = x + kp$ 로 둘 수 있다. $t = 1, \cdots , p-1$ 와 같이 인덱스를 픽스해두고 $x^{(p - 1)-t} y^{t}$ 를 $x$ 에 대해 전개해보면 $\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*} $$ 다시 원래의 급수로 돌아가보면 $$ \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*} $$ 따라서 $p^{2} \mid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$ 이다.
■