ユークリッドの互除法を利用して、いろいろな問題を解いていきます。
(例題1)
任意の自然数\(n\)に対し、\(28n+5\)と\(21n+4\) は互いに素であることを証明せよ。
互いに素であるとは、最大公約数が\(1\)であることです。互除法を使って、最大公約数が\(1\)であることを示します。
(解答)
\(28n+5=(21n+4)×1+(7n+1)\)
\(21n+4=(7n+1)×3+1\)
よって、\(28n+5\)と\(21n+4\) の最大公約数は、\(7n+1\)と\(1\)の最大公約数と等しく、それは\(1\)である。
したがって、\(28n+5\)と\(21n+4\) は互いに素である。
(例題2)
\(\displaystyle\frac{21n+4}{28n+5}\) は既約分数であることを示せ。
既約分数とは、これ以上約分できない分数です。
(\(\displaystyle\frac{1}{3},\displaystyle\frac{7}{5}\)など)
分母と分子が\(1\)以外の正の公約数を持たなければ既約分数なので、互いに素であることを示します。結局、例題1と同じです。
(\(\displaystyle\frac{1}{3},\displaystyle\frac{7}{5}\)など)
分母と分子が\(1\)以外の正の公約数を持たなければ既約分数なので、互いに素であることを示します。結局、例題1と同じです。
(解答)
(例題1)と同様に、\(28n+5\)と\(21n+4\) は互いに素であることが示される。
よって、\(\displaystyle\frac{21n+4}{28n+5}\) は既約分数である。
(例題1)と同様に、\(28n+5\)と\(21n+4\) は互いに素であることが示される。
よって、\(\displaystyle\frac{21n+4}{28n+5}\) は既約分数である。
(例題3)
\(7n\)と\(3n+1\)が互いに素になるような、\(100\)以下の自然数\(n\)は全部でいくつあるか。
互除法を利用して、\(7n\)と\(3n+1\)の公約数を、簡単な2数の公約数にします。互いに素なので最大公約数は\(1\)です。
(解答)
\(7n=(3n+1)×2+(n-2)\)
\(7n=(3n+1)×2+(n-2)\)
\(3n+1=(n-2)×3+7\)
よって、\(7n\)と\(3n+1\)が互いに素であるとき、\(n-2\)と\(7\)は互いに素である。
よって、\(7n\)と\(3n+1\)が互いに素であるとき、\(n-2\)と\(7\)は互いに素である。
\(1≦n≦100\) なので
\(-1≦n-2≦98\)
ここで、\(n-2\)と\(7\)が互いに素になるような\(n\)を数えるのではなく、互いに素でないもの(\(7\)の倍数)のほうが数えやすいので、\(7\)の倍数となる\(n\)の個数を数えて全体から除きます。
\(n-2\)が\(7\)の倍数となるのは
\(n-2=7×0,7×1,\)\(・・・,7×14\) の\(15\)個
よって、求める個数は
\(100-15=\)\(85\)(個)
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。