LTEの補題について書きます！！備忘録(´・ω・｀)

どーも(´・ω・｀)ﾉｼ

独り言ドーン(ﾉ °ω° )ﾉ

昨日の記事が結構ヘビーな内容だったから何書いていいか迷ったんですけどね(；・∀・)
アレに匹敵するものだったら……整数問題の花形「LTEの補題」！！
これしかない！と思ったので書きます
思い立ったら即実行って事で…(´・ω・｀)
LTEの補題は一部のオタク気質な人たちの間では割りかし有名みたいで、ググれば記事を書いている人がちらほら見受けられます
なので今さら記事として取り上げる必要も無いかな〜とも思ったのですが、自力で証明を書き直すことで理解が深まるだろうし、備忘録として書いてみるのもいいかも！(´･∀･｀)
という訳で書きます

LTEの補題ってなんぞや(ﾟДﾟ#)ｱｧ？

[定理]
ある奇素数 $p$ がある整数 $x,y$ を割り切らず、 $(x-y)$ を割り切るとき、以下が成り立つ。
$\displaystyle \mathcal{ord}_p {(x^n-y^n)}=\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p n$

Lifting The Exponent Lemmaとかいうのだったと思います(´・ω・｀)
$\displaystyle \mathcal{ord}_p n$ というのは「素数 $p$ に関する $n$ のオーダー」と言い、 $n$ が何回 $p$ で割り切れるか、を表したものです
$p=2$ の場合も考えることが出来ます(後述)
ググれば誰が思いついたーとか出てくると思うので省略！！
|ω・`).｡oO(知らないとか言えない)

さっそく証明しようず(´^p^`)

