数論におけるp-進数
定義 1
素数 $p$ と整数 $a \in \mathbb{Z}$ に対して次のように定義された $v_{p}$ を $a$ の $p$-進付値と言う。 $$ 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$ の整数環ではなく、わざわざ商環の形を使っているのを見て、なぜそうなのか教授に質問したことがある。その時、教授はそれが数論では主に使われる $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
パート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) $$
パート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) $$
パート3. $v_{p} \left( x^{n} + y^{n} \right) = v_{p} \left( x + y \right)$
パート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]
パート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} $$
パート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}$ である。
パート3. $p^{2} \nmid \sum_{t = 0}^{p-1} x^{(p - 1)-t} y^{t}$
$x \equiv y \pmod{p}$ なので、$y = x + kp$ として$k \in \mathbb{Z}$ を設定できる。$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}$ である。
■