6
競技数学解説
文献あり

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

542
0
$$$$

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

まずは,普通のLTEの補題についてです.

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

$p$が奇素数,$x,y$$p$と互いに素な異なる整数,$x\equiv y \pmod{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 \pmod{p}$が成立しないとこの補題は使うことができません.そこで,$x\equiv y \pmod{p}$が成立しない場合にも使えるLTEの補題のようなものを考えたので,紹介します.

LTEの補題の別バージョン

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

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

証明

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

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

$x^r\equiv y^r \pmod{p}$なる最小の自然数$r$に対して,次が成立する.
(1) $x^n\equiv y^n \pmod{p} \Longleftrightarrow r \mid n$
(2) $r \mid (p-1)$

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

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

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

これを用いて,定理2の証明を行います.

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

補題3より$r \mid (p-1)$なので,自然数$e$を用いて$p-1=er$とおける.
よって,$r$$p$と互いに素なので,
$$\ord_p(k)=\ord_p(kr)=\ord_p(n)$$
また,$p-1=er$より,

$$ x^{p-1}-y^{p-1} =x^{er}-y^{er} = (x^r-y^r)(x^{r(e-1)}+x^{r(e-2)}y^{r}+\cdots+y^{r(e-1)}) $$
$$ \therefore \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}+\cdots+y^{r(e-1)}) $$
ここで,$x^r\equiv y^r$なので,
$$x^{r(e-1)}+x^{r(e-2)}y^{r}+\cdots+y^{r(e-1)}\equiv ex^{r(e-1)}$$
であり,$p-1=er$より$e$$p$と互いに素,仮定より$x$$p$と互いに素なので,
$$ex^{r(e-1)}\not\equiv 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 \pmod 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}≡y^{p-1}≡1 \pmod 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)$$

$p-1$$r$に変えても同じように証明できます.

参考文献

投稿日:2023523

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

dragoemon
dragoemon
127
26764
大学二年生です

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中