p-進付値について(触りだけ)

LTEの補題なるものを聞いたことがある人は多いかもしれない。

残念ながらこんな書き出しをしているけれども筆者もLTEに詳しいわけではない。
そこで自分が知っている限りの「p-進付値」についての考え方をこの記事に記していく。

目次

1. 用語記号の整理
2. n乗根が無理数となる証明
3. 難しい問題を解く
4. ラグランジュ、クンマーのお話
5. LTEの補題

1. 用語記号の整理

さっそく、「p-進付値」まわりの用語や記号を整理する。

また、「$v_p(a)$」のことを、「$a$の$p$-進付値」という。
また、定義どおり、$a$は$a=2^{v_2(a)}\cdot3^{v_3(a)}\cdot5^{v_5(a)}\cdot7^{v_7(a)}\cdots$と素因数分解される。

2. n乗根が無理数となる証明

(一般的な証明)
正の整数$p,\ q$を用いて$\sqrt{2}=\frac{q}{p}$とかけたとする。両辺$p$倍し$2$乗することで$2p^2=q^2$

ここで、
$v_2(2p^2)=v_2(2)+v_2(p^2)=1+2v_2(p)$
$v_2(q^2)=2v_2(q)$
となるから、素因数分解の一意性を考えると$1+2v_2(p)=2v_2(q)$である必要があり、この式は左右で偶奇が不一致だから不成立。故に$\sqrt{2}$は無理数。

正の整数$p,\ q$を用いて$\sqrt[3]{2}=\frac{q}{p}$とかけたとする。両辺$p$倍し$3$乗することで$2p^3=q^3$

ここで、
$v_2(2p^3)=v_2(2)+v_2(p^3)=1+3v_2(p)$
$v_2(q^3)=3v_2(q)$
となるから、素因数分解の一意性を考えると$1+3v_2(p)=3v_2(q)$である必要があり、この式は$\text{mod}\ 3$を考えると不成立。故に$\sqrt[3]{2}$は無理数。

正の整数$p,\ q$を用いて$\sqrt[n]{2}=\frac{q}{p}$とかけたとする。両辺$p$倍し$n$乗することで$2p^n=q^n$

ここで、
$v_2(2p^n)=v_2(2)+v_2(p^n)=1+nv_2(p)$
$v_2(q^n)=nv_2(q)$
となるから、素因数分解の一意性を考えると$1+nv_2(p)=nv_2(q)$である必要があり、この式は$\text{mod}\ n$を考えると不成立。故に$\sqrt[n]{2}$は無理数。

(変な証明：参考「えびまラボ」氏)

正の整数$p,\ q$を用いて$\sqrt[n]{2}=\frac{q}{p}$とかけたとする。両辺$p$倍し$n$乗することで$p^n+p^n=q^n$

$n\geq3$のとき、これはフェルマーの最終定理に反する。

3. 難しい問題を解く

この話の前に、ちょっとだけ平方剰余について触れておく。

$\text{mod}\ 3$の世界において、$x^2$は$0$か$1$にしかならない。
$0^2\equiv0\ (\text{mod}\ 3)$
$1^2\equiv1\ (\text{mod}\ 3)$
$2^2\equiv1\ (\text{mod}\ 3)$

こんな感じで、$\text{mod}\ 4$や$\text{mod}\ 5$も見ていく。
$0^2\equiv0\ (\text{mod}\ 4)$
$1^2\equiv1\ (\text{mod}\ 4)$
$2^2\equiv0\ (\text{mod}\ 4)$
$3^2\equiv1\ (\text{mod}\ 4)$　　　　$0$か$1$にしかならない

$0^2\equiv0\ (\text{mod}\ 5)$
$1^2\equiv1\ (\text{mod}\ 5)$
$2^2\equiv4\ (\text{mod}\ 5)$
$3^2\equiv4\ (\text{mod}\ 5)$
$4^2\equiv1\ (\text{mod}\ 5)$　　　　$0$か$1$か$4$にしかならない

いっぱんに、素数$p$の平方剰余は、$0$を除いて$\frac{p-1}{2}$個存在する。( この記事 の「オイラーの規準」あたりの補題5を読むとよい。)

こんな感じで、合同式の世界は$2$乗すると一気に条件が厳しくなる。
かの有名な京大の問題も解ける。

