乳首にパイ毛を巻きつけてたら壊死しました。
東京大学2014年度理系第5問、文系第4問整数問題の解説をします。
[問題]
rを0以上の整数とし、数列{a_n}を次のように定める。
a_1=r,a_2=r+1,a_(n+2)=a_(n+1)(a_n+1) (n=1,2,3,…)
また、素数pを1つとり、a_nをpで割った余りをb_nとする。ただし、0をpで割った余りは0とする。
(1)自然数nに対し、b_(n+2)はb_(n+1)(b_n+1)をpで割った余りと一致することを示せ。
(2)r=2,p=17の場合に、10以下のすべての自然数nに対して、b_nを求めよ。
(3)ある2つの相異なる自然数n,mに対して、
b_(n+1)=b_(m+1)＞0,b_(n+2)=b_(m+2)
が成り立ったとする。このとき、b_n=b_mが成り立つことを示せ。
(4)a_2,a_3,a_4,…にpで割り切れる数が現れないとする。このとき、a_1もpで割り切れないことを示せ。
(文系は(3)まで)
[解答と解説]
(1)
a_n≡b_n (mod p)より
b_(n+2)≡a_(n+2)
=a_(n+1)(a_n+1)
≡b_(n+1)(b_n+1)
ってすぐに終わるには終わるねんけどな。
ただ、もしかしたらこのことを証明して欲しい可能性があるから、modを使わずに書いた方が安全かもしれん。
つまりM≡N (mod p)はM-N=(pの倍数)と言うことやから、M-N=(pの倍数)ってことを証明して欲しいみたいな。
言葉で書くと
MとNはpで割った余りが等しい⇔M-N=pの倍数
やな。
これは正確に覚えておいて欲しいとこやな、
a_nをpで割った商をa'_nとおくと
a_n=pa'_n+b_nより
a_(n+2)-a_(n+1)(a_n+1)=0
⇔
pa'_(n+2)+b_(n+2)-(pa'_(n+1)+b_(n+1))(pa'_n+b_n+1)=0
⇔
b_(n+2)-b_(n+1)(b_n+1)=p(-a'_(n+2)+a'_na'_(n+1)p+a'_(n+1)+a'_n)
でpの倍数になってるから
b_(n+2)はb_(n+1)(b_n+1)をpで割った余りは等しい
これで安全やな。
(2)
これは実際求めてくれってことやな。
a_1=2からb_1=2
a_2=3からb_2=3
b_3≡3・(2+1)=9よりb_3=9
b_4≡9・(3+1)=36よりb_4=2
b_5≡2・(9+1)=20よりb_5=3
b_6≡3・(2+1)=9よりb_6=9
2,3,9の繰り返しになっているから
b_7=2,b_8=3,b_9=9,b_1=10
(3)b_(n+2)=b_(m+2)よりb_(n+1)(b_n+1)=b_(m+1)(b_m+1) (mod p)
やからb_(n+1)=b_(m+1)＞0より割って
b_n+1≡b_m+1⇔b_n≡b_m⇔b_n=b_m
とやると
チーン
ってなります。
これはな、どういうことかと言うと話すと長くなるねん。
長くなるねんけど、話すわ。
これは合同式に除法をしていいかどうかって話やねん。
加法と減法と乗法については定義できることはよくやるやん。
例えば
pを法として
nをpで割った商をn'、余りをr_1
mをpで割った商をm'、余りをr_2
とすると
n≡r_1,m≡r_2
やろ
M-N=(pの倍数)を言ってM≡N (mod p)であると示すと
加法は
(n+m)-(r_1+r_2)=n'p+r_1+m'p+r_2-r_1-r_2
=p(n'+m')
=(pの倍数)
やから
n+m≡r_1+r_2
やろ
減法は同じように
(n-m)-(r_1-r_2)=n'p+r_1-m'p-r_2-r_1+r_2
=p(n'-m')
=(pの倍数)
やから
n-m≡r_1-r_2
やろ
乗法は
nm-r_1r_2=(n'p+r_1)(m'p+r_2)-r_1r_2
=n'm'p^2+n'r_2p+m'r_2p
=p(pn'm'+n'r_2+m'r_1)
=(pの倍数)
やから
nm≡r_1r_2
やったやんな。
そしたら除法はどういう場合にどう定義するのかと言うと
nに対してnm≡1となるmがあったとすると
n^(-1)≡m
とかいて逆元と言うねんけど、これをかけることで除法を定義するねん。
例えば
5を法にすると
2×3=6≡1より2^(-1)≡3、3^(-1)≡2
4×4=16≡1より4^(-1)≡4
って0以外の1,2,3,4それぞれ逆元があるから除法が定義できます。
1は当たり前として
2で割るということは3をかけること
3で割るということは2をかけること
4で割るということは4をかけることやねん。
今度は6を法にすると2に対する逆元は
2×2=4≡4ちゃうな
2×3=6≡0ちゃうな
2×4=8≡2ちゃうな
2×5=10≡4ちゃうな
となると2には何をかけても1にならないから、これは逆元がないねん。
つまり2で割る除法が定義できないねんな。
この違いは何かと言うとpを法にしたときに
pが素数やったら逆元があって除法が定義できて
pが素数でなかったら逆元がない場合があって除法が定義できないねん。
それはなぜかというと、話すと長くなるねんけどな。
まずこの定理やな
aとbが互いに素な整数の時
ax+by=1
となる整数x,yが存在
証明もできるようになっていて欲しいとこやけどな。
この定理から
pが素数の時、nがpの倍数でもないとするとnとpは互いに素で
nx+py=1
となる整数x,yが存在するやろ。
そしたら
nx=p(-y)+1
からm=xと書きなおすと
nm≡1 (mod p)
で
n^(-1)≡m
つまりn≡0以外のnに対して、n^(-1)が存在することがわかって除法が定義できるねん。
と言うことは、何を言いたいのかと言うとこの問題では
「pが素数である」と言うことを使うのがポイントになるねん。
さすがにこの説明は書けないから現実的な解答を書くと、mod使わずに条件を書いたら
b_(n+2)-b_(n+1)(b_n+1)=(pの倍数)
b_(m+2)-b_(m+1)(b_m+1)=(pの倍数)
これでb_(n+2)=b_(m+2),b_(n+1)=b_(m+1)から辺々差をとって消去とかしてあげて
b_(n+1)(b_m-b_n)=(pの倍数)
ここでpは素数より、b_(n+1)とpは互いに素なので
b_m-b_n=(pの倍数)
ってなるわけやねん。
でも0≦b_m≦p-1,0≦b_n≦p-1やから
-(p-1)≦b_m-b_n≦p-1
でpの倍数になるのは
b_m-b_n=0しかなくて
b_m=b_nと言えるねん。
(4)
こういうときは調べてみよか
a_1=0と仮定すると
a_2=1
a_3=1
a_4=2
a_5=4=2・2
a_6=12=2^2・3
a_7=60=2^2・3・5
a_8=780=2^2・3・5・13
a_9=47580=2^2・3・5・13・61
a_10=2^2・3・5・7・13・61
…
終わらないパーティーがはじまります。
これはちょっとアプローチが違うみたいやな。
そもそも(3)を使うはずとか前の問が使えないか考えるのが先やからな。
a_2,a_3,a_4,…にpで割り切れず数が現れないので
b_2,b_3,b_4,…はすべて正にはなってるやろ。
だからもしb_(n+1)=b_(m+1),b_(n+2)=b_(m+2)が成り立てば
b_n=b_m
なってるやろ。
そしたら
b_(n-1)=b_(m-1),b_(n-2)=b_(m-2),…
って成立していって循環するはずやな。
と言うことは循環小数の話は使えないか？考えみよか
まず有理数は
(有理数)=(整数)/(整数)
=割り切れるか、循環小数
やったな。
例えば7で割るとあまりは0,1,2,3,4,5,6しかないやろ。
と言うことは鳩の巣原理から8回も割れば、どこかで0が出るか、または同じあまりが出てくるはずやねん。
11を7で割ると
あまり4
あまり5
あまり1
あまり3
あまり2
あまり6
ってなっていくから、この次は0でも1でも2でも…6でも何が出ても割り切れるか、被りが出るねん。
と言うことは被りが出ると、同じ計算になるから循環するはずやねん。
このことから
pで割るとあまりは0,1,2,…,p-1のどれかよりp桁以内に割り切れるか循環するねん。
{b_n}も余りなわけやから0,1,2,…,p-1のp個の値しかとらないやんな。
ただ隣り合った二つの組み合わせが等しいところがないといけないから
(b_n,b_(n+1))の組み合わせを考えるとp^2個以下のパターンになるねん。
と言うことはp^2+1個の隣り合った組み合わせを考えると鳩ノ巣原理から少なくとも1組は同じのがあるはずやねん。
a_2,a_3,a_4,…にpで割り切れる数が現れないので
k≧2でb_kは1,2,3,…,p-1のp-1個のいずれかである。
よってk≧2でb_k＞0
また(b_k,b_(k+1))の値は(p-1)^2個以下
b_2,b_3,b_4,…,b_(2+(p-1)^2)は隣りあう組が(p-1)^2+1個あるので鳩の巣原理より(b_n,b_(n+1))=(b_m,b_(m+1))となるn,mが存在する
b_(n-1)=b_(m-1),b_(n-2)=b_(m-2),b_(n-3)=b_(m-3),…b_1=b_l
(lは2以上の整数)
となってb_1=b_k＞0よりa_1もpで割り切れないことになります。
東京大学の入試の数学の過去問の解説
- 関連記事
-
テーマ:大学受験 - ジャンル:学校・教育
|
