スポンサーリンク

2000 大阪市立大学|整数問題(互いに素・ユークリッド互除法)

整数問題

次の問に答えよ.

(1) 自然数 \(a\) ,\(b\) ,\(c\) ,\(d\) に \(\displaystyle\frac{b}{a}=\frac{c}{a}+d\) の関係があるとき,\(a\) と \(c\) が互いに素であれば, \(a\) と \(b\) も互いに素であることを証明せよ.

(2) 任意の自然数 \(n\) に対し,\(28n+5\) と \(21n+4\) は互いに素であることを証明せよ.



(1)考え方・解答

互いに素であることの証明について

互いに素であることの証明について

  1. 最大公約数 \(g\) が1であることを直接示す
  2. 背理法(最大公約数 \(g\) が2以上と仮定)の利用
  3. ユークリッドの互除法の利用
  4. 「\(a , b\) が互いに素」\(\Leftrightarrow\) 「\(ax+by=1\) が整数解をもつ」の利用
※互いに素・・・最大公約数が「1」である

 

(1)解答:背理法の利用

(1) 自然数 \(a\) ,\(b\) ,\(c\) ,\(d\) に \(\displaystyle\frac{b}{a}=\frac{c}{a}+d\) の関係があるとき,\(a\) と \(c\) が互いに素であれば, \(a\) と \(b\) も互いに素であることを証明せよ.

【解答】

\(a\) と \(b\) も互いに素でないと仮定する.

このとき、\(a\) と \(b\) の最大公約数を \(k\) ( \(k\) は \(2\) 以上の自然数 )とおける.

また、互いに素な自然数 \(a^{\prime}\) と \(b^{\prime}\) を用いて、

\(a=ka^{\prime}\) 、\(b=kb^{\prime}\) とかける.

\(\displaystyle\frac{b}{a}=\frac{c}{a}+d\) より、

\(\displaystyle\frac{kb^{\prime}}{ka^{\prime}}=\frac{c}{ka^{\prime}}+d\)

\(kb^{\prime}=c+ka^{\prime}d\)

\(c=k(b^{\prime}-a^{\prime}d)\)

しかしこれは、\(a\) と \(c\) が互いに素であることに矛盾する.

以上より題意は示された.

(2)解答

(2) 任意の自然数 \(n\) に対し,\(28n+5\) と \(21n+4\) は互いに素であることを証明せよ.

解法Ⅰ:(1)の利用

(1)において、\(a=21n+4\) 、\(b=28n+5\) と考えると、

\(\displaystyle\frac{b}{a}=\displaystyle\frac{28n+5}{21n+4}=\displaystyle\frac{7n+1}{21n+4}+1\) より

\(c=7n+1\) 、\(d=1\) に対応する.

つまり(1)の結果から、\(21n+4\) 、\(7n+1\) が互いに素であれば、

\(21n+4\) 、\(28n+5\) が互いに素となるので、

\(21n+4\) 、\(7n+1\) が互いに素になることを示せばよい.

 

ここで新たに、(1)において \(a=7n+1\)、\(b=21n+4\) と考えると、

\(\displaystyle\frac{b}{a}=\displaystyle\frac{21n+4}{7n+1}=\displaystyle\frac{1}{7n+1}+3\) より

\(c=1\) 、\(d=3\) に対応する.

\(7n+1\) と \(1\) は互いに素であるから、(1)の結果より、\(21n+4\) 、\(7n+1\) が互いに素

したがって、題意は示された.

解法Ⅱ:ユークリッド互除法の利用

ユークリッド互除法

【ユークリッドの互除法】

\(2\) つの自然数 \(a\) 、\(b\) において、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\) とすると

\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しい

\(28n+5=(21n+4)\times 1+7n+1\)

\(21n+4=(7n+1)\times 3+1\)

ユークリッド互除法より

「\(28n+5\) と \(21n+4\) の最大公約数」

=「\(21n+4\) と \(7n+1\) の最大公約数」

=「\(7n+1\) と \(1\) の最大公約数」

= \(1\)

したがって、題意は示された.

 

コメント

タイトルとURLをコピーしました