x-yがpの倍数でないときのLTEの補題
$\newcommand{\ord}{\mathrm{ord}}$
今回は，数学オリンピックなどで有名な「LTEの補題」のちょっとした別バージョンを発見したので，紹介したいと思います．(既出だったらごめんなさい)
まずは，普通のLTEの補題についてです．
$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$に変えても同じように証明できます．