文献あり

x-yがpの倍数でないときのLTEの補題

602

今回は，数学オリンピックなどで有名な「LTEの補題」のちょっとした別バージョンを発見したので，紹介したいと思います．(既出だったらごめんなさい)

まずは，普通のLTEの補題についてです．

LTEの補題 (Lifting-the-exponent lemma)

$p$ が奇素数， $x, y$ が $p$ と互いに素な異なる整数， $x \equiv y (\mod p)$ であるとき，正の整数 $n$ に対して
${ord}_{p} (x^{n} - y^{n}) = {ord}_{p} (x - y) + {ord}_{p} (n)$ が成り立つ．ただし， ${ord}_{p} (X)$ は整数 $X$ が $p$ で割り切れる回数(p進付値)を表す．

証明は色々なところに溢れているのでここでは省略します．

LTEの補題は，方程式の整数解を求める問題などで， $x^{n} - y^{n}$ の指数 $n$ を下から評価するのに使われる場合が多いです．しかし， $x \equiv y (\mod p)$ が成立しないとこの補題は使うことができません．そこで， $x \equiv y (\mod p)$ が成立しない場合にも使えるLTEの補題のようなものを考えたので，紹介します．

LTEの補題の別バージョン

$p$ が奇素数， $x, y$ が $p$ と互いに素な異なる整数， $n$ を正の整数とする． $x^{n} \equiv y^{n} (\mod p)$ であるとき，
${ord}_{p} (x^{n} - y^{n}) = {ord}_{p} (x^{p - 1} - y^{p - 1}) + {ord}_{p} (n)$ が成り立つ．

条件は $x \equiv y (\mod p)$ ではなく $x^{n} \equiv y^{n} (\mod p)$ なので，実質 $x, y$ がどんな値でも ${ord}_{p} (x^{n} - y^{n})$ を計算することができます，
また，右辺の $p - 1$ を， $x^{r} \equiv y^{r} (\mod p)$ なる最小の自然数 $r$ に書き換えても成立します．この主張は普通のLTEの補題の一般化になっています．

証明

まずは簡単な補題を用意します．
「 $\mod p$ において $x y^{- 1}$ の位数 $r$ を取る」と言って理解できる人は読み飛ばしてください．

$p$ を素数， $x, y$ を $p$ と互いに素な整数とする．

$x^{r} \equiv y^{r} (\mod p)$ なる最小の自然数 $r$ に対して，次が成立する．
(1) $x^{n} \equiv y^{n} (\mod p) ⟺ r ∣ n$
(2) $r ∣ (p - 1)$

合同式の法を $p$ とする．

まず(1)を示す．
$⟸$ については $x^{r} \equiv y^{r}$ の両辺を $\frac{n}{r}$ 乗すれば従う．
$⟹$ の対偶「 $r ∤ n ⟹ x^{n} ≢ y^{n}$ 」を示す．
$r ∤ n$ より， $k r < n < (k + 1) r$ なる整数 $k$ が取れる． $0 < n - k r < r$ より $r$ の最小性から
$x^{n - k r} ≢ y^{n - k r}$
$x^{k r} \equiv y^{k r}$ であり，この値は法 $p$ と互いに素なので，
$x^{n} ≢ y^{n}$
となる．したがって(1)は成立．

次に(2)を示す．フェルマーの小定理より，
$x^{p - 1} \equiv y^{p - 1} \equiv 1$
なので，(1)より，
$r ∣ (p - 1)$
であるから成立．

これを用いて，定理2の証明を行います．

合同式の法を $p$ とする． $x^{r} \equiv y^{r}$ なる最小の自然数 $r$ をとる．
$x^{n} \equiv y^{n}$ なので，補題3より自然数 $k$ を用いて $n = k r$ とおける．LTEの補題より，
${ord}_{p} (x^{n} - y^{n}) = {ord}_{p} (x^{k r} - y^{k r}) = {ord}_{p} (x^{r} - y^{r}) + {ord}_{p} (k)$

補題3より $r ∣ (p - 1)$ なので，自然数 $e$ を用いて $p - 1 = e r$ とおける．
よって， $r$ は $p$ と互いに素なので，
${ord}_{p} (k) = {ord}_{p} (k r) = {ord}_{p} (n)$
また， $p - 1 = e r$ より，

$x^{p - 1} - y^{p - 1} = x^{e r} - y^{e r} = (x^{r} - y^{r}) (x^{r (e - 1)} + x^{r (e - 2)} y^{r} + \dots + y^{r (e - 1)})$
$∴ {ord}_{p} (x^{r} - y^{r}) = {ord}_{p} (x^{p - 1} - y^{p - 1}) - {ord}_{p} (x^{r (e - 1)} + x^{r (e - 2)} y^{r} + \dots + y^{r (e - 1)})$
ここで， $x^{r} \equiv y^{r}$ なので，
$x^{r (e - 1)} + x^{r (e - 2)} y^{r} + \dots + y^{r (e - 1)} \equiv e x^{r (e - 1)}$
であり， $p - 1 = e r$ より $e$ は $p$ と互いに素，仮定より $x$ は $p$ と互いに素なので，
$e x^{r (e - 1)} ≢ 0$
よって，
${ord}_{p} (x^{r} - y^{r}) = {ord}_{p} (x^{p - 1} - y^{p - 1})$
以上より，
${ord}_{p} (x^{n} - y^{n}) = {ord}_{p} (x^{p - 1} - y^{p - 1}) + {ord}_{p} (n)$
が成り立つ．

追記(2023/5/24)

もっと簡単な証明を見つけてしまったので載せておきます

$x^{n} \equiv y^{n} (\mod p)$ なのでLTEの補題より
${ord}_{p} (x^{(p - 1) n} - y^{(p - 1) n}) = {ord}_{p} (x^{n} - y^{n}) + {ord}_{p} (p - 1) = {ord}_{p} (x^{n} - y^{n})$
また，フェルマーの小定理より $x^{p - 1} \equiv y^{p - 1} \equiv 1 (\mod p)$ なのでLTEの補題より，
${ord}_{p} (x^{n} - y^{n}) = {ord}_{p} (x^{(p - 1) n} - y^{(p - 1) n}) = {ord}_{p} (x^{p - 1} - y^{p - 1}) + {ord}_{p} (n)$