2021年東工大第3問の誘導を除いた解法

お久しぶりです。修論とかが忙しくて更新できていませんでした。ちなみに今は修論を英語にして国際誌に出す作業があったり、そのあともしばらくも忙しいのでまとまった更新は6月以降くらいになりそうです。

とりあえずそんなこんなですが、今年の東工大の入試が誘導を抜くと割と整数の典型問題でなく、かつそこそこ有用性の高い素数の性質を使う問題だなと思って久しぶりに記事を書こうと思いました。

まず問題はこれです。

ようは2nCn/(n+1)が整数になるnを求めたら良いです。

これ、この誘導で(a_(n+1))/a_nを求めて整数になる性質をうんぬんかんぬんすればできるんだなってことが後で少し考えたらわかりましたが、ではこの誘導を除いたら比率を考えてもあまり割り切れる的な性質がなくて考えづらくないかって思いました。

しかしながら、2n Cnの形を思い出すとこの値を素因数分解したとき、2n以下の素数しか出てこないっていうふうになります。

あとは2n Cnはnを大きくすると2n(n+1)より大きくなるので小さい値をしらみつぶししたら解けます。

一般的にコンビネーションがらみの整数の問題は素数pで何回割り切れるかみたいな考え方を使うことが主なので、コンビネーションの評価と素数の合成数である性質というより「素数pとしたらp未満の整数はpの倍数にならない」みたいな性質を使ってて面白いなと思いました。

答えはこちらです。

(21)4^a+4^b+4^cが平方数になるa,b,c

こんばんは。今日はこの問題について考えたいと思います。

この問題、高3のときに知人から聞いた問題なのですが、春合宿の問題にも出てたらしいです。が、問題作るときに自然に出てきそうな問題だったりもするからどうしようと思ったまま知人の問題になってます。

とりあえずこの問題、4で割り切れる回数まとめたら本質的に1+4^a+4^bが平方数になるa,bを求めたらよくなるけど、aに比べてbが大きいと(2^b)^2くらいになりそうというお気持ちから平方数を2^b+kと起きます。こうしたらあとはよくある手法を使って計算すれば解けます。

(6) ペル方程式の無限個の解の構成について

こんばんは。今回はペル方程式について話します。ペル方程式は実際はもっと色々できて、特に解の形状とか完全に特定できるのですが今回は解が無限個あるという点のみに絞って話します(そういう記事はどうせwikiとかに書いてあると思うので)。

ちなみにこれは高2のときにペル方程式の存在を知らずx^2＝5y^2+1の解が無限個存在するかどうかが気になって解いた自作問題がのちにペル方程式と呼ばれてることを知り、このような形でbotに残っております。

で、これ、発想としては9,4がいけて、その他にどうなるか考えてたと思うんですけど、因数分解考えたら(b-1)(b+1)＝5a^2が出てきてb-1とb+1を5x^2とy^2みたいに分かれそうって思います。で、この差を考えたら2になってるはずだけど、そうすると5x^2とy^2の差が2にならないといけないけどそれは構成とかを考えるときに無理そう(だしそもそも|5x^2-y^2|＝2はmod5をみたら不適)なのでb+1とb-1が10x^2と2y^2になるようなケースを考えます。このときまたy^2-5x^2＝1が作れそうなので、構成して無限個になりそうって感じになります。解答はこちら。

(4)京大整数最難問2009年6を解く

こんばんは。今日は僕が見た中では京大通常入試で最難問と思う2009年の6番を解きたいと思います。僕は大学院生で、兄はもっと年上なのですが、兄の京大過去問10年を持っていたおかげか2000年〜の京大入試は解いたことがあるのですが、その中で一番難しいと思います。ただ、今の受験生は10年以上前の問題になると思うと歳を取ったことに震えてしまいますね。

さて、問題はこのようなものですが、

