問題
以下の問いに答えよ。
(1) 2017と225の最大公約数を求めよ。
(2) 225との最大公約数が15となる2017以下の自然数の個数を求めよ。
(3) 225との最大公約数が15であり，かつ1998との最大公約数が111となる2017以下の自然数をすべて求めよ。
出典：九州大学 2017年度 前期日程 第2次学力試験 文系 前期 第4問
方針
最大公約数の条件を素因数分解で整理する。なので，は，に直せる。(2)はで3と5の倍数を除く。(3)ではを使い，になるようにの37倍条件と偶奇条件を調べる。
解答
(1)
ユークリッドの互除法を用いる。 である。最後に余り1が出たので である。
(2)
である。自然数がを満たすには，は15の倍数で，は3でも5でも割れないことが必要十分である。そこで とおくと，条件は
となる。 からまでの整数のうち，3の倍数は44個，5の倍数は26個，15の倍数は8個である。したがって求める個数は である。
(3)
引き続き，，とおく。また である。はすでに3を1つ含むので，となるためには，が37の倍数であり，かつ2の倍数ではなく，3の倍数でもないことが必要である。から，3の倍数でないことと5の倍数でないことはすでに含まれている。 にある37の倍数は である。このうちは2の倍数なので不適，は3の倍数なのでを満たさない。したがって だけが残る。よって である。実際，，であるから，求める自然数は である。