わんこら日記
甘くて切ない日記。わんこら式数学の勉強法、解説記事

東京大学2014年度理系第5問、文系第4問整数問題の解説
乳首にパイ毛を巻きつけてたら壊死しました。

東京大学2014年度理系第5問、文系第4問整数問題の解説をします。


[問題]
201704231301170c4.jpg
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)
201704231301184e1.jpg
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)
201704231301195b3.jpg
これは実際求めてくれってことやな。

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
とやると

20170423130121fe9.jpg

チーン
ってなります。


これはな、どういうことかと言うと話すと長くなるねん。

長くなるねんけど、話すわ。

これは合同式に除法をしていいかどうかって話やねん。


加法と減法と乗法については定義できることはよくやるやん。
20170423130122ab7.jpg
例えば
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
やったやんな。

20170423130311855.jpg
そしたら除法はどういう場合にどう定義するのかと言うと

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が素数でなかったら逆元がない場合があって除法が定義できないねん。


それはなぜかというと、話すと長くなるねんけどな。

20170423130312abb.jpg

まずこの定理やな

aとbが互いに素な整数の時
ax+by=1
となる整数x,yが存在

証明もできるようになっていて欲しいとこやけどな。

20170423130314a26.jpg

この定理から
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使わずに条件を書いたら
20170423130315bab.jpg

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)
20170423130317ef5.jpg
こういうときは調べてみよか
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


20170423130433c1d.jpg

終わらないパーティーがはじまります。

これはちょっとアプローチが違うみたいやな。

そもそも(3)を使うはずとか前の問が使えないか考えるのが先やからな。
20170423130434617.jpg
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),…
って成立していって循環するはずやな。


と言うことは循環小数の話は使えないか?考えみよか

まず有理数は
(有理数)=(整数)/(整数)
=割り切れるか、循環小数
やったな。


20170423130436e17.jpg
例えば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桁以内に割り切れるか循環するねん。

201704231304376d7.jpg
{b_n}も余りなわけやから0,1,2,…,p-1のp個の値しかとらないやんな。
ただ隣り合った二つの組み合わせが等しいところがないといけないから
(b_n,b_(n+1))の組み合わせを考えるとp^2個以下のパターンになるねん。
と言うことはp^2+1個の隣り合った組み合わせを考えると鳩ノ巣原理から少なくとも1組は同じのがあるはずやねん。


20170423130439645.jpg
201704231305319e6.jpg
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で割り切れないことになります。

東京大学の入試の数学の過去問の解説

テーマ:大学受験 - ジャンル:学校・教育

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://wankora.blog31.fc2.com/tb.php/4838-610226f6
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

わんこら

Author:わんこら
京都大学理学部を数学専攻で卒業した数学と物理講師

現在、東京で働いています。

かずスクール
で数学を教えてます。

わんこら式数学の勉強法
数学の勉強方法や仕方を説明

詳しいプロフィール


メッセージはこちらへ
メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください

勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてはわんこら式診断プログラムを参考にしてメールください
都合がつかず遅れたり返せなかったりする場合があるのは申し訳ないです

リンクはばりばりのフリー
一言メールくれれば相互リンクします。


カテゴリーと名作集
読者に受けが良かった記事を集めてたり、今までの記事をカテゴリー別にまとめてます。



水と空気と街並とからだ
中学時代からの親友てつろうのブログ。
今年、滋賀医科に合格した医学生です。

リンク集
リンク集はこっちです。

このブログは携帯でも見られます。

ランキングサイト


↓ランキング参加中




にほんブログ村 その他日記ブログ 日々のできごとへ

blog Ranking


お勉強BLOGЯanK

リンク

カテゴリー

メールフォーム

名前:
メールアドレス:
件名:
本文:

ブロとも申請フォーム

この人とブロともになる

FC2カウンター

月別アーカイブ

ブログ内検索

RSSフィード