第 章 ユークリッドの互除法 ユークリッドの互除法は つの自然数 ， の最大公約数を計算する方法です。 と 公約数の計算方法としては、 と ますが、この方法では と の最大 を素因数分解してその共通項を見つけるというものがあり がとてつもなく大きな数の場合には、最大公約数を見つけるのが 大変困難になります。それに対して、ユークリッド互除法は数が大きくても比較的簡単に計算 することができるのです。 ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方 法です。ユークリッド（ ～ 頃）はユークリッド幾何学の名前で有名な古代ギリシア の数学者であり、 「原論」と言われる著作を残しています。このユークリッドの「原論」は全 巻からなる大著で、幾何学だけでなく数論も含んだ、当時のギリシア正統的数学の集大成とも いえるものです。ユークリッドの互除法は「原論」第 巻命題 から命題 に書かれています が、この「原論」はユークリッド自身の著作と言うよりは、当時の数学をまとめた著作と言わ れており、この成果はもう少し前のピタゴラスの時代のものと言われています。 ユークリッドの互除法 ユークリッドの互除法 （補題） とする。このとき、 （証明） とおき、 であることを示す。 より、 でもあるので、 は と の公約数。一方、 は と の最大公約数なので より、 でもあるので、 より、 は と の公約数。一方、 は と の最大公約数なので ■ （定理）ユークリッドの互除法 に対し、 を次の様に定める。 このとき、次の条件を満たす が存在する。 （証明） ここで、 より、 ∴ となる が存在する。 より、 ∴ ■ この定理より次の系を導くことができる。 （系） 例題 次の つの整数 用いて表せ。 （解答） の最大公約数をユークリッドの互除法を用いて求めよ。また、 を行列の積を よって、 よって、 【問題 】次の つの整数 の最大公約数をユークリッドの互除法を用いて求めよ。また、 を行列 の積を用いて表せ。 例題 任意の自然数 に対し、 と は互いに素であることを証明せよ。 （解答） と は互いに素だから、 と も互いに素である。■ 【問題 】 を互いに素な自然数とするとき、 【問題 】 は互いに素な正の整数とするとき、次の問に答えよ。 分数 は既約分数であることを証明せよ。 なる正の整数 に対して，分数 が既約分数にならないような自然数 【問題 自然数 は既約分数であることを証明せよ。 】 は既約分数であることを証明せよ。 を、小さい方から順に三つ求めよ。 年 大阪市大前期理系 に， とを証明せよ。 の関係があるとき， と が互いに素ならば， と も互いに素であるこ 一次不定方程式 に対し、 なるような を求める問題をディオファントスの問題と いい、この方程式を一次不定方程式（ディオファントス方程式）という。 （補題） に対して、 とする。 （証明） についての帰納法で証明する。 となるから，解 の は必ず解を持つ。 のとき より ゆえに方程式は をもつ。 と で と互いに素な任意の に対して が解をもつとする。 このとき、 が解をもつことを示す。 とする。このとき， と が互いに素なので と も互いに素である。ゆえに，仮定より この解に対して より、 を解くと は は解 をもつ。 となる。 の解となっている。つまり， のときも成立する。 よって 数学的帰納法により すべての と なる に対し は解をもつ。 ■ （系） が互いに素であるとき、 は必ず解を持つ。 （定理） に対して、 （証明） ある整数 なので、 も に対して、 が成り立つとする。 を満たす解が存在する。それを としてこの両辺を よって、 は同値である。 はともに の倍数。 補題より、 が整数解を持つことと とすると、 倍すると、 は の解となる。 ■ 例題 次の一次不定方程式をユークリッドの互除法を用いて解け。解は 組だけでよい。 （解答） ∴ ∴ ∴ ∴ ■ 【問題 】次の一次不定方程式をユークリッドの互除法を用いて解け。解は 組だけでよい。 の倍数 一次不定方程式 （定理） に対して、 に対し、 が のとき、解のひとつを とし、 とすると、解の全体は で与えられる。 （証明）方程式のひとつの解を 、 とすると、 また、仮定より、 ∴ なので、 ここで、右辺は ∴ で割り切れ、 と は互いに素だから、 ∴ は で割り切れることになる。よって、 ■ 例題 一次不定方程式 で割ると の整数解を全て求めよ。 余り、 で割ると 余る整数を求めよ。 （解答） ∴ ∴ ∴ より、 ∴ ∴ ∴ を解く。 より、 を解くと、 より、 ∴ ∴ ∴ ∴ よって、 で割って 【問題 】次の一次不定方程式の整数解を全て求めよ。 【問題 】次の問いに答えよ。 、 余る整数。 ■ で割ると 余り、 で割ると 余る整数を求めよ。 で割ると 余り、 で割ると 余る整数を求めよ。 で割ると 余り で割ると 余るような自然数のうち、 桁で最大のものと最小のものを求めよ。 で割ると 余り で割ると 余るような自然数のうち、 桁で最大のものと最小のものを求めよ。 一次不定方程式 （定理） 不定方程式 が解を持つ必要十分条件は （証明） が成り立つことである。 とおく。 不定方程式 このとき等式 逆に が解 が成り立つ。 明らかに であると仮定すると、 を持つとする。 は左辺の各項を割り切るので と表される。 このとき が存在するので が成り立つ。 を満たす整数 が成り立つ。ゆえに、 不定方程式 解 は をもつ。 ■ 例題 一次不定方程式 で割ると の整数解を全て求めよ。 余り、 で割ると （解答） 余り、 で割ると より、 のとき、まず 余る整数はどのような整数か。 を解けばよい。 を解くと、 ∴ が一つの解なので、 ∴ のとき、 より、 ∴ ∴ より、 ∴ 、 すなわち、 を解く。 より、 まず を解くと、 より、 ∴ ∴ ∴ ∴ 次に、 、 を解く。 ∴ まず を解くと、 より、 ∴ ∴ ∴ ∴ 、 ∴ よって、 で割ると 余る整数である。■ 【問題 】次の一次不定方程式の整数解を全て求めよ。 【問題 】 で割ると 余り、 で割ると 余り、 で割ると 余る最小の自然数を求めよ。 次の問いに答えよ。 整数 は の範囲にあるとする。このとき、 整数 が を満たすとき の整数解を全て求めよ。 の最大値を求めよ。 年 大阪女子大 は互いに素な正の整数とする。 を満たす整数 は存在しないことを示せ。 を満たすすべての整数の組 を整数とするとき、 ならば を で割った余りを で表す。 を 以下の正の整数とするとき、 であることを示せ。 を満たす整数 を求めよ。 が存在することを示せ。 年 東京大前期文理共通 以上 以下の奇数 で、 が で割り切れるものをすべて求めよ。 は整数 は任意の整数値をとることができることを証明せよ。 年 東京大前期理系 平面上， 座標， 座標がともに整数であるような点 半径 の円がえがかれており、傾き ような性質をもつ実数 を格子点とよぶ。各格子点を中心として の任意の直線はこれらの円のどれかと共有点をもつという。この の最小値を求めよ。 年 お茶の水女子大学 正の数 に対して、数列 を次の様に定義する。 のとき を で割った余り のとき について、 任意の 任意の をそれぞれ第 について、 について、 となる について、 のとき のとき （等号は となる が 項まで計算せよ。 のときに限る）を示せ。 が存在することを示せ。 と の最大公約数になっていることを示せ。 の定理 オイラー関数 （定義）オイラー関数 が自然数のとき、 例． の中で のとき、 また、 以外に と互いに素なものの個数を と互いに素な整数は と共通の因数を持つのは のとき、 と表し、オイラー関数という。 の つあるので の つあると考えると、 と互いに素な素数は の つあるので （定理） を素数とする。 の素因数分解が つ。特に が成り立 である。 （証明） から であるとき の素因数は のみであるから、 の間に、 となる の は 個ある。よって 例． のとき、 は の倍数である。このような 個ある。従って から は の間の互いに素な整数 ■ のとき、 （定理） と が互いに素ならば、 （証明） である。 とし， を 以上 以下で もまた同様に選ばれているとする。 と が互いに素なので、 素なので 値を と互いに素で、 で割った余りを である。 を は とする。 に変え同様にして 逆に 同となる と がとれる。この式の値は、 は とすると， が 合同でない。よって異なる と互いに 以上 ， 以下の数 より と を法として合同でない。 が異なる場合も、両方異なる場合も同 とも が が と互いに素である。この式の となる をとる。 と互いに素で互いに合同でない整数が少なくとも が存在する。 と とし， 個ある。その一つをとる。 が と互いに素なので と互いに素、つまり を法として合同でない。よって 様である。 例． となる整数 と互いに素な整数とする。 の組は とも互いに素なので 個存在した。つまり を法として に関して合同でなければ に対する または の組はすべて異なる。 に、 を法として に合 の少なくとも一方に関しても ■ （定理）オイラーの公式 （ は素数、 ）とするとき、 （証明） ■ 例． より、 これをもう少し別な角度から考えてみる。 ある。重複しているのは までの の倍数、 の倍数はそれぞれ、 の倍数であるから、 個 個ある。よって、 例題 を自然数とするとき、 で と の最大公約数が となる自然数 の個数を とする。 を求めよ。 を互いに素な素数とする。このとき を求めよ。 を素数、 を自然数とする。このとき を求めよ。 （解答） と互いに素な 以下の数は の範囲にある と互いに素でない数は が共通なので、互いに素でない数が から の までの数のなかで 。よって の倍数と 個ある。よって、 と互いに素ではないものは、 で割り切れるので、 個ある。よって、 【問題 】 自然数 の倍数でありそれぞれ、 ■ 年 早稲田大学 社会科学 に対して、 以下の自然数で 例えば、 との最大公約数が に対しては、このような自然数は、 、 素数 に対しては であるような自然数の個数を の 個なので、 である。次の問に答えよ。 の値を求めよ。 となる つの素数 を自然数とするとき、 （ただし、 の値を と とする）の組を求めよ。 の式で表せ。 とする。 である。また、 の定理 （補題） かつ ならば （証明）仮定より 。 例． である。 であるから、 。 よって ■ ならば のとき、 であるが、 （補題） とおき、 の中で と互いに素なものを いに素であるとする。このとき任意の とする。また整数 は に対して と互 を満たす が存在する。 （証明） のときは自明であるから、 である。 かつ である。従って を で割った余りを とする。 となる。また となり、 に対して 例． であるとする。 であるから、 が成り立つので、 と表されるから となる が存在する。この が成り立つ。■ のとき であり、 いに素な整数 （定理）（ の中で と互いに素な整数は である。 と互 に対して、 の定理） ならば （証明） が成り立つ。 の中で であるから、補題より と互いに素なものを はある に が成り立つ。補題より、 とする。ここで である。 を法として合同となるので、 のとき であるから、 は を並びかえたものである。 よって、 が成り立つ。これより、 が得られる。 であるから、 例． のとき、 より、 のとき、 より、 （系）（ ■ の小定理） が素数で ならば が成り立つ。 （証明） が素数のときは であることから明らかである。■ 例題 の下 桁は何か。 （解答） より、 より よって となる。よって、 の下一桁は 【問題 】 の下 【問題 】 を である。 ■ 桁は何か。 で割った余りを求めよ。 が成り立つ。ここで であるから 年 京大文系後期 自然数 の関数 を を で割った余り によって定める。 すべての自然数 に対して あなたの好きな自然数 を示せ。 を一つ決めて を求めよ。 その の値をこの設問 におけるあな たの得点とする。 東京農大 を素数、 を で割り切れない自然数とし、 から 任意の に対し， を で割った余りを までの自然数の集合を とおく。 とする。このとき、集合 は と一致す ることを示せ。 は で割り切れることを示せ。 奈良女子大改題 素数 と は に対して、 二項係数についての等式 を証明し、 の倍数であることを示せ。 素数 に対して 自然数 なる整数 に対して を で割った余りを求めよ。 を で割った余りを推測し、 数学的帰納法で証明せよ。 年 阪大後期 は素数、 は正の整数とする。以下の問いに答えよ。 についての式 めよ。ここで、 を展開したときの単項式 は または正の整数で の係数を求 をみたすとする。 が正の整数のとき、 は で割り切れるこ とを示せ。 は で割り切れないとする。このとき、 は で割り切れることを示せ。 年 九州大前期理系 正の整数 ば に対し、 の正の約数全体の和を であり、 ならば で表す。ただし、 及び の正の約数は 自身も約数とする。例え なので となる。次の問に答 えよ。 が正の奇数 と正の整数 を用いて と表されるとする。このとき、 が成り立つことを示せ。 が 以上の整数 と正の整数 を用いて と表されるとする。このとき、 が成り立つことを示せ。また、等号が成り立つのは、 は正の奇数 の形をした偶数 を満たす を求めよ。 かつ 素数であるときに限ることを示せ。 を考える。このとき、 合同方程式の解法 一次合同方程式 「ある整数を 倍して で割ると 余る。ある整数を求めよ。」という問題は合同式を用いると、 を満たす を求める問題になる。一般に未知数を含む合同式を合同方程式という。 （定理） の場合 ならば合同方程式 の解は を法として唯一つ存在し、 えられる。 （証明） のとき、両辺に をかけて 従って、 は合同方程式 逆に、 が成り立っているとすると 、両辺に の解である。 よって、合同方程式 の定理を適用すると、 の解は をかけて、 のみである。■ 例題 次の合同方程式を解け。 （解答） （解 ） （解 ） ∴ より、 （解 ）ユークリッドの互除法を利用する。 ∴ ∴ （解 ） ∴ ∴ ∴ ∴ ∴ より、 （解 ） より、 （解 ）ユークリッドの互除法を利用する。 ∴ ∴ ∴ 【問題 】次の合同方程式を解け。 ∴ ■ で与 一次合同方程式 一般に と が互いに素でないとき、合同方程式 は解を持つとは限らない。例えば、 は解を持たない。なぜならば、解 を持つとすれば、 を得るが、左辺は の倍数であるのに対して、右辺は （定理） が解を持つための条件は が成り立つことである。 とおけば、 が成り立つことと が成り立つことは同値である。また、その解の個数は （証明） が解 する。このとき、 である。 を持つとすると、 より、 が成り立つことから となる が存在 を得る。 とする。 従って、 が成り立つことと であるから たす は が成り立つことは同値である。一方、 は解を持つ。ゆえに 次に解の個数を考える。 において、 が解を持つ。 と は互いに素であるから、この合同式を満 を法とする一つの剰余類になる。それをそれを で与えられる。 つまり、 と に対する が とすると、合同式の解は を法として合同となるのは、 となるときに限る。したがって、 余系 は の倍数にならないので矛盾が生じる。 の場合 逆に となる整数 が存在し、 の値を与えるとき、 で を を法とする剰 のすべての解が得られる。すなわちその個数 である。 ■ 例題 次の合同方程式を解け。 （解答） （解 ） より、 は解を持つ。 定理より すなわち の解と一致する。 よって、解 を得る。またこの解は法 （解 ） （解 ） では と表される。 ∴ を解くことと同値。 ∴ ∴ ∴ ∴ ∴ ∴ ∴ （解 ） より、 は解を持ち、 を解けばよい。 ∴ （解 ） （解 ） ∴ を解くことと同値。まず、 を解く。 ∴ ∴ ∴ ∴ ∴ 【問題 】次の合同方程式を解け。 ∴ ∴ ■ 連立合同方程式 「 で割ると 余り、 で割ると 余る数は何か」という問題は、連立合同方程式 と して表される。この問題はユークリッドの互除法を用いて解くことができるが、ここでは合同式を利用した 解法について考える。 （定理） ならば、任意の整数 は に対して、合同方程式 は解を持ち、その解 を法として一意である。 （証明）まずは解が存在することを示す。 も解 が成り立つから 次に解が であるから を持つ。このとき は解 を持つ。同様に とおくと、 は解である。 を法として一意に定まることを示す。 も解であるとすると、 が成り立つ。これより すなわち かつ が得られる。ここで が成り立つ。ゆえに解は であるから、 。 を法として一意である。■ 例題 連立合同方程式 （解答） を解け。 より、連立方程式は解を持ち、 を法として一意である。 を解く。 より、 より、 より、 を得る。これより 【問題 】次の連立合同方程式を解け。 【問題 】次の問に答えよ。 ∴ となるので、求める解は で割ると 余り、 で割ると 余る整数は何か。 【問題 】次の連立合同方程式を解け。 【問題 】 で割ると 余り、 で割ると ■ で割ると 余り、 で割ると 余る整数は何か。 余り、 で割ると 余る 桁の自然数を全て求めよ。 合同方程式の解法 が整数係数の多項式であるとき、合同方程式 たす を求めよう。このときは、各係数 を満 をそれと合同な数で置き換えても構わない。特に る係数は消し去ってもよい。このような消去を行った後に で割り切れ なら、この方程式を 次という。 （定理） 法 が素数であるならば、 次の合同方程式 （証明）次数 は 個より多くの解を持たない。 についての帰納法で示す。 のとき、一次の合同方程式 は より、 を法として唯一つ解を有す る。 次のとき、解が 個以下であるとする。 の一つの解を とする。 すなわち このとき除法の原理により、 となる とおくと、 なので、 る。このとき、 は この合同式は 解は 次の多項式 または が が存在する。 は整数が係数の多項式であ と同一の解を有する。 が素数であるから で割り切れるときに限って成り立つ。ゆえに 次の合同方程式 以外の の解でなければならない。帰納法の仮定よりこの解は 以下である。よって は 一般の合同方程式 の解は は、 次以下である。■ がある条件を満たせば解くことができる。それを二段階に 分けて示していく。 （定理） 合同方程式 きる。 を の解は、 の解から構成することがで の一つの解とするとき、 ならば の解の中に であるものが に 関してただ一つある。 ならば の が の解を持つときに、その解から 個の解が構成されるか、 は なる解 を持たない。 （証明） に関する帰納法で示す。 のとき、 の何らかの解 整式 の解は と一致しなければならない。つまり を満たす。従って の解 の解 は、 は を法として の形をしている。ここで に対して、 と展開され、さらに は の 次の整数係数の整式であることに注意する。 を に 代入すると、 ここで は整数である。ゆえにこの展開式の第 で を満たすものを求めることは、 とに帰着する。同様に は で割り切れるので ⅳ ここで つの場合を区別する。 項以下は で割り切れる。よって を満たす を求めるこ のとき、 ⅳ はただ一つの解を持つ。それを だから より、 のとき、 ⅳ は 割り切れるなら任意の が て とする。このとき を得る。これは がさらに の解となる。 で割り切れなければ解がない。 が で が解になる。つまり を満たす。すなわち の形の数 は一つの の解を与えないか、あるいは を法とし 個の解を与える。 のとき、 ら の解 が与えられたとして、 のときの解の構成法を示す。このときも の解を構成したのと同様にできる。すなわち、 のあ たちの数で を満たすものは次の様に構成される。 なら を法としてただ一つ定まる。 なら を法として一つもないか、または のときである。■ 例題 合同方程式 を解け。 （解答） ここで のとき、 とおくと、 ∴ ∴ のとき、 ∴ ∴ よって、 ■ 【問題 】合同方程式 ∴ とおくと、 ∴ を解け。 個ある。 個あるのは の解か 合同方程式の解法 （定理） 法 を素数べきに因数分解して がそれぞれ とするとき、 個の解を持つとすれば、 で与えられる。ここで は はそれぞれ （証明） が 個の解をもち、その解は を法としての の任意の解の一組である。 の解ならば、 従って、 の解である。 を満たす。 逆に を満たす は を満たすから、 を満たす。■ 例題 合同方程式 を解け。 （解答） の解はそれぞれ とする。 は次の ⅰ つある。それらを つの解を持つ。 のとき、明らかに ⅱ のとき、 より、 より、 ∴ ⅲ のとき、 より、 より、 ∴ ⅳ のとき、 より、 より、 ∴ よって 【問題 ■ 】合同方程式 を解け。 と 年 九州大 整数を係数とする 次の多項式 について、次のことを証明せよ。 有理数 が方程式 ある自然数 程式 の一つの解ならば、 は整数である。 に対して、 個の整数 のどれもが は有理数の解を持たない。 とする。 が解を持つ必要十分条件は であることを示せ。また、このとき解は を法としてただ一 つ定まることを示せ。 年 京大後期文系 は 以上の自然数、 は素数、 は整数とし、 次式 を考える。 方程式 が が整数解 を持てば、 で割り切れれば、方程式 で割り切れることを示せ。 年 大阪大学前期理系 イ 次方程式 ロ 不等式 は は整数解を持たないことを示せ。 次の条件 イ ロ を同時に満たす整数 で割り切れなければ方 の の組 つの解が共に が成り立つ。 年 千葉大前期 を素数とする。 に関する が整数解を持つのは をすべて求めよ。 次方程式 のときに限ることを示せ。 以上の整数である。
© Copyright 2024 ExpyDoc
