問題
以下の問いに答えよ。
(1) 2017と225の最大公約数を求めよ。
(2) 225との最大公約数が15となる2017以下の自然数の個数を求めよ。
(3) 225との最大公約数が15であり，かつ1998との最大公約数が111となる2017以下の自然数をすべて求めよ。
方針
解法1
最大公約数の条件を素因数分解で整理する。なので，は，に直せる。(2)はで3と5の倍数を除く。(3)ではを使い，になるようにの37倍条件と偶奇条件を調べる。
解法2
(1)は互除法，(2)は として15個ごとの周期で互いに素な剰余を数える。(3)は37の倍数だけを候補にし，2・3・5の各条件で絞る。
解答
解法1
(1)
ユークリッドの互除法を用いる。 である。最後に余り1が出たので である。
(2)
である。自然数がを満たすには，は15の倍数で，は3でも5でも割れないことが必要十分である。そこで とおくと，条件は
となる。 からまでの整数のうち，3の倍数は44個，5の倍数は26個，15の倍数は8個である。したがって求める個数は である。
(3)
引き続き，，とおく。また である。はすでに3を1つ含むので，となるためには，が37の倍数であり，かつ2の倍数ではなく，3の倍数でもないことが必要である。から，3の倍数でないことと5の倍数でないことはすでに含まれている。 にある37の倍数は である。このうちは2の倍数なので不適，は3の倍数なのでを満たさない。したがって だけが残る。よって である。実際，，であるから，求める自然数は である。
解法2
(1)
より，最大公約数は である。
(2)
は
と同値である。また より である。15個の連続する整数のうち15と互いに素な剰余は
の8個である。 で，最後の1から14にも上の8個がすべて現れる。よって個数は
(3)
， である。 とすると， は37の倍数で，2・3・5のいずれの倍数でもないことが必要十分である。 の37の倍数は
は偶数， は3の倍数なので除かれ， だけが残る。したがって