数A \整数の性質 \互除法
数Aの範囲で学習する“互除法”は２つの自然数の最大公約数を求める方法です。
$ a $を$ b $で割ったときの商を$ q $,余りを$ r $とすると「$ a $と$ b $の最大公約数は、$ b $と$ r $の最大公約数に等しい」 性質を利用しています。
高田中学校3年生のK君から最大公約数に関する問題の質問がありました。
【問題】 $11n+39$ と $6n+20$ の最大公約数が7になるような100以下の自然数 $n$ をすべて求めよ
まず、２つの数で余りが整数になるまで互除法を行います。
$ 11n+39=(6n+20)+5n+19$ $6n+20=(5n+19)+n+1$ $5n+19=5(n+1)+14$ となり、$11n+39$ と $6n+20$ の最大公約数は $n+1$ と $14$ の最大公約数に一致することが分かります。
$n+1$ と $14$ の最大公約数が7になるには $n+1$ は７の倍数であり、かつ奇数でなければなりません（偶数では最大公約数が14になるため）。
また、$n$ は100以下の自然数ですから $n+1$ は2以上101以下の整数です。したがって、$n+1= 7,21,35,49,63,77,91$ となり、求める自然数 $n$ は
$n= 6,20,34,48,62,76,90$ になります。
ユークリッドの互除法を利用した定番問題ですので紹介しておきます。