(略解)
$p$と$q$がどちらも奇数なら$2$より大きい偶数となってよくない。よって$p=2$
「$2^q+q^2$が素数」となればいいが、京大が大好きな$\text{mod}\ 3$をしてあげると$(-1)^q+q^2$になる。$q=2$は明らかに不適だから$q$は奇数。よって$q^2-1$を考える。
$q=3$で成立。$q>3$で$q^2=1$となるしかないから$q^2-1$は$3$の倍数。不適。
よって$(p,\ q)=(2,\ 3)$のみ。

こんなかんじで、平方剰余はつよい。

では、難しい問題を解いてみる。

(解答)

両辺のp-進付値は、
(左辺)$=x^2v_p(x)$
(右辺)$=v_p(2)+3v_p(y)$
となり、$x^2v_p(x)=v_p(2)+3v_p(y)$がすべての$p$について成立することと必要十分。
$x\equiv0\ (\text{mod}\ 3)$だと$p=2$で不成立だから$x\not\equiv0\ (\text{mod}\ 3)$である。よって$x^2\equiv1\ (\text{mod}\ 3)$。だから、

• $v_2(x)\equiv1\ (\text{mod}\ 3)$
• $v_p(x)\equiv0\ (\text{mod}\ 3)$　($p$は$3$以上の素数)

だから$x=2t^3$という形でないといけない(ただし$t$は$3$で割り切れない)。

逆にこのとき、$x^{x^2}$は、ちょっと計算すると$2y^3$という形になるとわかる。

よって$t$の範囲は$1\leq 2t^3\leq2\cdot10^{2025}$から$1\leq t\leq10^{675}$。この中に$3$の倍数は$\frac{10^{675}-1}{3}$個あるため、答えは「$10^{675}-\frac{10^{675}-1}{3}=\frac{2\cdot10^{675}+1}{3}$個」である。

難しいですね。

4. ラグランジュ、クンマーのお話

ちょっと簡単な問題を考えてみる。

(解答)

$100$までの自然数のうち$2$の倍数は$50$個あるから少なくとも$100!$は$2$で$50$回割れる。
$4$の倍数は$25$個あるため、まだ割れるやつが$25$個ある。
$8$の倍数は$12$個あるため、さらに割れるやつが$12$個ある...

とすると、求まるものは「$50+25+12+6+3+1=97$」である。

こんな感じで、階乗のp-進付値は簡単に求めることができる。一般化するとラグランジュの定理になる。

では、階乗がうまく計算できるなら二項係数「${}_n \mathrm{ C }_k$」もうまく計算できるのではないだろうか。

クンマーの定理レベルになると、いよいよ入試で使えなくなる。でも筆者は東進の京大本レでこれを使って1分で整数満点を取った。

(解答)
$A$は$3$進法で$2222222\cdots222$であるため、$3$進法で$k$から$A$に繰り上がりが生じない。
よってクンマーの定理より${}_A\mathrm{C}_k$は$3$でちょうど$0$回割れ、これは$3$で割り切れないことを意味する。

意外と楽しくなってきたのではないでしょうか。

5. LTEの補題

Lifting the Exponentのイニシャルを取ってLTEである。読んで字のごとく、指数を上げる補題だ。

$4-1$は$3$で$1$回割れ、
$4^2-1^2$は$3$で$1$回割れ、
$4^3-1^3$は$3$で$2$回割れ、
$4^4-1^4$は$3$で$1$回割れ、
$4^5-1^5$は$3$で$1$回割れ、
$4^6-1^6$は$3$で$2$回割れ、
$4^7-1^7$は$3$で$1$回割れ、
$4^8-1^8$は$3$で$1$回割れ、
$4^9-1^9$は$3$で$3$回割れ、
$4^{10}-1^{10}$は$3$で$1$回割れる。

$1$回しか割れないとき、指数は$1,\ 2,\ 4,\ 5,\ 7,\ 8,\ 10$。
$2$回割れるとき、指数は$3,\ 6$。
$3$回割れるとき、指数は$9$。

実は、こんなものが成立する。

この補題を用いると、$4^n-1^n$は$3$で$1+v_p(n)$回割れることがわかる。

LTEの補題は「$p$で割れる回数」の話だから、「(ある分数)が整数となる(a,b)をすべて求めよ」において分母が$p$で割れる回数と分子が$p$で割り切れる回数を求めて、ある条件下では分母のほうがたくさん割れてしまう、みたいな議論をするときにつかえるのだろうか。

