Evolton

東京大学 2022年度 前期日程 第2次学力試験理系数学 第2問

数列{an}を次のように定める。a1=1,an+1=an2+1(n=1, 2, 3, ⋯⋯ )(1) 正の整数nが3の倍数のとき,anは5の倍数となることを示せ。

(2) k, nを正の整数とする。
anがakの倍数となるための必要十分条件をk, nを用いて表せ。

(3) a2022と(a8091)2の最大公約数を求めよ。

難易度7/ 10計算量6/ 10目安25分

数列、整数 合同式、約数・倍数、最大公約数、ユークリッドの互除法、帰納的定義の利用

方針

漸化式 an+1=an2+1 は、任意の法で余りだけを追える形である。a0=0 と拡張すると、ak+j≡aj(modak) が帰納法で示せるので、添字に対して割り算の余りを取る操作がそのまま項の最大公約数に反映される。(2)はこの合同式と単調増加性から ak∣an  ⟺  k∣n を示す。(3)は同じ合同式で gcd⁡(am,an)=agcd⁡(m,n) を証明してから、25を法とする周期で5の指数を確認する。

解答

(1)
5を法として an の余りを調べる。a1=1 からa1≡1,a2≡12+1≡2,a3≡22+1≡0(mod5)である。さらに a4≡02+1≡1(mod5) となり、a1 と同じ余りに戻る。漸化式は直前の余りだけで次の余りを決めるので、以後 1,2,0 が周期3で繰り返される。したがって n が3の倍数のとき an≡0(mod5) であり、an は5の倍数である。

(2) a0=0 と定める。このとき a1=a02+1 なので、漸化式は n=0 から成り立つ。

固定した正の整数 k に対して ak+j≡aj(modak)(j=0,1,2,…) を示す。j=0 では ak≡a0=0(modak) である。ak+j≡aj(modak) が成り立つと仮定すると、漸化式より ak+j+1=ak+j2+1≡aj2+1=aj+1(modak) である。よって帰納法により上の合同式が成り立つ。

いま n=qk+r、0≦r<k とおく。この合同式を q 回繰り返すと an≡ar(modak) である。

数列 an は正で、an+1=an2+1>an より単調増加する。したがって 0<r<k なら 0<ar<ak であり、an を ak で割った余りは0ではない。一方、r=0 なら an≡a0=0(modak) である。

したがってan が ak の倍数⟺r=0⟺k∣nである。

(3)
まず、任意の正整数 m,n について gcd⁡(am,an)=agcd⁡(m,n) が成り立つことを確認する。たとえば m=qn+r、0≦r<n とすると、(2)で用いた合同式より am≡ar(modan) である。したがって gcd⁡(am,an)=gcd⁡(an,ar) である。これは添字に対するユークリッドの互除法と同じ操作であり、最後に余りが0になったとき gcd⁡(ad,a0)=ad となる。ゆえに上の式が成り立つ。

ここで gcd⁡(2022,8091)=3 であるから gcd⁡(a2022,a8091)=a3 である。実際 a1=1,a2=2,a3=5 なので gcd⁡(a2022,a8091)=5 である。

次に、a2022 が25で割り切れるかを調べる。25を法としてa1≡1,a2≡2,a3≡5,a4≡52+1≡1(mod25)であるから、余りは周期3で 1,2,5 を繰り返す。2022 は3の倍数なので a2022≡5(mod25) である。したがって a2022 は5で割り切れるが、25では割り切れない。 a2022 と (a8091)2 の共通素因数 p をとると、p∣(a8091)2 から p∣a8091 である。したがって p は gcd⁡(a2022,a8091)=5 の素因数であり、可能性は p=5 だけである。さらに a2022 は25で割り切れないので、共通因子として現れる5の指数は1で止まる。

よって求める最大公約数は 5 である。

別解

解法2

方針

まず強い整除性 gcd⁡(am,an)=agcd⁡(m,n) を合同式とユークリッド互除法で示す。(2)はこの公式と単調増加性から直ちに判定し、(3)は a8091 の a2022 による余りを直接5まで落として平方の最大公約数を25との最大公約数に帰着する。

解答

(1)
5を法としてa1≡1,a2≡2,a3≡0,a4≡1だから余り 1,2,0 が周期3で繰り返す。よって 3∣n なら 5∣an である。

(2)
a0=0 とおく。帰納法によりak+j≡aj(modak)(j≧0)が成り立つ。したがって添字にユークリッド互除法を行うたびに項の最大公約数も保たれ、gcd⁡(am,an)=agcd⁡(m,n)を得る。数列は狭義単調増加だからak∣an  ⟺  gcd⁡(ak,an)=ak  ⟺  agcd⁡(k,n)=ak  ⟺  gcd⁡(k,n)=k  ⟺  k∣n.(3)
8091=4⋅2022+3 なので合同式よりa8091≡a3=5(moda2022).ゆえにgcd⁡(a2022,a80912)=gcd⁡(a2022,25).25を法とすると余りは 1,2,5 の周期3であり、2022≡0(mod3) だからa2022≡5(mod25).したがって求める最大公約数は 5 である。

総評

添字の互除法が項の互除法へ移る整除数列の問題。目安時間は20〜25分。駿台分析では第6問と並ぶ思考問題で、(1)のみの答案が多い一方、満点も1割強。中心合同式の帰納法、単調性による余り非零の確認、平方に対する5の指数を25法で止める3段階を省略しない。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の数列の問題で問題集を作る

出典: 東京大学 2022年度 第2次学力試験 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。