初等整数論 | 天游ヶ丘数理学院

概要

本単元は、整数について「割り切れるかどうか」「余りが等しいかどうか」を問い、初等的な手段だけでその構造を調べます。除法の原理とユークリッドの互除法から始め、素因数分解の一意性、一次不定方程式、記数法を扱い、合同式によって余りの計算をまとめます。さらに中国剰余定理、フェルマーの小定理、オイラーの定理へ進み、無限降下法によって解が存在しないことを証明する方法を扱います。その到達点として、本単元はフェルマーの最終定理の $n = 4$ の場合を、初等的な手段だけで証明します。

本単元は、扱う範囲を、代数的な一般論を用いずに到達することができるところに限ります。それでも、除法と剰余、素因数分解の一意性、既約な元、余りの世界における乗法の構造は現れます。これらは、大学の代数学が一般の環や体について論じ直す対象です。読者は、整数という具体的な対象について計算しながら、その内容を先に経験することができます。

この単元のねらい

本単元は、読者が次に掲げる能力を習得することを目標とします。

除法の原理によって商と余りを定め、ユークリッドの互除法によって最大公約数を求めることができます。
素数と合成数を区別し、素因数分解の存在と一意性を証明し、約数と倍数の構造を説明することができます。
一次不定方程式 $ax + by = c$ の整数解が存在する条件を判定し、すべての解を記述することができます。
位取り記数法によって整数を表し、底の異なる表示の間で変換することができます。
合同式を等式と同じように計算し、法の取り方と、それによって判定することができる性質との対応を説明することができます。
中国剰余定理によって、複数の余りの条件を一つの条件にまとめることができます。
フェルマーの小定理とオイラーの定理を、適用に必要な条件を確かめたうえで用い、累乗の余りを求めることができます。
無限降下法によって、方程式が整数解をもたないことを証明することができます。
原始ピタゴラス数の一般形を導き、それを用いて $x^4 + y^4 = z^4$ に正の整数解がないことを示すことができます。
連分数によってユークリッドの互除法を書き直し、実数を有理数で近似することができます。

前提知識

本単元は、「数と式の計算」で扱う整式の除法と剰余の考え方を用います。整数の除法と整式の除法は同じ形をしているので、読者は両者を対応させながら読むことができます。

本単元は、「集合と論理」で扱う背理法、対偶、数学的帰納法、および「すべて」「ある」を含む命題の扱いも用います。素因数分解の一意性と無限降下法の証明は、これらの論法を明示的に用います。とくに発展２と応用の記事では、読者が量化子を含む主張を自分で立てる場面があるため、これらの記事は同単元の発展・応用を前提とします。

この単元を貫く4つの方針

本単元の各記事は、次の4点を共通の方針とします。

除法と余りへ帰着させます。 整除、互除法、合同式、記数法は、いずれも整数を割ったときの商と余りという一つの操作から整理することができます。各記事は、新しい記号を導入するときに、その記号が除法の何を言い換えたものかを述べます。
存在と一意性を分けて示します。 素因数分解、一次不定方程式の解、剰余による表示について、そのようなものが存在することと、それがただ一通りであることは別の主張です。各記事は、どちらを示しているかを毎回明示します。
存在しないことを示す論法を用います。 解が見つからないことは、解が存在しないことの証明になりません。各記事は、剰余による矛盾や無限降下法のように、存在しないことを直接に示す方法を用います。
法を選ぶ根拠を示します。 合同式では、どの法で考えるかによって判定することができる事柄が変わります。各記事は、平方数、累乗、桁数などの条件に応じて、有効な法を選ぶ根拠を述べます。

難易度区分

本単元は、17記事を「基礎」4記事、「発展１」7記事、「発展２」5記事、「応用」1記事に分けます。

基礎と発展１は、本単元の中心となる内容です。基礎では、除法と互除法によって整数を直接に扱います。発展１では、合同式を導入して、余りそのものを計算の対象とします。この二つを読み終えた読者は、除法の原理、素因数分解の一意性、中国剰余定理、フェルマーの小定理とオイラーの定理、および無限降下法による非存在の証明を、自分で再構成することができます。この11記事は本単元で必ず読む内容であり、順に読むことを想定しています。

