ユークリッドの互除法

数Aの範囲で学習する“互除法”は2つの自然数の最大公約数を求める方法です。

$ a $を$ b $で割ったときの商を$ q $,余りを$ r $とすると「$ a $と$ b $の最大公約数は、$ b $と$ r $の最大公約数に等しい」 性質を利用しています。

高田中学校3年生のK君から最大公約数に関する問題の質問がありました。

【問題】 $11n+39$ と $6n+20$ の最大公約数が7になるような100以下の自然数 $n$ をすべて求めよ

まず、2つの数で余りが整数になるまで互除法を行います。
$ 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$ は7の倍数であり、かつ奇数でなければなりません(偶数では最大公約数が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$ になります。

互除法を応用した定番問題ですので紹介しておきます。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)