帰納法でやるのが一般的だと思います
それ以外では出来ないんじゃない？知らないけど←ヾ(･Д･`)ｵｲ
方針としては、

$n=p$ の場合に成り立つことを示す
$n$ と $p$ が互いに素の場合に成り立つことを示す
$n=ap^k$ の時に成り立つことを示す(ここで帰納法)

というステップを踏みます
最初は何も見ないで記憶をたよりに書きます(´・ω・｀)

[証明]

ある奇素数 $p$ がある整数 $x,y$ を割り切らず、 $(x-y)$ を割り切るとき、
$\displaystyle \mathcal{ord}_p {(x^n-y^n)}=\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p n$
が成り立つことを示す。
⑴ $n=p$ の場合
$\displaystyle x^p-y^p=(x-y)(x^{p-1}+x^{p-2} y+\cdots +y^{p-1})$
ここで、 $\displaystyle y \equiv \ x+mp \ \mathcal{mod} \ p^2$ であり、
$\displaystyle x^{p-1}+x^{p-2} y+\cdots +y^{p-1}\\ \displaystyle =\sum_{k=0}^{p-1}x^{p-1-k}y^k\\ \displaystyle \equiv \sum_{k=0}^{p-1}x^{p-1-k}\sum_{l=0}^{k}x^{k-l}p^l m^l {}_k \mathrm{C}_l\\ \displaystyle =\sum_{k=0}^{p-1} \sum_{l=0}^{k}x^{p-1-l}p^l m^l {}_k \mathrm{C}_l\\ \displaystyle = \sum_{l=0}^{p-1}\sum_{k=l}^{p-1}x^{p-1-l}p^l m^l {}_k \mathrm{C}_l\\ \displaystyle \equiv\sum_{k=0}^{p-1}x^{p-1}+\sum_{k=1}^{p-1}x^{p-2}pmk\\ \displaystyle \equiv\ p+pmx^{p-2}\cdot\frac{p(p-1)}{2}\\ \displaystyle =\ p+p^2 (\frac{p-1}{2}\cdot mx^{p-2})\\ \equiv \ p \ \mathcal{mod} \ p^2$
であるので、与式の $n=p$ の場合、すなわち $\displaystyle \mathcal{ord}_p {(x^p-y^p)} =\mathcal{ord}_p {(x-y)}+1$ は成立する。
⑵ $n$ と $p$ が互いに素である場合
$\displaystyle x^n-y^n=(x-y)(x^{n-1}+x^{n-2} y+\cdots +y^{n-1})$
ここで、 $\displaystyle y \ \equiv \ x \ \mathcal{mod} \ p$ であり、
$\displaystyle x^{n-1}+x^{n-2} y+\cdots +y^{n-1}\ \equiv \ nx^{n-1} \ \not\equiv \ 0 \ \mathcal{mod} \ p$
したがって与式は成立する。
⑶ $n=ap^k$ の場合( $a$ は $p$ と互いに素)
$k=0$ のとき⑵より成立する。
$k=m$ のとき成り立つと仮定すると、⑴が適用できて、
$\displaystyle \mathcal{ord}_p {(x^{ap^{m+1}}-y^{ap^{m+1}})}\\ =\mathcal{ord}_p {({(x^{ap^m})}^p-{(y^{ap^m})}^p)}\\ =\mathcal{ord}_p {(x^{ap^m}-y^{ap^m})}+1\\ =\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p {ap^m}+1\\ =\mathcal{ord}_p {(x-y)}+m+1\\ =\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p {ap^{m+1}}$
以上⑴⑵⑶より示された。//

$p=2$ の場合にも考えてみる(((っ･ω･)っ

同様に考えていきましょう(´・ω・｀)
少し条件が複雑になります
$x,y$ は $2$ で割り切れず、 $(x-y)$ は $2$ で割り切れるとします

[定理]
・ $2\not\mid n$ または $2\mid n\ \wedge\ 4\mid (x-y)$ の場合
$\displaystyle \mathcal{ord}_2 {(x^n-y^n)}=\mathcal{ord}_2 {(x-y)}+\mathcal{ord}_2 n$
が成り立つ。
・ $2\mid n\ \wedge\ 4\not\mid (x-y)$ の場合
$\displaystyle \mathcal{ord}_2 {(x^n-y^n)}=\mathcal{ord}_2 {(x^2-y^2)}+\mathcal{ord}_2 n -1$
が成り立つ。

[証明]
$n$ が奇数の場合は、上記の証明の⑵と同様の議論で証明される。
$(x-y)$ が $4$ で割り切れるとき、
$\displaystyle y \ \equiv \ x \ \mathcal{mod} \ 4 \ \wedge \ x,y \ \not\equiv \ 0 \ \mathcal{mod} \ 2 \\ \Rightarrow x+y \ \equiv \ 2 \ \mathcal{mod} \ 4$
に注意して、
$\displaystyle \mathcal{ord}_2 {(x^2-y^2)}\\ =\mathcal{ord}_2 {(x-y)(x+y)}\\ =\mathcal{ord}_2 {(x-y)}+1$
であり、 $n=2^ka$ ( $a$ は奇数)のときに主張が成り立つと仮定すると、
$\displaystyle \mathcal{ord}_2 {(x^{2^{k+1}a}-y^{2^{k+1}a})}\\ =\mathcal{ord}_2 {({(x^{2^{k+1}})}^a-{(y^{2^{k+1}})}^a)}\\ =\mathcal{ord}_2 {({(x^{2^k})}^2-{(y^{2^k})}^2)}+\mathcal{ord}_2 a \\ =\mathcal{ord}_2 {(x^{2^k}-y^{2^k})}+1\\ =\mathcal{ord}_2 {(x-y)}+\mathcal{ord}_2 +\mathcal{ord}_2 2^k +1\\ =\mathcal{ord}_2 {(x-y)}+\mathcal{ord}_2 {2^{k+1}}$
となり、帰納法より一つ目の主張は正しい。//
$(x-y)$ が $4$ で割り切れないとき、 $\displaystyle x^2-y^2\ \equiv \ 0 \ \mathcal{mod} \ 4$ より、一つ目の主張に、 $\displaystyle x^2,y^2,\frac{n}{2}$ を代入する事で、二つ目の主張を得る。//
このとき、 $\displaystyle \mathcal{ord}_2 {(x^2-y^2)}$ をこれ以上簡単に表すことは出来ない。*1

結論をまとめます( ﾟωﾟ )ゝ

ある素数 $p$ とある整数 $x,y$ が
$\displaystyle x\ \equiv \ y \ \not\equiv \ 0 \ \mathcal{mod} \ p$
を満たすとき、

⑴ $\displaystyle p=2\ \wedge\ 2\mid n \ \wedge \ 4\not\mid (x-y)$ でない場合
$\displaystyle \mathcal{ord}_p {(x^n-y^n)}=\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p n$
⑵ $\displaystyle p=2\ \wedge\ 2\mid n \ \wedge \ 4\not\mid (x-y)$ である場合
$\displaystyle \mathcal{ord}_2 {(x^n-y^n)}=\mathcal{ord}_2 {(x^2-y^2)}+\mathcal{ord}_2 n -1$

証明を終えた感想(A；´･ω･)

なにも見ずに証明しよう！って事で、 $p=2$ よりも前の部分は自力でやったんですが、 $p=2$ はなかなか思いつかなかったので「獲得金メダル！国際数学オリンピック」という本を参考にしますた(´・ω・｀)
$p=2$ よりも前の部分も正しい事を確認しました
他の方の証明と比較してみて、個性が出てる部分があるかどうか探してみたのですが、有名な証明方法では $\displaystyle x^{p-1}+x^{p-2} y+\cdots +y^{p-1}$ の部分をさらに $(x-y)$ で割るようです
私のやり方では $p^2$ で割った余りが $p$ である事を示し、 $p$ で一度しか割ることが出来ない事を示しています
ここは割と大きな違いじゃないですかね…？(；・∀・)

※不備があったため修正しました。申し訳ございません(2017/12/23)
※修正していなかった不備を全て修正し、大幅リニューアル致しました！(2018/04/05)

*1:見つかっていないだけで、もしかしたら簡単に表せるかも知れません…

cmasterの独り言(´・ω・｀)

2ちゃんねるのコテが気ままにつぶやきます(´・ω・｀)ﾉｼ