📂整数論

数論におけるp-進数

定義 ¹

素数 $p$ と整数 $a \in \mathbb{Z}$ に対して次のように定義された $v_{p}$ を $a$ の $p$-進付値と言う。 $$v_{p} (a) := \sup \left\{ e \in \mathbb{Z} : p^{e} \mid a \right\}$$

定理 ²

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

パート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}$ である。

■