Evolton

九州大学 2017年度 前期日程 第2次学力試験文系数学 第4問

以下の問いに答えよ。

(1) 2017と225の最大公約数を求めよ。

(2) 225との最大公約数が15となる2017以下の自然数の個数を求めよ。

(3) 225との最大公約数が15であり,かつ1998との最大公約数が111となる2017以下の自然数をすべて求めよ。

難易度4/ 10計算量4/ 10目安15分

整数 ユークリッドの互除法、最大公約数、剰余分類

方針

最大公約数の条件を素因数分解で整理する。225=32⋅52なので,(n,225)=15はn=15m,(m,15)=1に直せる。(2)は1≦m≦134で3と5の倍数を除く。(3)では1998=2⋅33⋅37を使い,(15m,1998)=3⋅37になるようにmの37倍条件と偶奇条件を調べる。

解答

(1)
ユークリッドの互除法を用いる。 2017=225⋅8+217 225=217⋅1+8 217=8⋅27+1 である。最後に余り1が出たので (2017,225)=1 である。

(2) 225=32⋅52=152 である。自然数nが(n,225)=15を満たすには,nは15の倍数で,n/15は3でも5でも割れないことが必要十分である。そこで n=15m とおくと,条件は1≦m≦⌊201715⌋=134,(m,15)=1となる。 1から134までの整数のうち,3の倍数は44個,5の倍数は26個,15の倍数は8個である。したがって求める個数は 134−44−26+8=72 である。

(3)
引き続きn=15m,(m,15)=1,1≦m≦134とおく。また 1998=2⋅33⋅37,111=3⋅37 である。15mはすでに3を1つ含むので,(15m,1998)=111となるためには,mが37の倍数であり,かつ2の倍数ではなく,3の倍数でもないことが必要である。(m,15)=1から,3の倍数でないことと5の倍数でないことはすでに含まれている。 1≦m≦134にある37の倍数は 37,74,111 である。このうち74は2の倍数なので不適,111は3の倍数なので(m,15)=1を満たさない。したがって m=37 だけが残る。よって n=15⋅37=555 である。実際,(555,225)=15,(555,1998)=111であるから,求める自然数は 555 である。

別解

解法2

方針

(1) は互除法,(2)は n=15m として15個ごとの周期で互いに素な剰余を数える。(3)は37の倍数だけを候補にし,2・3・5の各条件で絞る。

解答

(1) 2017=225⋅8+217,225=217+8,217=8⋅27+1より,最大公約数は 1 である。

(2) (n,225)=15 はn=15m,(m,15)=1と同値である。また n≦2017 より m≦134 である。15個の連続する整数のうち15と互いに素な剰余は1,2,4,7,8,11,13,14の8個である。134=15⋅8+14 で,最後の1から14にも上の8個がすべて現れる。よって個数は8⋅8+8=72.(3) 1998=2⋅33⋅37,111=3⋅37 である。n=15m とすると,m は37の倍数で,2・3・5のいずれの倍数でもないことが必要十分である。m≦134 の37の倍数は37, 74, 111.74 は偶数,111 は3の倍数なので除かれ,m=37 だけが残る。したがってn=15⋅37=555.

総評

難度4,計算量4。目安時間は15分。最大公約数の問題は,まず素因数分解して「ちょうどその指数だけ共有する」という条件に直すのが定石である。(2)では包除原理の範囲をm≦134に移してから数えること,(3)では37を含める一方で2を含めてはいけないことが落とし穴である。最後に候補555を2つの最大公約数へ戻して確認すると答案の信頼性が上がる。

Evolton Pro

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

冊子PDFで見る九大の整数の問題で問題集を作る

出典: 九州大学 2017年度 前期 文系 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。