第 章 整数問題 連分数 入試問題 （ 早稲田） 次の問いに答えよ。 を互いに素な正の整数とする。 の整数解を全て求めよ。 は正の整数） と書けるとする。 を通分して得られる分子 を 、分母 を とするとき、 の値を求めよ。 の整数解を求めよ。 （ 東大理系） 実数 の小数部分を， かつ 実数 に対して，無限数列 の各項 が整数となる実数 ， のこととし，これを記号 で表す。 を次のように順次定める。 ） のとき、 のとき、 のとき，数列 任意の自然数 を求めよ。 に対して となるような 以上の実数 が有理数であるとする。 を整数 と 自然数 を用いて 数 に対して， であることを示せ。 をすべて求めよ。 と表すとき、 以上のすべての自然 有理数の連分数 次の様な分数を（正則）連分数といい、 と略記する。 この連分数は厳密には次の様に定義される。 （定義）連分数 例題 を連分数表示せよ。 （解答） ■ 【問題 】 を連分数表示せよ。 これからこの連分数について学習するが、その下準備として連分数の ”分子 ”と ”分母 ”にあたる数につ いて学んでおく必要がある。 （定義）連分数の ”分子 ”と ”分母 ” に対し、 を次の様に定める。 （補題） （証明） また、 定義より より、 ∴ より、 ∴ より、 ■ （定理）（ 次分数近似） ここで である。 （証明） ■ を 次分数近似という。 例題 を連分数表示せよ。また、 を求めよ。 （解答） ■ 【問題 】 を連分数表示せよ。また、 を求めよ。 実数の連分数 有理数についての連分数展開をみてきたが、今度はこれを実数にまで拡張する。 （定義）実数の連分数 とする。 すなわち （定理） （証明） より、 とすると、 ■ （定義） に対し、 を次の様に定める。 このとき有理数の場合と同様に次の定理が成り立つ。 （定理） （証明）省略 （定理）（ 次分数近似） （証明）省略 例題 （解答） ∴ を連分数表示し、 次の分数近似をせよ。 とおく。 【問題 】次の値を連分数表示し、 次の分数近似をせよ。 （補題） または （証明） ∴ ∴ ■ （定理） （証明） ここで より、 ∴ より、 ∴ ∴ ∴ ∴ ∴ より、 より、 より、 が奇数のとき、 が偶数のとき、 より、 は単調増加なので、 ■ 例題 の近似分数を用いて、次のことが成り立つことを について確かめよ。 （解答） ∴ が成り立つ。 ∴ ∴ ■ 【問題 】 の近似分数を用いて、次のことが成り立つことを について確かめよ。 （定理） （証明） ∴ のとき、 ∴ ∴ ■ 循環連分数と 次無理数 （定義）循環連分数 無限連分数が が循環連分数であるとは、 を満たす が存在することをいう。 また、 を循環節の長さという。 を循環節といい、次の様に表す。 のとき、純循環であるという。 例題 を連分数表示し、循環節表示せよ。 （解答） とおく。 ∴ ■ 【問題 】次の数を連分数表示し、循環節表示せよ。 （定義） 次無理数 整数係数の 次方程式 の判別式が正かつ平方数でないとき、この方 程式の解を 次無理数であるという。逆に 次無理数が満たす整数係数の 次方程式を、その 次無理 数の 次方程式という。その中で最高次の係数が の多項式を最小多項式という。このとき方程式の解 に対して、 となるような 平方数でない に対し、 は が存在し、 次無理数で、 を共役元という。 が最小多項式である。また、 の共役元は である。 （定理） が 次無理数であることと、 ることは同値である。また、 （証明）（ ） を が は の共役元とする。 の共役元である。 は明らか。また、 次無理数であ より、 ∴ （ ） 次無理数 を の作る 次方程式を とする。 に代入すると、 ここで、 とおくと、 のとき、 より、 のとき、方程式 ここで すなわち の判別式をそれぞれ は平方数ではないので、 となり、矛盾。よって、 とすると、 も平方数ではない。よって、 は 次無理数である。■ （定理） 次無理数は循環連分数に展開される。 （証明） を無理数、 の作る 次方程式を を とする。 に代入すると、 ∴ ここで、 とおくと、 より、 ∴ 同様に また、 （定数） （定数） （一定）より、 （定数） よって、 となる 致する。 ■ は有界な点列をなり、 が存在する。ここで は 次方程式 の解であるから、少なくとも つは一 例題 （解答） ∴ の値を求めよ。 とする。 ∴ （∵ ） ■ 【問題 】次の数の値を求めよ。 の連分数展開 （定義）簡約な 次無理数 次無理数 が簡約な 次無理数であるとは、 が成り立つことである。 （補題） は簡約 次無理数である。 （証明） また、共役元は なので、 ■ （定理） 簡約な （証明） 次無理数は純循環な連分数に展開される。 を簡約 次無理数として、循環の長さを とする。 とすると、 より、 より、 ∴ ∴ ■ 例題 は純循環な連分数に展開されることを確認せよ。 （解答） とおく。 ∴ は簡約な 次無理数。 ■ 【問題 】 は純循環な連分数に展開されることを確認せよ。 （定理） （証明） の証明 は簡約 ここで とおくと、 次無理数なので、純循環な連分数に展開される。循環節の長さを とすると、 ∴ の証明 とおくと、 であるから、 を満たす。このとき、 は次の に関する 次方程式 とおく。 任意の整数 に対して、 となる て、 をとり、 とおく。このとき、 と定め、すべての整数 に対し となる。 ∴ ∴ となり、 は と同じ 次方程式を満たす。 だから、 は の共役元 ∴ 後半の性質は回文構造を有するという。 例題 を連分数展開し、回文構造を有することを確認せよ。 （解答） ∴ 【問題 】 とおく。 ■ を連分数展開し、回文構造を有することを確認せよ。 に等しい。よって、 ■ 素数と整数論の基本定理 入試問題 （ 北見工業大学） 次の定理と証明について，以下の問いに答えよ． 定理 素数は無限に存在する。 証明 定理が成立しないとすると，素数は有限個である。それらの素数を を考えると， は とする。このとき， のどれでも割り切れない。 したがって， の積として表したとき，この積に現れる素数は を素数 のいずれとも異なる。これは矛盾である。 したがって定理が証明された。 上のように，結論が成り立たないと仮定して矛盾を導き出すことにより命題を証明する方法を何とい うか。 下線 の主張がなぜ成り立つかを説明せよ。 下線 で何と何が矛盾するのかを答えよ。 で小さい方から 番目の素数を表すとき，不等式 が成り立つことを示せ。 （ 千葉大） 以上の素数は，ある自然数 を自然数とする。 を用いて は， または の形で表されることを示せ。 は自然数 の形で表される素数を約数にもつことを示せ。 は自然数 の形で表される素数は無限に多く存在することを示せ。 素数の定義 （定義）素数、合成数 次の条件を満たす整数 を素数という。 の正の約数は と のみである また、 より大きな整数でないものを合成数といい、整数 の約数で素数であるものを素因数または素因 子という。 （定理）素因数分解 以上の整数 は、 は素数 と表すことができる。 （証明） についての帰納法で証明する。 のとき、明らかに成立。 として、 以上 以下の自然数について成り立つと仮定する。 が素数の場合は明らかに成立する。 が合成数の場合、 とすると、仮定より は素数 ∴ となり、 についても成り立つ。 より 以上の全ての自然数 について成り立つ。■ 例題 が自然数となるような自然数を全て求めよ。 （解答） ∴ 【問題 】 【問題 】 ■ が自然数となるような自然数を全て求めよ。 が自然数となるような自然数 の値を求めよ。 例題 が素数になるような自然数 を全て求めよ。 （解答） だから、 の組み合わせが考えられるが、 は自然数なので の場合しかない。このとき、 められる。よって、求める自然数は 【問題 】 【問題 】 を自然数とする 【問題 】（ よ。また，このときの になるとき、 より、 より となり、 が素数であることが確か ■ が素数となるような整数 年千葉大学）自然数 が素数 の値をすべて求めよ。 が素数ならば、 もまた素数であることを示せ。 を用いて、 をすべて求めよ。 と表されるような素数 を全て求め 例題 は自然数とする。 （解答） が全て素数となるのは、 のとき、 となり条件を満たさない。 のとき、 が となり、条件を満たす。 以上の素数のとき、 は よって のときに限ることを証明せよ。 の倍数でないので、 または のとき、 よって素数でない。 のとき、 よって素数でない。 が 以上の素数のときは、条件を満たさない。よって、 と表される。 が全て素数となるのは のときのみである。■ 【問題 】（ 年京都大学） 以上の自然数 に対し、 と がともに素数となるのは のと きに限ることを証明せよ。 【問題 】 は異なる素数とする。 【問題 】（ 年一橋大） であるとき、 がいずれも素数であるような の値を求めよ。 をすべて求めよ。 がいずれも素数であるような をすべて求めよ。 例題 を 以上の自然数とするとき、 は素数とならないことを示せ。 （解答） より、 よって、 は素数ではない。■ 【問題 】次の問いに答えよ。 を整数とする。 が素数となるとき、 と 整数を係数とする多項式 るならば は定数であることを証明せよ。 の値を求めよ。 について、任意の自然数 に対して が素数であ レピュニット数 のように、すべての桁が い、 である自然数をレピュニット数（単位反復数）とい であらわす。 個 は素数であるが、 などは合成数である。 現在、 のとき、素数であることが知られている。し かし、このような素数が無限にあるかどうかはわかっていない。 （定理） 個 が合成数のとき、 （証明） は素数ではない。 は素数 とする。 個 ■ 例題 個 を素因数分解せよ。 個 （解答） ■ 個 【問題 】 【問題 】素数 を素因数分解せよ。 に対して、 が成り立つとき、 めよ。 素因数分解 の値を求 整数論の基本定理 （補題） が素数のとき、整数 （証明） に対して、 と仮定して、 一方、 より または が成り立つ。 を導けばよい。 は素数 の正の約数で であるから、 。 を得る。■ （定理）ユークリッド かつ （証明） より、 は必ず解を持つ。このとき、 より、 。また、 であるから、 ■ （定理）ユークリッドの第一定理 が素数のとき、 （証明） として または を導けばよい。 より、 なので補題より ■ （補題） と が素数で、 ならば はある に一致する。 （証明） についての帰納法で証明する。 のとき、 。 は素数 として、 の正の約数で であるから で定理が成り立つと仮定する。 より、 または のときは、 のときは、帰納法の仮定より、 は よって の場合も成り立つ。 のいずれかに一致する。 より全ての自然数について成り立つ。■ （定理）整数論の基本定理 以上の整数 （証明） を きる。 は素因数分解でき、素因数分解の方法は順序を除いて一意的である。 以上の整数とすると、 は素因数の積として がもう一つの素因数の積として、 は素数）と表すことがで は素数）として表されたとする。このとき、 であり、適当な並べ替えで一致することを についての帰納法で示す。 のとき、 となるので、 は のいずれかに一致する。従って適当な並べ替えで、 が成立。 として、 なり は で定理が成り立つと仮定する。 より、 と のいずれかに一致する。適当な並べ替えで、 ∴ 帰納法の仮定より、 よって の場合も成り立つ。 すなわち かつ より全ての自然数について成り立つ。■ （定理）ユークリッド第二定理 素数は無限に存在する。 （証明）背理法で示す。素数の個数が有限であると仮定する。その個数を 個とし、 数とする。このとき、 は 因数にもたない。従って、 の素因数分解に現れる素数は が全ての素数という仮定に反する。■ のいずれで割っても 余るので、 以外である。つまり、 を全ての素 を 約数の個数と総和 について 自然数 の約数の個数を 、約数の総和を で表すことにする。ここで、約数はす べて正のものに限るとする。 （定理）約数の個数と総和 （ は異なる素数、 は自然数）とする。 の正の約数の個数は の正の約数の総和は （証明） を あるから、 のある正の約数とすると、 の選び方は の め方は について で 通りある。従って、指数の列 通りあり、このそれぞれと とする。式 について、 なる任意の の約数が 対 の定 に対応する。 の右辺を展開すると、その各項はそれぞれの という形になる。ところが、展開してできるこれらの項全体の集合は、自然数 の約数全体の集合に一致する。よって求める総和 はこの れば、 であるから に等しい。 の各因子を等比数列の和と考え の式を得る。■ 例題 次の問に答えよ。 の全ての正の約数の個数を求めよ。 の全ての正の約数の総和を求めよ。 の全ての正の約数の逆数の総和を求めよ。 の全ての正の約数の積を求めよ。 （解答） ∴ 個 の約数の総和 ■ 【問題 】次の整数のすべての正の約数の個数、総和、逆数の和、積をそれぞれ求めよ。ただし、積につ いては素因数分解した形で表せ。 【問題 】正の約数の個数が 個であるような自然数のうち、最小の数を求めよ。 （定理）約数のペアと積 でない整数 自然数 に対して、 が の正の約数の個数 の約数ならば、 は、 が平方数（ き偶数である。さらに、 の正の約数全ての積を （証明） が 未満の の約数ならば、 の正の約数を小さい順に もまた の約数である。 が自然数）のとき奇数で、 が非平方数のと とおくと、 より とおくと、 ∴ より もまた より大きい の約数。 の約数は順に となる。 が平方数のとき でできて の正の約数の個数は になる約数のペアを作ると 個 だけが残るので、 が非平方数のとき できるので、 例題 かけて においては、 の正の約数の個数は かけて になる約数のペアを作ると 個で ■ となる。 が素数で割り切れる回数 （定理） 自然数 に対して、 （証明）各自然数 を が素数で割り切れる回数 が素数 で割り切れる回数を に対して、 は とおく。このとき、 く。 で割り切れる。 各自然数 のとき、 は とおくと、 とおき、その要素の個数 に対して が で割り切れるから は で割り切れる回数を 個の集合 とお に属する つの要素で ある。よって ■ 例題 と素因数分解する。 であることを示せ。 の値を求めよ。 （解答） の倍数は 個ある。 個の の倍数それぞれから をくくりだす。 の倍数は 個ある。 個の の倍数それぞれから をくくりだすことができる。 の倍数は 個ある。 個の の倍数それぞれから をくくりだすことができる。 の倍数は 個ある。 個の の倍数それぞれから の倍数は倍数は存在しないのでこれ以上 以上から で割り切れ、 をくくりだすことができる。 をくくりだすことができない。 で割り切れないことがわかる。 ■ 【問題 】 【問題 】（上智大学） を素因数分解すると、 【問題 】 の下位桁に がいくつ続くか。 【問題 】 京都大学 を素因数分解せよ。 となる。 の値を求 めよ。 を素数、 を正の整数とするとき， は で何回割り切れるか。 ディリクレの原理 入試問題 広島大学 次の文章は，ある条件を満たすものが存在することを証明する際に，よく使われる「鳩の巣原理」 （また は，抽出（ひきだ）し論法ともいう）を説明したものである。 「 個のものが， 個の箱にどのように分配されても， であれば， 個以上のものが入ってい る箱が少なくとも一つ存在する」 この原理を用いて，次の二つの命題が成り立つことを証明せよ． 辺の長さが の正三角形の内部に，任意に 小さいものが少なくとも 個の点をとったとき，その内の 点で，距離が 組存在する。 座標空間で，その座標がすべて整数であるような点を格子点という。座標空間に られたとき，その内の より 点で，中点がまた格子点であるものが少なくとも 個の格子点が与え 組存在する。 名大理系 複素数平面において集合 を次のように定義する。 は整数 は整数 は整数 集合 から いるような は整数 個の複素数を任意に選んでその集合を とする。 の中に，中点が の要素になって 点が存在することを示せ。 愛知教育大 を 以下の自然数の集合とする。また， 以下の自然数 となるものからなる集合を うち最大のものが に対し， の要素でその奇数の約数の とする。このとき 次の問いに答えよ。 を求めよ。 の各要素は， の部分集合 から が までの 個の集合のうちのいずれか 個の要素からなるとき， つに属することを示せ。 が整数となるような の異なる要素 が存在す が整数となるような異なる要素 が存在し ることを示せ。 個の要素からなる ないものを の部分集合 で，その中に つ求めよ。 京大理系 自然数 と 項数列 が与えられていて，次の条件 はすべて正整数で，すべて とおくとき， 整数の と を満たしている。 の間にある。 はすべて平方数である。 乗である数を平方数という。 このとき であることを示せ。 を求めよ。 ディリクレの原理 （定理）ディリクレの原理（鳩の巣原理、部屋割り論法） 人の人を もし 個の部屋に入れることを考える（ ならば少なくとも つ は は ～ の値を （証明） ）。 を で割った商を 、余りを とおく。 人より多くの人が入った部屋が存在する。 を満たし、全て異なるとする。このとき、 個ずつとる。 もしどの部屋も 人以下なら、合計人数は 人以下となり、 に反する。 の中に、 ～ で取らない値があるとする。その値を除く数を記した箱を用意する。箱の 数は 以下となる。数 箱に入るものが少なくとも をその値にしたがってこれらの箱に入れる。 によって、同じ つ存在する。 ■ この原理をもっと簡単にいうと、次のようになる。 （系） 個の箱に個のものを入れると、少なくとも一つ、 個以上のものが入った箱が存在する。 例題 以下の自然数から、 個の数を適当に選ぶ。この 個の数の中から、いくつかの相異なる数の 組を 組選んで、その和を等しくすることができることを示せ。 から までの整数の中から相異なる 個の数をどのように選んでも、和が になる つの 数の組が必ず含まれていることを示せ。 （解答） 個の数の中から、いくつかの相異なる数を選んで組を作るとき、その作り方は、 通りある。また、そのような組の中で、 和が最大となるものは、 和が最小となるものは、 である。したがって、和のとり得る値は、 よって、鳩ノ巣原理により、和が等しくなる組が少なくとも 和が 選んだ になる つの数の組は、次の 個の数をこの つ存在する。 組ある。 組に入れると、 組入る組が少なくとも つある。つまり、和が になる つ の数の組が必ず含まれている。■ 【問題 】 で割って 余る数の数列 数をどのように選んでも必ず、その 【問題 】異なる を考える。この 個の中に、 つの相異なる数で、和が 個の自然数がある。その中に自然数の差が 個の数から相異なる 個の となるものが存在する。 で割り切れるような組が少なくとも 組存在することを示せ。 （ヒント：自然数を 異なる で割った余りは 個の自然数を の 通りで、これを 個の部屋と考える。そして、 人と考えると、 人以上入っている部屋が少なくとも 室ある。すなわち、 で割ったときの余りが等しい自然数が少なくとも 個ある。） ディオファントスの近似定理 （定理）ディオファントスの近似定理 を無理数とする。 （証明） となる 任意の自然数 ることを示す。区間 に対し、 を となる整数 は全部で 組存在す とする。このとき、 個あるので、鳩ノ巣原理によって が属する。 の 個の中に少なくとも つの区間には、 つ以上 が同じ区間に属するとすると、 として、 において が少なくとも 等分する。 として、 に対して の が無数に存在する。 とおくと、 を動かすとき、 の中に相異なるものが無数に存在することを示す。もし、有限個 しかないとすると、その中で の値が最小なものが存在するので、それを に対して、 となる をとる。この に対して再び を選ぶことができる。しかし、 となり、 よって、相異なるものが無数に存在する。 とする。その より、 となるように の最小性に矛盾する。 ■ 例題 となる を求めよ。ただし、 の値を ～ までの整数として、 は に最 も近い数を選べ。 （解答） よって、 【問題 】 に最も近い数を選べ。 ■ となる を求めよ。ただし、 の値を ～ までの整数として、 は ペル方程式 入試問題 大阪府立大 に対して、 と とする。次の問いに答えよ。 を求めよ。 とおく。 は全て同じ曲線上にある。 と を を用いて表せ．また，点 が成り立つことを利用して、その曲線の方程式を求めよ。 明治大学 とする．以下の問いに答えよ． ベクトル に対し， とおく。 ならば であることを 示せ。 等式 をみたす正の整数 に対して， とおけば， が成り 立つことを示せ。 数列 を によって定めると，等式 が成り立つことを示せ。 等式 を満たす正の整数の組 は で与えられた整数の組 のどれかに等しいことを証明せよ。 東京工業大学 二つの条件 または をみたす任意の整数 のうち最小のものを から得られる実数 全体の集合を とする とする。 を求めよ。 整数 と の元 の任意の元 に対し は適当な整数 は の元であることを示せ。 によって と書かれることを示せ。 より大きい の元 お茶の水女子大 等式 を示せ。 の自然数解 が無限組あることを示し， となる解を一組求めよ。 滋賀医大 平面上の 曲線 と を次の式で定義する。 また，点 点 に対して点 は 点 がともに整数であるとき整数点という。 が曲線 上の整数点ならば 上の整数点ならば 点 を次式で定める。 が は曲線 の場合を除いて， または の整数点で は整数 上の整数点であり， は曲線 ならば は自然数 と表す。点 上の整数点であることを示せ。 であることを示せ。 は曲線 にあることを示せ。 曲線 または 上の整数点は を求めよ。 が曲線 は自然数 に限ることを示せ。 または 上 ペル方程式の定義 （定義） 平方数でない に対し、 を未知とする方程式 をペル方程式という。 （補題） を満たす任意の自然数解を も とすると、 で求まる の解である。 を満たす自然数解の任意の 求まる （証明） Ⅱ も つを とすると、 で の解である。 帰納法で示す。 Ⅰ のとき、 のときは明らか。 が解であるとする。 のとき、 ∴ よって、 のときも解となる。 ■ 例題 方程式 方程式 について、次の問いに答えよ。 の任意の解 を見つけて、 の解であることを 方程式 で求まる も について確認せよ。 の任意の つの解 を見つけて、 で求まる も の解であることを確認せよ。 （解答） ∴ ∴ ∴ ∴ 【問題 】 方程式 方程式 の任意の解 解であることを 方程式 の任意の ■ について、次の問いに答えよ。 を見つけて、 で求まる も の について確認せよ。 つの解 の解であることを確認せよ。 を見つけて、 で求まる も ペル方程式の一般解 （定理）ペル方程式の一般解 を満たす自然数解のうちで で求まる （証明） が の値を最小とするものを が自然数解のすべてである。つまり、 の解であるので、 の解となる。 とする。このとき、 の任意の解を で定まる も とすると、ある自然数について、 ∴ は最小なので、 ∴ で定まる ∴ ■ 例題 方程式 の一般解を求めよ。 （解答）最小解は明らかに よって一般解は ここで を求める。 ∴ ① のとき、 ∴ ② とすると、 ∴ のとき、 ∴ とすると、 ∴ とおくと、 ∴ ∴ ∴ ∴ ∴ ∴ 【問題 】方程式 も ■ の一般解を求めよ。 を満たす。 ペル方程式の解の存在 （定理）ペル方程式の解の存在 、 を無理数とする。 （証明） となる は自明でない整数解 を持つ。 が無数に存在する。 を加えて、 をかけると、 より ∴ は と にあるので、少なくとも の間の有限個の整数のいくつかと一致する。しかし、 つの整数 に対して、 が成り立つ。整数を の剰余系で分類すると 組存在する。よって、整数の組 れる。しかし、整数の組 は無数に存在するので、分類された組には無数の が同一の組に属するとする。 とすると、 一方、 は を満たすので、 ∴ よって は ∴ よって で割り切れる。つまり、 ∴ は は無数 は で割り切れる。 ∴ の解である。 ■ は 個の有限個に分類さ が属する。 ペル方程式の解の構成定理 これまでペル方程式の最小解がわかれば、一般解が求まることを見てきた。下の表はペル方程式の最小 解を表したものである。これをみると例えば のときの最小解は と 簡単には求めることができないものも多く存在する。 ではペル方程式の最小解を求めるにはどうしたらよいのであろうか。 ペル方程式の最小解 （定理）ペル方程式の解の構成定理 は平方数でないとする。 の連分数展開の周期を とする。 が奇数のとき 正の偶数 に対して、 は 正の奇数 に対して、 は の解である。 の解である。 が偶数のとき 正の数 に対して、 （証明） は の解である。 とすると、 ここで、 （ とおくと、 より、 よって、 ∴ ∴ ∴ は の共役元） ∴ よって、 が奇数のとき、 正の偶数 に対して、 は 正の奇数 に対して、 は が偶数のとき、正の数 に対して、 の解である。 の解である。 は の解である。 ■ 例題 方程式 の最小解を求めよ。 （解答） は奇数なので、 が の解 が ここで ∴ に対して、 の解 ■ はその次の解になる。 ∴ 【問題 】次の方程式の最小解を求めよ。 に を代入して、 ペル方程式の解の構成定理 （定理）ペル方程式の解の構成定理 は平方数でないとする。 の連分数展開の周期を とする。 の解で、 であるものは の連分数展開で得られる 尽くされる。 （証明） である任意の解を とする。 すなわち であるので、 ここで、 とおく。ただし、 （ は の共役元） に代入すると、 ∴ なので、 である。 とおく。 ここで、 また また、 は ∴ すなわち、 の であるから、 つの解であるから、 さらに、 ∴ のとき、 ∴ のとき、 のとき、 は のとき、 ∴ の連分数展開から得られる。 より、 のとき、 いずれの場合も なので より、 は よって なので 自信の連分数の中に現れる。 は連分数展開である。 であるから、 ∴ よって、 は周期 の倍数になる。つまり、ある整数 したがって、 ■ によって、 となる。 で 多項式環 入試問題 （ 京都教育大） まず整式に関する用語の確認をする。 整式 が整式 整式 が の約数であるとは つの整式 を満たす整式 ， の公約数であるとは， が ， の最大公約数であるとは， が存在することをいう。 の約数であり，かつ， の 約数でもあることをいう。 整式 が つの整式 が最大のものであることをいう。 が ， の公約数の中で次数 の場合は除く 。 これらの用語に注意して 次の問に答えよ． 整式 は の約数であることを示せ。 と異なる整式 が が整式 の約数であれば， とは異なる整式で，整式 が を の要素ならぱ， は が このとき の要素で の最大公約数でもあることを示せ。 が次の条件 を満たしているとする。 が ならば， とすると は の要素である。 は自然数 であることを証明せよ。 京大文系） 個（ ）の正の数の集合 から相異なる要素 このとき， （ ， であるとする。いま，整式 の要素である。 の量小の要素を 互いに異なる 「 は の最大公約数であることを示せ。 お茶の水女子大） 自然数を要素とする空集合でない集合 （ ， で割った余りが の最大公約数であるとすれば， （ は が次の性質をもつという。 をとれば の少なくとも一方は必ず に属する」 の順序を適当に変えれば等差数列になることを示せ。 中央大） であるとき， を満たす整式 の組のなかで， の次数が最小である組，および であるなかで次数が最小の組，をそれぞれ求めよ。 の最高次数の係数が 整式の除法の原理 と 整式の係数が有理数、実数、複素数のいずれかによって、整式全体の集合をそれぞれ 表すこととする。 （定理）整式の除法の原理 つの整式を ただし、 となる整式 がただ とする．このとき， 組，存在する。 （証明）（存在性の証明） ならば のとき れぞれ とすればよい。 とする。また、 と の 次の項をそ とする。 と定めれば である。 で最高次数の係数が と について同様の操作を繰り返す。 の次数が とすれば 回の操作の後 となったとき， とする。この に対し となるので，定理の等式を満たす。 （一意性の証明） 組あったとする。 このとき となる。ここで とすると ところが一方， より、 これは矛盾。ゆえに等式が成立するのは， のときのみである。このとき と なる。 ■ （定義） 整式 が整式 の倍数であるとは， を満たす整式 が存在することと 定義する。 および定数でない整式 は少なくとも定数と でない定数 を 約数 として持つ。 これら以外の約数を 真の約数 という。真の約数を持たない整式を既約という。 例 が の倍数であることは， を で割った余りが であることと同値である。 既約かどうかは，定数倍しても変わらない。 では では では は既約。 はすべて既約である。 と因数分解され， で と因数分解され， は既約。 で と因数分解され， は既約。 で 最小公倍数・最大公約数 （定義） 共通の約数を公約数、公約数のなかで最も次数の高いものを最大公約数という。 最大公約数が定数のとき， と は互いに素であるという。 共通の倍数を公倍数といい、公倍数のうちで次数が最も小さなものを最小公倍数という。 （定理） 二つ以上の整式の公倍数は，最小公倍数の倍数である。 二つ以上の整数の公約数は，最大公約数の約数である。 の最小公倍数を ，最大公約数を が互いに素で，他の整数 とすれば と との積 が で割りきれるなら， が で割りきれる。 （証明） の最小公倍数を 割った商を 余りを も よって、 の倍数であるから は の倍数である。同様に ′ は次数が最小の公倍数であったから，もし より は は は とし は と の倍数であり， でないとすると の倍数である。つまり も よ が を と と の公倍数で の倍数である。つまり が最大の公約数なので， の最小公倍数なので の最小公倍数 は最大公約数 が の を任意の公約数とする。 の 倍数である．同様に の公約数である。 と は の倍数である。 の最小公倍数とする。 一方 で の次数の最小性に反する。よって、 の最大公約数を あるから を ′とおくと の倍数でもあり， り次数が小さい公倍数があることになり は を任意の公倍数とする。 とすると、 も 公倍数となる。ところが つまり とし に一致したので、 は の倍数，つまり任意の公約数 の約数である。 は の最小公倍数であるから適当な整数 とおける。 は の公倍数だから と を用いて， から は の倍数である。 とする。 つまり は の公約数である． は おける。一方 より最大公約数 の約数なので， の最大公約数なので と とおける。 よって、 より、 ところがこれは 最小性により が ， の公倍数であることを示している。 の最大公約数が 定数 なので は り， の倍数であり，したがって が定数。つまり が最小の公倍数なのでその の最小公倍数は と の公倍数である。よって は の倍数である。■ である． 仮定から は の倍数であ 素因数分解 （定義）素因数分解 多項式 を既約な多項式の積に分解して， の形にしたものを そ の体における 素因数分解という。 は異なる既約な多項式、 は 正の整数である． （定理）素因数分解の一意性 多項式は既約な多項式の積として， 定数倍と順序を除けばただ一通りに表すことができる。 （証明）相異なる因数分解をもつ多項式が存在するとする。異なる因数分解をもつ多項式の集合を考える。 この集合に属する次数が最小の多項式を 在する。 は相異なる とする。次数の集合は自然数の部分集合なので，最小値が存 つの因数分解をもつ。それを とする。ここに は既約である。これが異なる因数分解ということは か，または で異なる と が存在するか， のいずれかである。ただし，ここで因数が 異なるとは，どのような定数を一方に乗じても また， と のいずれも なら， これを約せば は一致しないことをいう。 のいずれとも異なる。なぜなら，もし より小さい次数で，異なる因数分解をもつ多項式が得られ， がそのような 多項式のなかで次数最小であることに反する。 とする。 とすると，適当な定数 を となるようにとる。 ここで多項式 を で定める。 である。この い。なぜならもし 反する． よってこの因数分解に 一方、 る。この の因数分解における因数 の倍数なら が は の倍数ではな の倍数となり， 互いに異なる既約な多項式であることに は現れない。 は でもあ の因数分解には，因数 解である。 と矛盾した。したがって異なる なので， が現れている。よって の つの因数分解は相異なる因数分 が異なる つの因数分解をもつ次数最小の多項式であること つの因数分解をもつ多項式は存在しない．■ 不定方程式の解 （定理）整式のイデアル の部分集合 このとき集合 が空でなく はある整式 のみでもなく， 次の性質をもつとする。 の倍数の全体と一致する。つまり、 （証明）条件から る。 である。その結果， の要素のうち， 次数最小の整式 をとる。 なら の任意の要素 とおく。 ここでもし 意の要素 なら は であ をとり，それを より である。よって、 が次数最小の要素であることに反する。よって の倍数である。したがって で割る。 ，つまり の任 が示せた。■ （定理）不定方程式の解の存在 と を互いに素な整式とする。このとき、 を満たす整式 と が存在する。 （証明） とおく。 ， が に属せば、 である。したがって定理より は， に属するある整式 の倍数の全体である。 とする。 なので， も 互いに素なので， も の倍数である。 つまり は定数である。 しかも， 定数 より は は と の公約数である。 のみではないので は と である。 を満たす。■ は ユークリッドの互除法 （定理）ユークリッドの互除法 整式 の最大公約数を 任意の整式 とする。 に対して、 を で割った余り に対し、 （証明） とし、 とする。 より は は と の公約数である。 の最大公約数が なので， 定理より， の約数である。一方 より， は と 数である。つまり を したがって， 例． と で割った商を から の公約数である。したがって同様の理由から が示された。 とすると，余りが なので、 ■ は の約 の定理 入試問題 京大文系後期 自然数 の関数 を を で割った余り によって定める。 すべての自然数 に対して あなたの好きな自然数 を示せ。 を一つ決めて を求めよ。 その の値をこの設問 におけるあな たの得点とする。 東京農大 を素数、 を 任意の で割り切れない自然数とし、 から に対し， を で割った余りを までの自然数の集合を とおく。 とする。このとき、集合 は と一致す ることを示せ。 は で割り切れることを示せ。 奈良女子大改題 素数 と は に対して、 二項係数についての等式 を証明し、 の倍数であることを示せ。 素数 に対して 自然数 なる整数 に対して を で割った余りを求めよ。 を で割った余りを推測し、 数学的帰納法で証明せよ。 年 阪大後期 は素数、 は正の整数とする。以下の問いに答えよ。 についての式 めよ。ここで、 を展開したときの単項式 は または正の整数で の係数を求 をみたすとする。 が正の整数のとき、 は で割り切れるこ とを示せ。 は で割り切れないとする。このとき、 は で割り切れることを示せ。 年 九州大前期理系 正の整数 ば に対し、 の正の約数全体の和を であり、 ならば で表す。ただし、 及び の正の約数は 自身も約数とする。例え なので となる。次の問に答 えよ。 が正の奇数 と正の整数 を用いて と表されるとする。このとき、 が成り立つことを示せ。 が 以上の整数 と正の整数 を用いて と表されるとする。このとき、 が成り立つことを示せ。また、等号が成り立つのは、 は正の奇数 の形をした偶数 す を求めよ。 かつ 素数であるときに限ることを示せ。 を考える。このとき、 を満た オイラー関数 （定義）オイラー関数 が自然数のとき、 例． の中で のとき、 また、 以外に と互いに素なものの個数を と互いに素な整数は と共通の因数を持つのは のとき、 と表し、オイラー関数という。 の つあるので の つあると考えると、 と互いに素な素数は の つあるので （定理） を素数とする。 の素因数分解が つ。特に が成り立 である。 （証明） から であるとき の素因数は のみであるから、 の間に、 となる の は 個ある。よって 例． のとき、 は の倍数である。このような 個ある。従って から は の間の互いに素な整数 ■ のとき、 （定理） と が互いに素ならば、 （証明） である。 とし， を 以上 以下で もまた同様に選ばれているとする。 と が互いに素なので、 素なので 値を と互いに素で、 で割った余りを である。 を は 逆に 同となる の組は とする。 に変え同様にして は とすると， が 合同でない。よって異なる と互いに 以上 ， 以下の数 より と を法として合同でない。 が異なる場合も、両方異なる場合も同 とも が が と互いに素である。この式の となる をとる。 と互いに素で互いに合同でない整数が少なくとも が存在する。 と とし， 個ある。その一つをとる。 と がとれる。この式の値は、 が と互いに素なので と互いに素、つまり を法として合同でない。よって 様である。 例． となる整数 と互いに素な整数とする。 とも互いに素なので 個存在した。つまり を法として に関して合同でなければ に対する または の組はすべて異なる。 に、 を法として に合 の少なくとも一方に関しても ■ （定理）オイラーの公式 （ は素数、 ）とするとき、 （証明） ■ 例． より、 これをもう少し別な角度から考えてみる。 ある。重複しているのは までの の倍数、 の倍数はそれぞれ、 の倍数であるから、 個 個ある。よって、 例題 を自然数とするとき、 で と の最大公約数が となる自然数 の個数を とする。 を求めよ。 を互いに素な素数とする。このとき を求めよ。 を素数、 を自然数とする。このとき を求めよ。 （解答） と互いに素な 以下の数は の範囲にある と互いに素でない数は が共通なので、互いに素でない数が から の までの数のなかで 。よって の倍数と 個ある。よって、 と互いに素ではないものは、 で割り切れるので、 個ある。よって、 【問題 】 自然数 の倍数でありそれぞれ、 ■ 年 早稲田大学 社会科学 に対して、 以下の自然数で 例えば、 との最大公約数が に対しては、このような自然数は、 、 素数 に対しては であるような自然数の個数を の 個なので、 である。次の問に答えよ。 の値を求めよ。 となる つの素数 を自然数とするとき、 （ただし、 の値を と とする）の組を求めよ。 の式で表せ。 とする。 である。また、 の定理 （補題） かつ ならば （証明）仮定より 。 である。 であるから、 。 よって ■ ならば 例． のとき、 であるが、 （補題） とおき、 の中で と互いに素なものを いに素であるとする。このとき任意の とする。また整数 は に対して と互 を満たす が存在する。 （証明） のときは自明であるから、 である。 かつ である。従って を で割った余りを とする。 となる。また となり、 に対して 例． であるとする。 であるから、 が成り立つので、 と表されるから となる が存在する。この が成り立つ。■ のとき であり、 （定理）（ の中で と互いに素な整数は である。 と互 に対して、 いに素な整数 の定理） ならば （証明） が成り立つ。 の中で であるから、補題より と互いに素なものを はある に が成り立つ。補題より、 とする。ここで である。 を法として合同となるので、 のとき であるから、 は を並びかえたものである。 よって、 が成り立つ。これより、 が得られる。 であるから、 例． のとき、 より、 のとき、 より、 （系）（ ■ の小定理） が素数で ならば が成り立つ。 （証明） が素数のときは であることから明らかである。■ 例題 の下 桁は何か。 （解答） より、 より よって となる。よって、 の下一桁は 【問題 】 の下 【問題 】 を である。 ■ 桁は何か。 で割った余りを求めよ。 が成り立つ。ここで であるから 合同方程式の解法 入試問題 年 九州大 整数を係数とする 次の多項式 について、次のことを証明せよ。 有理数 が方程式 ある自然数 程式 の一つの解ならば、 は整数である。 に対して、 個の整数 のどれもが は有理数の解を持たない。 年 京大後期文系 は 以上の自然数、 は素数、 は整数とし、 次式 を考える。 方程式 が が整数解 を持てば、 で割り切れれば、方程式 年 大阪大学前期理系 イ 次方程式 ロ 不等式 で割り切れることを示せ。 は整数解を持たないことを示せ。 次の条件 イ ロ を同時に満たす整数 は の の組 つの解が共に が成り立つ。 年 千葉大前期 を素数とする。 に関する が整数解を持つのは をすべて求めよ。 次方程式 のときに限ることを示せ。 以上の整数である。 で割り切れなければ方 一次合同方程式 「ある整数を 倍して を満たす で割ると 余る。ある整数を求めよ。」という問題は合同式を用いると、 を求める問題になる。一般に未知数を含む合同式を合同方程式という。 （定理） の場合 ならば合同方程式 の解は を法として唯一つ存在し、 えられる。 （証明） のとき、両辺に をかけて 従って、 は合同方程式 逆に、 が成り立っているとすると 、両辺に の解である。 よって、合同方程式 の定理を適用すると、 の解は をかけて、 のみである。■ 例題 次の合同方程式を解け。 （解答） （解 ） （解 ） ∴ より、 （解 ）ユークリッドの互除法を利用する。 ∴ ∴ （解 ） ∴ ∴ ∴ ∴ ∴ より、 （解 ） より、 （解 ）ユークリッドの互除法を利用する。 ∴ ∴ ∴ 【問題 】次の合同方程式を解け。 ∴ ■ で与 一次合同方程式 一般に と が互いに素でないとき、合同方程式 は解を持つとは限らない。例えば、 は解を持たない。なぜならば、解 を持つとすれば、 を得るが、左辺は の倍数であるのに対して、右辺は （定理） が解を持つための条件は が成り立つことである。 とおけば、 が成り立つことと が成り立つことは同値である。また、その解の個数は （証明） が解 する。このとき、 である。 を持つとすると、 より、 が成り立つことから となる が存在 を得る。 とする。 従って、 が成り立つことと であるから たす は が成り立つことは同値である。一方、 は解を持つ。ゆえに 次に解の個数を考える。 において、 が解を持つ。 と は互いに素であるから、この合同式を満 を法とする一つの剰余類になる。それをそれを で与えられる。 つまり、 と に対する が とすると、合同式の解は を法として合同となるのは、 となるときに限る。したがって、 の値を与えるとき、 余系 は の倍数にならないので矛盾が生じる。 の場合 逆に となる整数 が存在し、 で を を法とする剰 のすべての解が得られる。すなわちその個数 である。 ■ 例題 次の合同方程式を解け。 （解答） （解 ） より、 は解を持つ。 定理より すなわち の解と一致する。 よって、解 を得る。またこの解は法 （解 ） （解 ） では と表される。 ∴ を解くことと同値。 ∴ ∴ ∴ ∴ ∴ ∴ ∴ （解 ） より、 は解を持ち、 を解けばよい。 ∴ （解 ） （解 ） ∴ を解くことと同値。まず、 を解く。 ∴ ∴ ∴ ∴ ∴ 【問題 】次の合同方程式を解け。 ∴ ∴ ■ 連立合同方程式 「 で割ると 余り、 で割ると 余る数は何か」という問題は、連立合同方程式 と して表される。この問題はユークリッドの互除法を用いて解くことができるが、ここでは合同式を利用した 解法について考える。 （定理） ならば、任意の整数 に対して、合同方程式 は解を持ち、その解 を法として一意である。 は （証明）まずは解が存在することを示す。 も解 が成り立つから 次に解が であるから を持つ。このとき は解 を持つ。同様に とおくと、 は解である。 を法として一意に定まることを示す。 も解であるとすると、 が成り立つ。これより すなわち かつ が得られる。ここで が成り立つ。ゆえに解は であるから、 。 を法として一意である。■ 例題 連立合同方程式 （解答） を解け。 より、連立方程式は解を持ち、 を法として一意である。 を解く。 より、 より、 より、 ∴ を得る。これより 【問題 】次の連立合同方程式を解け。 【問題 】次の問に答えよ。 となるので、求める解は で割ると 余り、 で割ると 余る整数は何か。 【問題 】次の連立合同方程式を解け。 【問題 】 で割ると 余り、 で割ると ■ で割ると 余り、 で割ると 余る整数は何か。 余り、 で割ると 余る 桁の自然数を全て求めよ。 合同方程式の解法 が整数係数の多項式であるとき、合同方程式 たす を求めよう。このときは、各係数 を満 をそれと合同な数で置き換えても構わない。特に る係数は消し去ってもよい。このような消去を行った後に で割り切れ なら、この方程式を 次という。 （定理） 法 が素数であるならば、 次の合同方程式 （証明）次数 は 個より多くの解を持たない。 についての帰納法で示す。 のとき、一次の合同方程式 は より、 を法として唯一つ解を有す る。 次のとき、解が 個以下であるとする。 の一つの解を とする。 すなわち このとき除法の原理により、 となる とおくと、 なので、 は る。このとき、 この合同式は 解は 次の多項式 または が が存在する。 は整数が係数の多項式であ と同一の解を有する。 が素数であるから で割り切れるときに限って成り立つ。ゆえに 次の合同方程式 以外の の解でなければならない。帰納法の仮定よりこの解は 以下である。よって は 一般の合同方程式 の解は は、 次以下である。■ がある条件を満たせば解くことができる。それを二段階に 分けて示していく。 （定理） 合同方程式 きる。 を の解は、 の解から構成することがで の一つの解とするとき、 ならば の解の中に であるものが に 関してただ一つある。 ならば の が の解を持つときに、その解から 個の解が構成されるか、 は なる解 を持たない。 （証明） に関する帰納法で示す。 のとき、 の何らかの解 整式 の解は と一致しなければならない。つまり を満たす。従って の解 の解 は、 は を法として の形をしている。ここで に対して、 と展開され、さらに は の 次の整数係数の整式であることに注意する。 を に 代入すると、 ここで は整数である。ゆえにこの展開式の第 で を満たすものを求めることは、 とに帰着する。同様に は で割り切れるので ⅳ ここで つの場合を区別する。 項以下は で割り切れる。よって を満たす を求めるこ のとき、 ⅳ はただ一つの解を持つ。それを だから より、 のとき、 ⅳ は 割り切れるなら任意の が て とする。このとき を得る。これは がさらに の解となる。 で割り切れなければ解がない。 が で が解になる。つまり を満たす。すなわち の形の数 は一つの の解を与えないか、あるいは を法とし 個の解を与える。 のとき、 ら の解 が与えられたとして、 のときの解の構成法を示す。このときも の解を構成したのと同様にできる。すなわち、 のあ たちの数で を満たすものは次の様に構成される。 なら を法としてただ一つ定まる。 なら を法として一つもないか、または のときである。■ 例題 合同方程式 を解け。 （解答） ここで のとき、 とおくと、 ∴ ∴ のとき、 ∴ ∴ よって、 ■ 【問題 】合同方程式 ∴ とおくと、 ∴ を解け。 個ある。 個あるのは の解か 合同方程式の解法 （定理） 法 を素数べきに因数分解して がそれぞれ とするとき、 個の解を持つとすれば、 で与えられる。ここで はそれぞれ （証明） が は 個の解をもち、その解は を法としての の任意の解の一組である。 の解ならば、 従って、 の解である。 を満たす。 逆に を満たす は を満たすから、 を満たす。■ 例題 合同方程式 を解け。 （解答） の解はそれぞれ とする。 は次の ⅰ つある。それらを つの解を持つ。 のとき、明らかに ⅱ のとき、 より、 より、 ∴ ⅲ のとき、 より、 より、 ∴ ⅳ のとき、 より、 より、 ∴ よって 【問題 】合同方程式 ■ を解け。 と 原始根 入試問題 （ 京都府立医大） でない複素数からなる集合 は次を満たしているとする。 の任意の元 の積 は再び ちょうど 個の複素数からなる の例をあげよ。 ちょうど 個の複素数からなる は （ 自然数 の元である。 の例以外にないことを示せ。 京大文系後期） の関数 を を で割った余り によって定める。 すべての自然数 に対して あなたの好きな自然数 の得点とする。 を一つ決めて を示せ。 を求めよ その の値をこの設問 におけるあなた 位数 を法とする剰余系から を除いた各剰余を縦に並べる。それぞれのべきを横方向に順次書いてみる。 が出ればそこからは同じことがくり返される。フェルマの定理によれば いとき， は である。したがって 乗してはじめて の段に が素数で が で割り切れな が並ぶのは当然であるが， ， ，７， と合同であり， しかも途中の １ が を法とする既約剰余系の 代表の組となっている。 オイラーの定理より， を満たす最小の ならば、 である。しかし， が であるかは別の問題であるということである。 （定義）位数 を を満たす整数とする。このとき、 となる最小の する位数という。 オイラーの定理より を法とする位数は 以下である。 例題 （解答） 表より を法としたときの の位数をそれぞれ求めよ。 を法としたときの の位数をそれぞれ求めよ。 ・ ・ ・ に対して の位数は、次のようになる。 位数 までの で割った余りを求める。 を の法 に関 ・ ・ ・ に対して 表より で割った余りを求める。 の位数は、次のようになる。■ 位数 【問題 】 例題 までの なし を法とする より、整数の なし なし なし なし なし の位数を求めよ。 を法とする位数はいずれも の約数となっていることが分かる。位数に関し て次の定理が成り立つ。 （定理） を を満たす整数とする。このとき、 を法とする の位数を とすると、 が 成り立つ。 （証明） である。 かつ だから であ る。 のとき定理は成り立つので， と、 とする。 を得る。このとき であれば の両辺を再び の両辺を で 回割る であれば手続きを終了し、 で 回割る。すると が得られる、 であれば手続きを終了し、そうでなければまた同様の手続きを繰り返す。 この操作によって、いずれある自然数 立する。ところが ばならない。よって を法とする に対して の位数は となり、 かつ であったから、位数の最小性より が成り立つ。■ が成 でなけれ 原始根 （定義）原始根 を を満たす整数とする。 を法とする の位数が に等しいとき， を の原 始根という。 が素数のときは、 が 乗してはじめて と合同になるになる。 （定理） を素数 の原始根とする。このとき、 は を法とする を除くすべての剰余の 集合と合同である。 （証明） とする。原始根の定義より を満たす最小の正の整数は で あるから、 である。よって、 なる異なる と に対して を で割った剰余はすべて異なり、それらは を法として合同である。■ （定理） を素数とし， がちょうど とする。合同方程式 であるもの 個存在する。 （証明）フェルマーの小定理より つ。これら の（ 個の）解で、位数が はちょうど 個の解のうち、位数が であるものの個数を だから、 が成り立つ。また， ここで、 個の解 を持 とおく。先ほどの定理より、 がなりたつので、 であることを示す。 とすれば、 のうちに位数が とする． という が成り立つから， に対して つ存在するので、これを 個の数を考えると、 は合同方程式 の位数が の解である。また， であることから が成り立ち，よって は である元が少なくとも の 個は を法として異なる数である。よって、 のすべての解である。 このうち の位数が であるとすれば、 である。なぜならば、 なる整数 が存在して とすれば、 となって、 の整数の の位数が であることに矛盾する。よって、 は より小さく つでなければならない。ゆえに より，任意の この定理において について である。■ とすれば，次の定理が得られる。 （系）原始根定理 素数 例．素数 に対して、 の原始根がちょうど の原始根は の （ 個存在する。 ）個。 と互いに素である 個 例題 素数 （解答） の原始根をすべて求めよ。 に対して 個存在する。 は の の原始根は の原始根の つである。 と互いに素な正の整数は 個だから、原始根は以下の表の通り。 よって の原始根は 【問題 】素数 【問題 】素数 ■ の原始根をすべて求めよ。 の任意の原始根 に対し、 であることを示せ。 指数 を法とする原始根 ちょうど ただ は， 個のベキ の中に 度ずつ現れるという性質を持つ。よって、 を法とする剰余 を満たす整数 が が を法として つ定まる。 （定義）指数 を素数 す整数 を法とする原始根とする。 を を法とし を底とする を満たす整数 の指数といい、 に対し、 を満た と表す。 例題 素数 （解答） を法とする原始根 に対して、 を求めよ。 を法とする剰余の対応は以下のようになる。 に対応する 素数 ば を法として考えるとき、 を法とする指数 を求めて表にすると次のようになる。（ という記号は を満たす任意の整数 と書いたとき、これは 全体を表すの。このことを など、 とかく。なお、素数 なって剰余が 巡するから、指数を考える際の法は 【問題 】 を法とするとき，次の式を満たす 【問題 】 を満たす 以上 の原始根は を素数 を満たす整数 であることに注意しなくてはならない。 を求めよ。 以下の整数 をすべて求めよ。 を法とする原始根とする。 のとき，次が成り立つ。 を整数とするとき、 （証明） よって よって 例題 のとき． （解答）底を 底 とする指数をとる。 の指数表は次のようになる。 を表す。例え 乗することで （定理）指数法則 ）■ を解け。 ■ と 指数表から、 指数表から ■ （定理） を素数とし とする。二項合同方程式 に解があるための必要十分条件は とするとき である。 （証明） を解くには を解けばよい。今 を法とする原始根 をとって、 とする。この合同方程式が解を有するための必要十分条件は、 で割り切れることである。 とする。 が で割り切れるとき、 が とおけば、 逆に ならば、 。ゆえに は で割りきれる。つまり で割りきれ、二項合同方程式は解をもつ。解があるとき解の数は 例． 実際、既約剰余系 とすると、 個である。■ である。 のうち、 べき剰余 平方剰余 は、 の 個である。 が 平方剰余の相互法則 入試問題 （ 横国大文系後期） 次の問に答えよ． を満たす整数の組 に が存在しないような 正の整数 を小さいものから順 個求めよ。 「正の整数 を で割ったときの余りが ならば、 存在しない」というのは、つねに正しいか理由を述べて答えよ。 を満たす整数の組 が 平方剰余とルジャンドルの記号 を法とする剰余類は となり、 や は平方数を 剰余という。ある整数 整数 であるが、それらの類の数を平方すると剰余類は順に を法とする剰余の中には登場しない。 や は の平方剰余， や は平方非 が整数 を法として平方剰余であるか平方非剰余であるかということと、整数 が を法として平方剰余であるか平方非剰余であるかということとの間にはガウスが整数論の基本定理 と呼んだ大変美しい定理が成り立つ。 （定義）平方剰余、ルジャンドル は の記号 以外の素数とする． が解をもつとき である整数 を に対して の平方剰余、解がないとき平方非剰余という。 が の平方剰余であるか非剰余であるかにしたがって または とする。これをルジャンドル の記号という。 の任意の原始根を底として指数をとるとき、 つまり た。ゆえに が偶数なら に関する は平方剰余，奇数なら非剰余であっ 個の既約類の中で半数は平方剰余のみからなり、 半数は非剰余のみからなる。 なので また、次の の 平方が平方剰余のすべてである。 性質が成り立つ。 ならば これは例えば、 非剰余数 非剰余数 ということである。実際 剰余数 剰余数 非剰余数 非剰余数 のとき、 である。 （定理）オイラーの規準 以上の素数 （証明） と整数 が平方剰余であるための必要十分条件は、 ゆえに ならば、 また ならば、 したがって 例． 一方． に対して である。 で一致。 。ところがフェルマの小定理から でやはり一致する。■ のとき． なのでオイラーの規準から であるから、 は法 に関する原始根であり、 平方剰余の相互法則 が法 に関する平方剰余であるか、非剰余であるかを決定する方法、つまり 的な方法はあるのか。一般に を求める一般 を求める方法は、これは初等整数論の基本問題である。これについてガ ウスが整数論の基本定理と呼んだ大変美しい定理が成り立つ。それが 平方剰余の相互法則である。具体的 には、 を相異なる奇素数とするとき、 平方剰余の相互法則 第一補充法則 第二補充法則 が成り立つことをいう。各法則の意味は次の通りである。 と のいずれもが奇数のときにかぎり である。ゆえに または のとき のとき 相互法則はすでにオイラー ンドル ， ， ～ ～ が多くの実例から帰納的に発見していた。ルジャ がこのような法則の形式で表し、その証明を試みた。彼は その証明の中で、初項と公差が互いに素な無限等差数列 算術級数 のなかに素数が存在することを、証明 なしに用いている。そのため証明は完全ではなかった。 相互法則を最初に完全に証明したのはガウス ， ～ である。ガウスは相 互法則を整数論の基本法則と名づけ、なんと七つのまったく異なる証明を与えた。 さて、この相互法則を証明するための下準備から始める。 （定義）ガウスの予備定理 を で割り切れない数とする。 を で割るとき、その剰余の中に より大きいものが 個あれば、 が成り立つ。 （証明）法 に関する剰余のうち より大きいものについて、それから を引くと，絶対値において より小さい剰余を得る。 を法とする剰余をこのように絶対値で最小になるようにとると、 はそのうち負 な剰余の個数である． の数の絶対値最小な剰余は の中にある。 のなかのどの二つの和も差も のみでなく、 のなかに絶対値が等しいものもない。 と一対一に対応し、そのうち では割りきれないので、 の の 絶対値最小剰余はすべて異なる 個の数は絶対値をとると 個が負である。よって すなわち ゆえにオイラーの規準から である。ところが両辺とも 例． のは でかつ のとき である。 のみである。したがって 実際、法 が奇数なので を が成り立つ。■ で割った剰余は である。 より大きいも で に関する平方剰余は であり、 が非剰余である。 （定理）第一補充法則 （証明）オイラーの規準を で用いると、 は奇数であるから、 ■ （定理）第二補充法則 （証明）ガウスの予備定理を で用いると、 このうち 個である。 より大きいもののは のなかの は より小さいものの個数でもある。 と同値であるから、その個数は が奇数ならここまで、 が偶数なら までである。よって より小さい奇数 すなわち ■ （定理）平方剰余の相互法則 （証明） 平面上に点 直線 を引く。点 として、 で、 は 直線 を と をとり点 とする。 の内部で直線 で割った絶対値最小剰余を 上の格子点で とする。 上に格子点はない。さて、 とする。直線 と直線 の交点が にもっとも近いものとの距離になり、この格子点が よ り上にあるとき は負である。 ガウスの予備定理を 各 が に対して 直線 で考えると、そこにおける 上 より上にあり、距離 より小さい格子点の個数である。いま直線 の正の方向に 行四辺形 だけ平行移動した直線を を を 軸 する。 は平 の内部にある格子点の個数である。 となる 同様にガウスの予備定理で 線 は 軸の正の方向に は直 だけ平行移動した直線を とするとき、平行四辺形 の内部にある格子点の個数 である。 における 小四角形 は この二つの平行四辺形の内部にある格子点の個数である。 を付け加えて 六角形 は 角形 の内部の格子点の個数もやはり の中点 である。六 を対象の中心として点対称である。したがって六角形 内の格子点は が格子点であるときはこれを除いて その他の格子点は対象の 中心に関して二つずつ組になっている。 したがって が奇数であるか偶数であるかは、点 によって決まる。つまり 自身が格子点であるかないか が奇数であるのは、 なので、これは がともに整数 となるときにかぎる。 がともに奇数になることと同値である。よっ て相互法則が証明された、■ 例． 第 補充法則 相互法則、第 補充法則 相互法則、第 、第 相互法則、第 相互法則 相互法則、第 、第 補充法則 補充法則 補充法則 ガウス整数環の基本定理 入試問題 （ 東京大学理系前期） を素数、 を互いに素な正の整数とするとき、 は実数でないことを示せ。ただし、 は虚数 単位とする。 （ 一橋大学前期） を整数とし、 とする。 整数 を満たすものが存在するような と でない整数 で は虚数単位である。 で求めた全ての に対して、方程式 を解け。 を全て求めよ。ただし、 ガウス整数 （定義）共役、ノルム、絶対値 を複素数とするとき、次のように定義する。 の共役 の絶対値 のノルム （定理）複素数の性質 ならば ならば （三角不等式） （証明） とすると、 ■ （定義）ガウス整数（複素整数） 複素数 において、 素整数全体の集合を ともに整数である複素数をガウス整数、または複素整数と呼び、複 と表す。 通常の整数を複素整数と区別して有理整数と呼ぶこともある。 また つのガウス整数 には和，差 ，そして積 が自然に定まり、それらはガウス整数であ る。和および積の結合法則、そして和と積を結びつける分配法則が成り立つ。このとき、代数学の用語では 集合 が環（ ）であるというので，これをガウス整数環と呼ぶ。 （定理）複素整数の除法 に対して、 となる が存在する。 （証明） とおく。 とすると、 とおくと、 ■ 例． となる しかい、一意とは限らない。実際、 を求める。 とすると、 約数、倍数、単数、同伴数 （定義）約数、倍数 に対して、 す。 を となる の倍数、 を が存在するとき、 は 公約数の中で、ノルムが最大のものを最大公約数、公倍数の中で 小公倍数という。 で割り切れるといい、 を除きノルムが最小のものを最 の最大公約数、最小公倍数をそれぞれ 例． と表 の約数 と呼ぶ。公約数、公倍数の定義は整数の場合と同じである。 で表す。 とする。 と の最大公約数は と の最小公倍数は （定義）単数、同伴数、正規型 全てのガウス整数の約数であるガウス整数を 単数といいう。 が単数であるとき、 と た、同伴数のうち、第 複素数 は同伴であるという。 の同伴数は の 個である。ま 象限にあるものを正規型であるという。 の同伴数は、 の つである。互いに同伴な つの複素数は、複素平面上で 転させた位置にあるので、そのうちの つは、偏角が ずつ回 より大きく 以下となる。 （定理） の単数 の単数は の 個である。 （証明）全てのガウス整数の約数なので、 の約数でもある。その単数を とすると、 逆に のとき、明らかに は全てのガウス整数の約数となる。■ 素数 （定義）素数 ガウス整数 について、 自身と単数を 自明な約数といい、それ以外の約数を 真の約数 という。 が真の約数を持たないとき 素数 であるという。素数以外の 合成数 と呼ぶ。有理整数の素数を特に区別 して 有理素数 と呼ぶことがある。 例． は素数 は と分解できるので合成数 （定理） ガウス整数 （証明） のノルム が有理素数ならば は素数である。逆は成り立たない。 が合成数だとすると、単数以外の を用いて これが有理素数であるから、 のどちらかが単数である。よって、 が単数であるという仮定に反す る。 逆に とすると、 より とすると、 例． は有理素数とならない。■ よって とすると、 は素数。 よって、 とすると、 は素数。 は合成数。 例題 有理素数 （解答） は素数化合成数か判定せよ。 が合成数だとすると、単数以外の を用いて、 と表すことができる。 より、 例えば が合成数だとすると、単数以外の を用いて、 よって合成数 と表すことができる。 より、 このような が合成数だとすると、単数以外の を用いて、 が存在しない よって素数 と表すことができる。 より、 例えば 【問題 】有理素数 よって合成数 ■ は素数化合成数か判定せよ。 （定理） 型の有理素数は素数である。 （証明）有理素数 が合成数であると仮定すると、単数以外の を用いて、 と表すことができる。 より、 とおくと、 は奇数なので、 とすると、 も奇数。よって、 のいずれかが奇数で、いずれかが偶数。 より矛盾。よって は素数。■ は素数。 例． （定理） 型の有理素数は合成数である。 （証明） とおく。平方剰余の第一補充法則より、 よって に対して、 が素数であると仮定すると、 は または の約数。つまり、 または しかい、 より、このようなことはありえない。よって 例． は素数ではない。すなわち合成数。■ （定理） 型の有理素数は、 つの互いに共役である素数の積 で表せる。この つの素数は同伴数で はない。 （証明） とおく。 は合成数なので、単数でない を用いて より、 よって は素数である。 とおくと、 ここで、 より、 また、 が同伴数であると仮定すると、 より、 が単数とならなければならない。しか し、 より、 または 例． となることもなく、 となることもないので同伴数ではない。■ （定理） を素数とするとき、 （証明） は有理素数である。 とする。 は で割り切れる自然数の中で最小のもの。 は単数でないから、 もし、 がガウス整数の合成数なら は素数だから、 または は有理素数。■ 例． とおける。 。しかし、 がこのような自然数の中で最小であることに矛盾。よって ガウス整数の因数分解 （定理）ガウス整数間の基本定理 全てのガウス整数は、単因子の違いを除き、ただ一通りの方法でガウス素数の積に分解できる。 （証明）（分解可能性）任意のガウス整数 が素数ならば題意を満たす。 が素数でないとき、有限個の約数を持つ。もし有限でないとすると、同じノルムを持つ素数は有限個であ るから、それらのノルムを小さい方から順に並べると、 となり、 自身が有限であることに反する。つまり 小のものを とすると は素数である。 は有限個の約数を持つ。その約数の中でノルムが最 とおく。 が素数なら題意を満たす。 が素数でない とき、これを繰り返すことにより、 は有限個の積に分解することができる。 （一意性の証明） が次のように 通りに因数分解されたとする。 は全て素数で、等しいものがあってもよい。 どれかが に等しい。これを とし、 を より、 の中の で割ると、 同様に繰り返していけば、 よって、 また、 ■ 以上のことから、ガウス整数を因数分解していく。次のような手順で考える。 実部と虚部が共通因数であるときは先に行う。 や 型の素数は分解できる。 ガウス整数 の因数を探すには、まず 分解できない。 が が または の因数を探す。 型の素数を持つなら、それを の因数となる。 例題 次のガウス整数を因数分解せよ。 （解答） ■ 【問題 】次のガウス整数を因数分解せよ。 が素数ならば、もうこれ以上因数 で表すと、 ピタゴラス数 入試問題 （ 旭川医科大学） はどの つも が， 以外の共通な約数をもたない正の整数とする。 を満たしているとき，次の問いに答えよ。 は奇数であることを示せ。 （ の つは の倍数であることを示せ。 の つは の倍数であることを示せ。 一橋大学） 次の条件 する。 をみたす直角三角形を考える．ただし、斜辺の長さを は自然数で、そのうちの少なくとも その他の つは素数である。 のどちらかは偶数であることを示せ。 の組をすべて求めよ。 （ お茶の水女子大学） 各辺の長さが整数となる直角三角形がある。 この直角三角形の内接円の半径は整数であることを示せ。 この直角三角形の三辺の長さの和は三辺の長さの積を割り切ることを証明せよ。 辺の長さを と ピタゴラス数 （定義）ピタゴラス数 辺の長さが の直角三角形は、 を満たす。等式 を満たす自然数 の組をピタゴラス数といい、それらの最大公約数が であるも のを 既約なピタゴラス数 という。 最も簡単なピタゴラス数は である。 もピタゴラス数である。これら以外にどんなピ タゴラス数があるだろうか？ 紀元前 から 年頃のものと推定されるバビロニアの粘土板には， 組からなるピタゴラス数の 表が楔形文字で残されている。さらに，驚くべきことにバビロニア人はピタゴラス数を利用して原始的な 三角関数表まで作っていた。 （補題 ） 自然数 に対して、 が偶数ならば、 は の倍数である。 （証明） が偶数なので、 は偶数である。よって、 り、 の倍数となる。■ は とおける。このとき、 とな （補題 ） 自然数 を を満たす既約なピタゴラス数とする。このとき、 は奇数と偶数の 組み合わせとなる。 （証明） がともに奇数とすると、 とおける。このとき、 は偶数となるが、 の倍数とならないので矛盾（補題 ）。よって、 は互いに素なので、ともに偶数となることもない。よって、 はともに奇数とはならない。また、 は奇数と偶数の組み合わせとなる。■ （定理） を、次の 条件を満たす整数とする。 は偶・奇の組み合わせ このとき、 は既約なピタゴラス数となる。つまり、 また逆に、全ての既約なピタゴラス数は が成り立つ。 の形に表すことができる。 （証明） 次に既約であることを示す。 よって、 は の公約数を の約数とならなければならないので、 とする。 より、 または が偶・奇の組み合わせより、 は奇数となるので、 えない。よって、 となり、 既約なピタゴラス数 が成り立つとする。補題 とおくと、 は既約である。 に対して、 より、 を奇数、 を偶数としてもよい。 より、 となる。 はあり 中心が原点、半径 の円周上に 点 と とり、直線 線の足を 軸との交点を 点 とする。このとき、 において、 直線 を から 軸に下ろした垂 ∽ で なので、 の方程式は でない方が より、 なので、円 との交点で、 である。 なので、 とおき、 ここで、 に代入すると、 の公約数を考える。 より、公約数は か しかありえない。 のどちらかが偶数で、どちらかが奇数のとき、 は奇数、 は偶数 は偶数、 は奇数 しかし、 を奇数、 を偶数としているので は奇数、 は偶数 ■ （別解）（途中から） とおくと、 において、 ここで、 より、 より、 （以下同様）■ より、 のいずれも奇数のとき、 ピタゴラス数を生み出す行列 というピタゴラス数があり、そこから 次の図を見てみよう。中心に 本の枝に別れ、またそこに というピタゴラス数が派生してくる。そこから更に 本に枝分かれして、ピ タゴラス数が現れてくる。 実はこの枝分かれの仕組みはたった つの行列からできているのである。この図をピタゴラス・ツリー と名付けよう。 （定義）ピタゴラス行列 この行列は数人によって、独立に発見されたといわれている。 ・ ・ ・ このピタグラス行列には という特徴がある。 それではこのピタゴラス行列からどのようにピタゴラス数を作っていくのかを説明しよう。 ピタゴラス数 から新たなピタゴラス数 ツリーでみたように、 種類の派生が生まれる。これを タゴラス数 から、次のように作成する。 を作成するにあたって、先ほどのピタゴラス・ とすると、それぞれのタイプは、もとのピ タイプ タイプ タイプ 作成された数の組をピタゴラス行列 で変換する。この変換をピタゴラス変換という。 （定義）ピタゴラス変換 変換された 数がまたピタゴラス数となっていることは容易に確かめることができる。 例題 （ピタゴラス変換） ピタゴラス数 からピタゴラス変換を用いてピタゴラス数を求めよ。 （解答）タイプ タイプ タイプ タイプ タイプ タイプ 【問題 】 ピタゴラス数 ■ からピタゴラス変換を用いてピタゴラス数を求めよ。 パラメータを用いたピタゴラス変換 前節で、ピタゴラス数は 変数 を用いて次のようにあらわされ ることを証明した。 ここで、 は正の整数で、 は偶・奇の組み 合わせである。 更に とおくことで、単位円周上に 点 をとり、直線 と 軸との有利点 を対応させることができた。このとき、次の関係式が成り立つ。 これを用いればピタゴラス数の から、条件を満たす新たな を生み出す変換を見つければよいことに なる。 先ほどのピタゴラス数を生み出す行列は次の変換を元に作られていた。 （定義）パラメータ を用いたピタゴラス変換 同様にしてピタゴラス数の から、条件を満たす新たな （定義）パラメータ を用いたピタゴラス変換 を生み出す変換は次のようになる。 例題 （パラメータを用いたピタゴラス変換） ピタゴラス数 から次のピタゴラス変換を用いてピタゴラス数を求めよ。 パラメータ を用いる （解答） パラメータ タイプ タイプ タイプ タイプ タイプ タイプ タイプ タイプ タイプ を用いる タイプ タイプ タイプ 【問題 】 ピタゴラス数 パラメータ を用いる ■ から次のピタゴラス変換を用いてピタゴラス数を求めよ。 パラメータ を用いる
© Copyright 2024 ExpyDoc