(解答)
分子は奇数だから$n$は奇数。
このとき、$2^n+1=1^n-(-2)^n$とかけるからLTEを使う、となると$3\equiv0$となる法$p$でのLTEになるから$\text{mod}\ 3$を考えそう。
分子の3-進付値は$1+v_3(n)$であり、分母は$2v_3(n)$になる。十分大きい$n$に対して$v_3(n)>1$となってくれれば調べる$n$が有限個になって嬉しい。つまり、最終的には「$n$が大きいとき、$n$は$9$の倍数」となることを示せば良さそうだ。

まず、$n$が$3$を素因数に含むことを示す。$n$のもつ最小の素因数を$p$として、これが$3$になっていてほしい。(奇数なので$2$は素因数に含まれないからこの証明でいい。)
まず、少なくとも$2^{n}\equiv-1\ (\text{mod}\ p)$が成立している必要がある。
似た条件として、$2^{p-1}\equiv1\ (\text{mod}\ p)$がある。
このあたりからうまいこと$2\equiv-1$が言えないか。

$x$を、$2^x\equiv-1\ (\text{mod}\ p)$なる最小の$x$とする。このとき、$x\mid n$であることを示す。
$n$を$x$で割った商を$a$、余りを$b$とすると、$(-1)^a\cdot 2^b\equiv-1$。ここで$b\neq0$と仮定する。
$a$が偶数のとき、$x$の最小性に$b$が反する。
$a$が奇数のとき、$2^b\equiv1$であり、これで$2^x\equiv-1$を割ると$x$の最小性に$x-b$が反する。
よって$x\mid n$。$x\geq p$のときフェル小で両辺を割って$x-(p-1)$が$x$の最小性に反するため$x< p$。$p$は$n$の最小の素因数だったから$x=1$となるしかない。

よって$p=3$。

ここで$n=3m$とおくと条件は$8^m+1\equiv0\ (\text{mod}\ 9m^2)$。
ここで$m=1$は条件を満たす。以降、$m\geq2$とする。
少なくとも$8^m+1\equiv0\ (\text{mod}\ 9)$だから$m$は奇数。
$m>1$のもつ最小の素因数を$q$とし、これが$3$であれば$n$が$9$の倍数となって嬉しい。

必要条件として、$8^m\equiv-1\ (\text{mod}\ q)$が必要。さっきと同様にして$9\equiv0$だから$q=3$が必要。

よって$m=1$つまり$n=3$のみが解になる。

(解答)
$a>b$のとき
左辺が大きくなりそう。
($b\leq p$のとき　$a^p\geq (b+1)^p>b^p+pb^{p-1}>b!+p$　より不適)
($b>p$のとき)
$\text{mod}\ p$より$a=kp$。$\text{mod}\ k$より$k\geq p$よって$a\geq p^2$。また、両辺の$p$-進付値より$p< b<2p$が必要。
ここで、$b!+p\leq(2p-1)!+p\leq p^{2p-1}+p< p^{2p}\leq a^p$より不適。
ただし、途中、$\sqrt[2p-1]{(2p-1)!}\leq p$(相加相乗平均)を用いた。

よって、$a\leq b$。
$\text{mod}\ p$より$a=p$。よって$p^p-p=b!$。
$p=2$のとき$b=2$
$p=3$のとき$b=4$
$p\geq5$のとき、$b\geq p+1$であり、両辺の3-進付値を考えると、
$v_3(p^p-p)=v_3(p^{p-1}-1)=v_3((p^2)^{\frac{p-1}{2}}-1)=v_3(p^2-1)+v_3(\frac{p-1}{2})=v_3(p-1)+v_3(p+1)+v_3(\frac{p-1}{2})$
これが$v_3(b!)$に等しい必要があるが、
$v_3(b!)\geq v_3((p+1)!)>v_3(p-1)+v_3(p+1)+v_3(\frac{p-1}{2})$
だから矛盾。

よって求まるものは$(a,\ b,\ p)=(2,\ 2,\ 2),\ (3,\ 4,\ 3)$である。

まとめ

LTEの補題は、そもそもありえない難易度の問題にしか出てこない。
しかも、「知らないと無理。知ってたらジャブ程度。」といった厄介なやつ。
「$p$でたくさん割れそう」と思ったときにLTEを使ってみる。
「$n$乗が絡んだ分数が整数になるとき」にLTEを使ってみる、
というのがよさそう。

ラグランジュの定理とクンマーの定理は使えるようになること。結構役に立つからいい。
特に、クンマーの定理を知っている人は一般人にそう多くいないと思われるため、積極的に使ってイキってほしい。