発展２の5記事と応用の1記事は必修ではなく、読者は関心に応じて選んで読むことができます。発展２では、余りの世界におけるべき乗の周期と、平方数になるかどうかという二つの問いを扱い、大学で学ぶ代数的整数論の内容を初等的な範囲で先取りします。応用では、基礎と発展で揃えた定理を、実際の問題へ当てる技法を扱います。

基礎

基礎の記事は、計算の分量を十分に取りながら、整数の除法と剰余の構造を解説します。読者が互除法や素因数分解を、手順としてだけでなく、なぜその手順で求まるのかまで理解することができるようにします。各記事が扱う内容は、次のとおりです。

整除・余りとユークリッドの互除法 — 除法の原理によって商と余りがただ一通りに定まることを示し、整除の記号と基本の性質を導入します。ユークリッドの互除法によって最大公約数を求め、余りの列が有限回で終わる理由と、この手順で最大公約数が得られる理由を確かめます。
素数と素因数分解 — 素数と合成数を定義し、素因数分解が存在することを数学的帰納法によって、一通りに定まることをユークリッドの補題によって証明します。あわせて、約数の個数と総和、最大公約数と最小公倍数を素因数分解から求める方法、および素数が無限に存在することを扱います。
一次不定方程式 ax + by = c — 整数解が存在するのは、 $a$ と $b$ の最大公約数が $c$ を割り切る場合に限ることを示し、互除法を逆にたどって解を一つ構成します。そこから一般解の形を求め、解の全体が整数を一つ選ぶごとに定まる形で書けることを確かめます。
記数法 — $2$ 以上の底を定めた位取り記数法によって整数を表し、その表し方が存在してただ一通りであることを除法の原理から導きます。底の変換、 $n$ 進法における四則計算、および桁数と数の大きさの関係を計算します。

発展１

発展１の記事は、余りそのものを計算の対象とする技法を解説します。合同式を導入すると、基礎で個別に扱った事実を、一つの計算としてまとめることができます。各記事が扱う内容は、次のとおりです。

合同式の計算 — 正の整数を法に固定した合同関係を定義し、加法、減法、乗法が保たれることと、除法には条件が必要であることを示します。合同式による累乗の計算、剰余類の考え方、および法を選んで整数の性質を判定する方法を扱います。
中国剰余定理 — どの二つも互いに素である複数の法についての合同式が、一つの合同式にまとまることを示します。解が存在することと、法の積を法として一通りに定まることを証明し、解を具体的に構成する手順を示します。
フェルマーの小定理とオイラーの定理 — 法が素数 $p$ であり、 $p$ が $a$ を割り切らないとき、 $a$ の $p-1$ 乗が $1$ と合同になることを示し、一般の法に対するオイラーの定理へ広げます。適用に必要な「互いに素」という条件を明示し、累乗の余りが周期をもつことと、指数が大きい場合の計算に用います。
オイラー関数 φ とその乗法性 — $n$ 以下で $n$ と互いに素な正の整数の個数として $\varphi(n)$ を定義し、素数のべきに対する値と、互いに素な二数についての乗法性を示します。素因数分解から $\varphi(n)$ を計算し、オイラーの定理と組み合わせて用います。
無限降下法 — 自然数の空でない集合には最小の要素があることを、この論法の根拠に置きます。反例の全体が空でないと仮定し、その最小の反例よりも小さい反例を構成して、矛盾を導きます。存在しないことを示す論法としての位置づけと、数学的帰納法との関係も述べます。
フェルマーの最終定理 n = 4 — $x^4 + y^4 = z^2$ が正の整数解をもたないことを無限降下法によって証明し、そこから $x^4 + y^4 = z^4$ の場合を導きます。準備として原始ピタゴラス数の一般形を導き、証明の中で二度用います。より強い主張を証明したほうが降下が閉じる理由も述べます。一般の指数に対する決着は扱いません。
連分数 — ユークリッドの互除法を連分数展開として書き直し、有限連分数と有理数が対応することを示します。近似分数を計算し、実数を有理数で近似する精度を調べます。