まあとりあえず漸化式立てて、奇数になることもすぐわかります。で、そのあとどうしようって感じですが、とりあえずa_mとb_mが互いに素でないならn>mでもa_nとb_nが互いに素になることがわかります。

また、それとは別個に帰納法でできるんじゃねみたいなお気持ちでn＝1を考えたら(a+b√2)^2＝ (a^2+2b^2)+2ab√2でa^2+2b^2と2abが互いに素が普通に示せます。これを念頭においたら二乗すれば互いに素になってくれるみたいなお気持ちでa_(2^n)とb_(2^n)が互いに素になることも示せます。それゆえa_mとb_mが互いに素でないならm<2^Lみたいなやつでa_(2^L)とb_(2^L)が互いに素にならずに矛盾するみたいなことが言えます。なかなか難しいけど面白い問題だと思います。

(151) pが素数ならx^n-p^nx-p^(n+1)＝0は整数解を持たないことを示す

こんばんは。今日はこの問題

をやります。千葉大後期ですが、千葉大の後期の数学は面白いやつも結構あるのでやってみると良いです。さて、この問題ですが、ご存知だと思いますが、

「有理数解は±(定数部分の約数)/(最高次の係数の約数)が必要」

という主張があります。そのため今回は整数解が存在するならpのべきになってくれます。

それに気をつけるとあとはx^n＝p^n(x+p)で左辺が符号を無視するとpのべきになってくれるため、x+pもpのべきになるはずです。この辺からは適当に条件絞れば出てきます。

(3) フェルマーの小定理、こっちの方が楽だと思う世界線

こんばんは。今回は多分ご存知の方も多そうなフェルマーの小定理「nとp互いに素でpが素数ならn^(p-1)≡1(modp)」を示します。

この問題、集合｛1,2,…,p-1｝を考えたら｛n,2n,…,(p-1)n｝をpで割ったあまりの集合が先の集合と一致するから全部の要素をかけた

n^(p-1) (p-1)!≡(p-1)!(modp)

で(p-1)!で割って示すやつが多いと思います。が、この問題は帰納法でやった方が記述が難しくないのでいいんじゃないかと個人的に思ってます。個人的に思ってるだけで実際は知りません。

(138) 任意の奇数mと任意の正の整数kである整数nが存在してn^n-mが2^kの倍数

こんばんは。今日はJMOのやつで解説希望があったこれを解きます。

考え方って言われてもだいたい経験則で適当にやっただけですがまあ解説していきます。

まずこの問題で何を考えるかですが、2^kの倍数みたいな話が出てきてるけどこういうのはだいたい2^kの倍数になったnに対してそれをうまく使って2^(k+1)の倍数になることをいう、すなわちkに対する帰納法でやればいけそうなんじゃねってお気持ちになります。

それを念頭におくと

k＝1ならn奇数ならなんでもいいやという感じになって、

k＝2ならn^n-mが4の倍数はm≡1(mod4)ならn＝5とかでいいし、m≡3(mod4)とかならn＝3でいけます。

で、ここからどうしようって感じになるけど、この次にn＝5とか見てみると625-mで例えばm＝1とかなら4の倍数になってくれてます(8の倍数にはなってません)。一方、n＝3とかみると、3^3-m＝27-mで、これはもしm＝3とかなら8の倍数にまでなります。

それゆえ単純な構成にはならないなあと思うわけですが、ここで冷静になると2でいっぱい割り切れる分には問題なくて、「2^kの倍数だが2^(k+1)の倍数にならない」のようなケースの時にのみうまくなんか施してやらばいいんじゃない？てなります。それを踏まえると、2^kの倍数になることがくずれなさそうな2^k+nのようなものを考えると、(2^k+n)^(2^k+n)は二項定理展開とかn^(2^k)が2^(k+1)の倍数になることとか念頭においたら2^(k+1)の倍数になってくれそうなことがわかります。

あとは帰納法として答案に昇華すればいけます。