※記事の改善を目的に簡単なアンケートを記事の最下段に設置しています※
※わかりやすい、わかりにくい、両方の貴重なご意見を頂き、日々改善しております。※
※ご協力よろしくお願いいたします&ありがとうございます!※

ユークリッドの互除法と一次不定方程式

割り算の式

10を3で割ると、商が3で余りが1ですね。
これを式で表すと、次のように表すことができます。
10=3\times 3 +1
これは何も10と3に限った話ではありません。

ある整数(割り算なので整数を考えます)aをある正の整数(負の数とすると余りがややこしくなりますので負の数としましょう)bで割ることを考えます。
商がqで余りがr(ただし0\leq r < b)としましょう。
このときやはり、
a=b\times q +r
と表すことができます。

割り算と最大公約数

実は割り算と最大公約数にはある関係があります。
整数aを正の整数bで割った商をq、余りをrとし、以下のように表す事ができました。
a=b\times q +r・・・①
(ただし0\leq r < b
aとbの最大公約数をqとするとある整数a',b'があって、a=a'g,b=b'gと掛けます。
これを①に代入すると、
a'g=b'g\times q +r
となります。
等式なので左辺と右辺は等しい数なわけですから、当然最大公約数も等しくgになるはずです。
という事は右辺はgで割り切れるので、rがgで割り切れる事になります。
つまり、aとbの公約数はbとrの公約数というわけですね。
逆にbとrの公約数g’があるとすれば、当然右辺もg’で割り切れるはずです。
つまり、つまりbとrの公約数はaとbの公約数にもなるという事です。
以上の事から、aとbの最大公約数はbとrの最大公約数という事になります。

ユークリッドの互除法

a=b\times q +r
に対し更にbをrで割るという事を考えます。
b=r\times q' +r'
するとbとrの最大公約数はrとr’の最大公約数になります。
更に余りは割る数よりも小さくならなければなりません。
5で割ってあまりが5以上は正しく割り算の計算ができていないですからね。
という事は0\leq r < b0\leq r' < rになります。
これはあわせて書くと0\leq r' < r < bになります。
つまり余りはどんどん小さくなるわけです。
一方でaとbの最大公約数がbとrの最大公約数でした。
同じようにbとrの最大公約数がrとr’の最大公約数になります。
さて、この操作を繰り返していくと、余りがどんどん小さくなるわけですから、やがて余りが0、つまり割り切れます。
例えばもう一回やって割り切れたとしましょう。
r=r'\times q''
これはrとr’の最大公約数がr’だったという事ですね。
なお、最大公約数が1だった場合、最終的に
r=r'\times q' + 1
r'=1\times r'
みたいなことになります。

例題はユークリッドの互除法の問題の解法をご参照ください。

素因数分解の一意性

ある整数を素数の積で表すことを素因数分解と言います。
※素数は1とその数の他に約数が無い正の整数の事です。2,3,5,7,11,…無限個あります。
15=3\times 5
45=3^2 \times 5
この素数の積で表すとき、その素数の「組み合わせ」は1つだけです。
15であれば3が1つ、5が1つ以外の表し方はありません。
45であれば3が2つ、5が1つ以外の表し方はありません。

一次不定方程式

ax+by=cのような形の方程式を2元一次不定方程式と言います。
単に一次不定方程式と呼ぶことにします。
この方程式を満たす(x,y)の組を一次不定方程式の解と言います。
また解の内ともに整数になるような解を整数解と言います。

一次不定方程式の解き方は一次不定方程式の問題の解法をご参照ください。

アンケートのご協力をお願いいたします

最後までお読みいただきありがとうございました。 よろしければ記事改善のためのアンケートにご協力頂けましたら幸いです。 頂いた内容をもとに近日中に記事を改善させていただきます。

記事を作成するうえでの参考にご意見いただければ幸いです。

疑問は解消されましたか?
 された されなかった

このページの記事の内容はわかりやすかったですか?
 わかりやすい わかりにくい

よろしければわかりにくい場合の理由を教えてください。
 細かすぎる、当たり前なところまで書きすぎ 粗すぎる、行間の不足、論理の飛躍 前提となる知識の記載が無い 言葉の意味が分からない 答えに至る過程の何故そう考えたかの記載が無い 難しすぎてわからない 簡単すぎる 求めていた例題と異なる

ご要望やご意見、もしくは困っている事等(任意)


内容に問題が無ければこちらにチェックをつけて送信ボタンをクリックしてください。

数学解法の目次ページ

数学のコンテンツで数学の演習問題の解法を解説しています。 高校の範囲に限定した目次を作成しました。
高校数学の解法(目次)
数学のコンテンツで数学の演習問題の解法を解説しています。 中学校の範囲に限定した目次を作成しました。
中学数学の解法(目次)
数学
  • このエントリーをはてなブックマークに追加
  • Evernoteに保存Evernoteに保存