発展２

発展２の記事は、余りの世界におけるべき乗の周期と、平方数になるかどうかという二つの問いを軸として、位数、原始根、平方剰余を解説します。これらの結果が使われる場面として、公開鍵暗号とペル方程式の解法も扱います。各記事が扱う内容は、次のとおりです。

位数と原始根 — 法 $n$ と互いに素な元について、その位数を定義し、位数がオイラー関数の値を割り切ることを示します。原始根を定義し、法が素数のときに原始根が存在することを証明して、べき乗が繰り返す周期の構造を記述します。
平方剰余とルジャンドル記号 — 奇素数 $p$ を法として、平方数となる剰余とそうでない剰余を分類し、ルジャンドル記号を定義します。オイラーの規準によって平方剰余であるかどうかを判定し、この記号が乗法的であることを示します。
平方剰余の相互法則 — 相異なる二つの奇素数の間に成り立つ平方剰余の関係として相互法則を述べ、あわせて $-1$ と $2$ についての補充法則を述べます。これらを用いて、与えられた合同方程式が解をもつかどうかを判定します。
RSA と計算数論 — オイラーの定理を基礎として、公開鍵暗号の仕組みを説明します。暗号化と復号が互いに逆の操作になる理由、鍵の作り方、および素因数分解が難しいことを安全性の前提に置いている点を扱います。
ペル方程式と連分数 — 平方数でない正の整数 $D$ について、 $x^2 - D y^2 = 1$ の整数解を、 $\sqrt{D}$ の連分数展開によって求める方法を扱います。基本解を一つ求めると、そこからすべての解が生成されることを示します。

応用

応用の記事は、基礎と発展１・発展２で揃えた定理を、実際の問題へ当てる技法を解説します。ここでは新しい定理を導入せず、どの定理をどの場面で用いるかという判断が課題になります。

競技数学入門 — 必要な定理は基礎と発展で揃っているという前提のもとで、技法の選び方に絞って扱います。どの法で考えるか、どの素数の指数に着目するか、どの量を最小にして降下させるかという判断の根拠を示します。分野を横断する発想の一般的な扱いは「雑多な話題」で扱います。

学習到達点の確認方法

同じ題材であっても、本単元が確かめる内容は区分によって異なります。

基礎では、読者が互除法、素因数分解、一次不定方程式の解法、記数法の変換を正確に実行することができるかを確かめます。あわせて、存在と一意性のどちらを示しているかを区別し、手順が正しい理由を説明することができるかを確かめます。
発展１では、読者が合同式を計算の道具として用い、適用に必要な条件（互いに素であること、法が素数であること）を明示することができるかを確かめます。無限降下法については、降下の各段階と矛盾の所在を示すことができるかを確かめます。 $n = 4$ の場合の証明については、新しく作った組が同じ方程式の解であることと、比較する量が小さくなっていることの両方を示すことができるかを確かめます。
発展２では、読者が位数と平方剰余を計算し、それによって合同方程式が解をもつかどうかを判定することができるかを確かめます。
応用では、読者が問題の形から、有効な法と着目すべき量を自分で選ぶことができるかを確かめます。

本単元は、演習に、最大公約数、余り、解の個数のように答えが一意に定まる計算問題を用います。一意性と非存在に関する主張については、論法の構造、用いた条件、各段階の根拠を含む解答を評価の対象とします。読者が具体例によって観察した内容は予想を立てるための手段であり、証明とは区別して扱います。

前後の単元との関係

