解いてみた4(APMO2004)
たまたま『数論の精選』って本を眺めてて感慨にふけってたところで適当に1問やってみようかなと思って解いてみました。良い問題だったので書いてみる。
問題4. (2004 APMO)
すべての自然数$n$に対して$\left\lfloor \frac{(n-1)!}{n(n+1)} \right\rfloor$は偶数であることを示せ。
解答.
軽い観察
実のところ, $\dfrac{(n-1)!}{n}$というのはだいたいの場合整数である。これ自体は東工大の過去問とかに似たようなものがあります。さらにこれはだいたいの場合偶数になります。若干怪しいのは$n$が素数とか小さいときの場合ですが, そういうのを除くとこれは偶数になってしまう。というのも, $n=ab$ ($a.b>1$) と合成数であったとするなら, $\dfrac{(n-1)!}{ab}$というのがまず約分されることを見たいのだが, まあ分子が階乗だから約分されるはずだろうし, そのとき取り除かれる$a,b$の他にも分子に偶数がたくさんあるのだから偶数になってしまうというのが分かると思う。本問もだいたいこれと同じ原理で成り立っていて, あとは合成数の議論が効かないところをいかに論証するかという感じです。そこでちゃんと数オリの知識を使わせてくるという。次は必要なので思い出しておきましょう。
定理. (Wilson)
$p$を素数とする。$(p-1)! + 1$は$p$の倍数である。■
上の証明はまあそこらへんに書いてあるだろうけど原始根とか取ればすぐ。
そして合同式を使っても分かるように, $(p-2)! - 1$も$p$の倍数です。
解答に入ります。$a_n = \left\lfloor \frac{(n-1)!}{n(n+1)} \right\rfloor$ とおく。
Case1. (小さい場合)
くだらん部分。$1\leq n\leq 5$までは全部OKです。実際
$$ a_1 = a_2 = a_3 = a_4 = a_5 = 0 $$
以降$n\geq 6$とする
Case2. ($n,n+1$がどちらも素数ではない場合)
$n=ab, n+1=cd$とおく。ただし$a,b,c,d>1$。$n\geq 6$なので(実際は$n>4$くらいでOK), $a\neq b, c\neq d$となるように取ることも出来る。$a>b, c>d$としてよい。ここで$a,b,c,d$はどの二つも異なる。なぜなら, $n$と$n+1$が互いに素で$a\neq b, c\neq d$となるようにしたから$a=c$だったりすると$n$と$n+1$の1でない公約数が取れてしまいOUT。ほかの場合も同様。
そして$b,d\geq 2$なので$a\leq \dfrac{n}{2}$, $c\leq \dfrac{n+1}{2}$で, $n\geq 6$なので(実際は$n\geq 3$でOK), $\dfrac{n}{2}, \dfrac{n+1}{2} \leq n-1$が成り立つ。よって$a,b,c,d$は$n-1$以下の異なる4つの自然数。したがって$a_n = \left\lfloor \dfrac{(n-1)!}{abcd} \right\rfloor$の床関数の「中身」について, 分母の$a,b,c,d$が$(n-1)!$の因数として現れる$a,b,c,d$を消去するだけなので「中身」は明らかに整数で, $a_n = \dfrac{(n-1)!}{abcd}$である。$a,b,c,d$の中に偶数は高々2個なので($n,n+1$のどちらかが奇数だから), 残った分子の因数の中に偶数が少なくとも一つ残っているというのは明らかである(この部分は$n\geq 6$なら必ずOK)。よってこの場合は偶数である。
以下, $p$は素数。
Case3. ($n=p$)
$a_p = \left\lfloor \dfrac{(p-1)!}{p(p+1)}\right\rfloor$ だが, 次が示せる。
Claim3.1
$a_p = \dfrac{(p-1)!}{p(p+1)} - \dfrac{p-1}{p} $ ■
(Proof.)
「中身」にとりあえず$\dfrac{p-1}{p}$という1未満の数を引いてみる(動機としては"整数部分の候補"をWilsonの定理をもとにして見つけたいと思ってるとわかる)
「中身」$-\dfrac{p-1}{p}$は$\dfrac{(p-1)! - (p^2-1)}{p(p+1)}$になる。これが整数であるというのは, Wilsonの定理と$(p-1)!$が$2\times \dfrac{p+1}{2}$の倍数であるということからただちにわかる(そのとき$2<\dfrac{p+1}{2}$を言うべきで$3<p$ならOK)。1未満の数を引いて整数になってしまったのでこれはClaimの主張を示唆する。□
$p$は奇素数だから
$$ p a_p = \dfrac{(p-1)!}{p+1} - (p-1) \in 2\mathbb{Z} $$
を言えば$a_p$が偶数ということが従う。よって
$\dfrac{(p-1)!}{p+1} \in 2\mathbb{Z}$を言えばよい。これはまあできる。実際, $p+1$は$2\times \dfrac{p+1}{2}$で, $(p-1)!$は$2\times \dfrac{p+1}{2}\times (p-1)$の倍数(もちろん$2 < \dfrac{p+1}{2} < p-1$を言うべきだが$3<p$でOKである) で, $\dfrac{(p-1)!}{p+1}$は$p-1$の倍数になる。とくに偶数。よってOK。
Case4. ($n=p-1$)
Case3. と方針はほとんど同じなのだが, まあ我慢して書くことにする。
Claim4.1
$a_{p-1} = \dfrac{(p-2)!}{(p-1)p} - \dfrac{p-1}{p} $ ■
(Proof.)
「中身」$-\dfrac{p-1}{p}$は$\dfrac{(p-2)! - (p-1)^2}{(p-1)p}$になる。これが整数であるというのは, Wilsonの定理と$(p-2)!$が$2\times \dfrac{p-1}{2}$の倍数であるということからただちにわかる(そのとき$2<\dfrac{p-1}{2}$を言うべきで$5<p=n+1$ならOK)。1未満の数を引いて整数になってしまったのでこれはClaimの主張を示唆する。□
よって
$$ p a_{p-1} + (p-1) = \dfrac{(p-2)!}{p-1} \in 2\mathbb{Z} $$
を言えば良い。これは最初の観察で述べたやつそのまんま。$p-1 = 2\times \dfrac{p-1}{2}$で, $(p-2)!$が$2\times \dfrac{p-1}{2} \times (p-3)$の倍数なので(もちろんこのとき$2<\dfrac{p-1}{2}< p-3$を言うべきで, $5<p = n+1$ならOK), $\dfrac{(p-2)!}{p-1}$は$p-3$の倍数。とくに偶数。
よって$a_n$は偶数。(証明終)
頭の体操で楽しかった。不等式的なところは微妙かもしれないけどふわっと思い浮かんでいけたので楽しい。まあなんというか$(n-1)! \bmod{n(n+1)}$が意外と激しく振る舞わないのでそこに注目したらClaimみたいなことは思いつきやすいと思う。$n$が小さいところはただの大小の問題ですが, そこはそこで偶然がもたらす設計だと思うので, こうい地味な不等式は避けられない性格をしているんじゃないかなという気はします(しらんが
)
近況報告。今期レポートだけなんで100点とか取りやすかったし講読研究以外の単位がそろいました。必修除き数学だけで単位が埋まって京大理学部のここがすごい！だった。幾何学は怖い。Fromis_9が全然カムバをしないのでiz*oneにうつっちゃいそう(宮脇さんとキムチェウォンが素敵)。最近読んでる本はJ.SerreのA course in Arithmetic, 複素代数幾何学入門(堀川), Harthshorne代数幾何学1巻など。8月はこのへんを進めながら院試対策。ガロア理論もっと深いところまで復習したい。9月はLiuとAtiyah-Macdonaldと複素代数幾何の予定。今年も僕らのサークルはzoomの活動になっちゃいましたが京大模試を頑張って作ると思いますので乞うご期待。
