最大公約数に関する問題です。九州大学はここ数年、毎年のように整数問題を出題しています。いずれもそれほど難しくはありませんが、対策してきた人としてこなかった人で差の付きやすい問題となっており、過去問の研究も怠れません。
《問題》
（１）$2017$と$225$の最大公約数を求めよ。
（２）$225$との最大公約数が$15$となる$2017$以下の自然数の個数を求めよ。
（３）$225$との最大公約数が$15$であり、かつ$1998$との最大公約数が$111$となる$2017$以下の自然数をすべて求めよ。
（九州大学2017 前期文系第４問）
《考え方》
$2017$が素数であることを知っていれば（１）は即答できますが、ここでは知らないものとしてユークリッドの互除法を利用します。
$2017-9 \cdot 225=-8$ 及び $225-28 \cdot 8=1$ より、$2017$と$225$の最大公約数は$1$と求められます。
（２）は$225=3^2 \cdot 5^2$に注意します。求める自然数を$n$とすると$n$は$15$の倍数でなければなりませんから、$n=15N \ (N \in \mathbb{N})$と置けます。ただし$N$は$3$や$5$を素因数に持つと最大公約数が$15$ではなくなってしまうので$N$は$3$や$5$を素因数に持ちません。
$1 \leqq n=15N \leqq 2017$より、$1 \leqq N \leqq 134$であり、$1$から$134$までの自然数の中に$3$の倍数は$44$個、$5$の倍数は$26$個、$15$の倍数は$8$個あるので、求める個数は
$134-(44+26-8)=$ $72$個
となります。
（３）ですが、$1998=2 \cdot 3^3 \cdot 37$なので、$1998$との最大公約数が$111=3 \cdot 37$であるということは、求める自然数を$m$とすると$m$は$3$と$37$の倍数であるということです。更に$m$は$225$との最大公約数が$15$ですから、$m$は$3$と$5$の倍数でなければなりません。
以上より、$m=3 \cdot 5 \cdot 37 M=555M \ (M \in \mathbb{N})$が必要です。ただし$M$は素因数に$3$と$5$と$37$を持たないような自然数です。$1 \leqq m=555M \leqq 2017$より$1 \leqq M \leqq 3$となりますが、$M=2$とすると$1998$との最大公約数が奇数であることに反するので不適であり、$M=3$は$M$の定義に反するので不適です。
以上より$M=1$に限られますから、求める自然数は$$555$$となります。
（コメント）
最大公約数に絡んだ基本的な問題です。来年度も整数問題が出題される可能性は非常に高いので、しっかりと対策しておきたいですね。