数と式の計算 — 同単元が扱う整式の除法、剰余の定理、因数定理は、本単元の整数の除法、合同式、素因数分解と同じ形をしています。本単元は、両者を対応させながら進みます。
集合と論理 — 本単元は、同単元で扱う背理法、数学的帰納法、量化子を含む主張の扱いを、整数についての証明に用います。
場合の数と確率統計 — 本単元は、約数の個数とオイラー関数の計算において、同単元で扱う数え上げと包除原理を用います。
初等整数論ギャラリー — 本単元は、整除と互除法、素因数分解の一意性、合同式、無限降下法、位数、平方剰余、連分数という道具を導入します。同単元は、これらの道具が二平方和定理やウィルソンの定理のような個々の定理を実際に証明する場面を扱います。
雑多な話題 — 本単元の無限降下法は、同単元で扱う極端原理と同じ考え方によります。分野を横断する論法としての一般的な扱いは、同単元で扱います。
離散数学とアルゴリズム — 同単元は、本単元の互除法と剰余の計算を手続きとして扱い直し、入力の大きさに応じて計算の手数がどれだけ増えるかを評価します。本単元は、これらの手順が正しい答えを与える理由までを扱います。
環論入門 — 同単元は、本単元の除法の原理と素因数分解の一意性を、ユークリッド整域と一意分解整域へ一般化します。
体論入門 — 同単元は有限体を扱います。本単元が示す、法が素数のときの原始根の存在は、有限体の乗法群が巡回群であることと同じ主張です。
群論入門 — 同単元では、本単元のフェルマーの小定理とオイラーの定理が、ラグランジュの定理の特別な場合として現れます。本単元の位数と原始根の議論は、巡回群の一般論の具体例にあたります。
代数的整数論 — 同単元は、代数体の整数環におけるイデアルの分解と類数を扱います。本単元が整数について示す素因数分解の一意性は、同単元で一般の整数環に対して問い直されます。

教育課程上の位置づけと参考年次

参考年次を日本の高校の学年で示すと、基礎の4記事が扱う約数と倍数、ユークリッドの互除法、二元一次不定方程式、記数法は数学Aに置かれ、高校1年から2年が目安です。発展１以降の13記事には、日本の課程で対応する項目がありません。したがって本単元は、これらの記事について学年の目安を示しません。国によって対応する学年は異なります。

初等整数論は、独立した必修内容として置かれる国が限られ、選択科目や課外の教材で扱われることが多くあります。各国の課程は、同じ内容を異なる学年や科目に置いています。以下は、その配置を比較するための参考です。本単元の発展と応用に置く記事の多くは、いずれの国でも通常の高等学校の必修課程には含まれません。

日本 — 高等学校学習指導要領（平成30年告示）の「数学A 数学と人間の活動」に主として対応します。同要領は約数と倍数、ユークリッドの互除法、二元一次不定方程式、記数法を扱います。合同式以降の内容は、同要領の内容として明示されていません。
韓国 — 2022改訂教育課程は、初等整数論を高等学校の独立した内容として置いていません。約数、倍数、素因数分解は初等・中等段階で扱われます。
中国 — 普通高中课程方案和语文等学科课程标准（2017年版2020年修订）は、必修課程および選択性必修課程に、初等整数論を独立した主題として置いていません。同課程標準の選修課程には、大学進学や競技数学に向けた発展的な内容を置く枠が用意されています。
米国 — 連邦教育省の説明のとおり、教育基準は州が定めます。比較資料として Common Core State Standards for Mathematicsを用いると、同基準は最大公約数と最小公倍数をGrade 6の「The Number System」で扱うにとどまり、合同式や不定方程式をHigh Schoolの標準に含めていません。
フランス — lycée général et technologiqueの数学課程では、 terminaleの選択科目「mathématiques expertes」に置かれる「Arithmétique」に主として対応します。同科目は整除、合同、最大公約数、ベズーの定理、フェルマーの小定理などを扱います。
ドイツ — 各州が学校課程を定め、 KMKが全国共通の到達基準を示します。 KMKの一般大学入学資格向け数学基準は、初等整数論を独立した内容領域として置いていません。素因数分解や記数法は中等段階Iで扱われ、合同式や暗号への応用は、州や学校が定める選択・深化の内容として扱われる場合があります。
イギリス（England） — National Curriculum: mathematics programmes of studyの Key stage 3・4では、素因数分解、最大公約数、最小公倍数を扱います。 GCE AS and A level mathematicsは必修内容に合同式や不定方程式を含まず、Further Mathematicsの選択問題として扱う試験団体があります。

§A4初等整数論全17項目

概要