数論

初等整数論

初等整数論の表紙

概要

本テキストでは、整数の性質について取り扱う。 整数の性質についての研究は初等幾何学と並んで、最も古い数学の分野のひとつである。直角三角形の3辺の長さとなる正の整数、つまり $$a^2+b^2=c^2$$ となる正の整数 $a, b, c$ の組は非常に古く、古代バビロニアや古代エジプトでも知られていたと考えられている（たとえばバビロニアの粘土板プリンプトン322には $65^2+72^2=97^2$, $12709^2+13500^2=18541^2$ をあらわすと思われる記述がある）。$6$ の（$6$ 自身を除く）約数の和が $6$ に一致し、$28, 496, 8128$ も同様の性質をもつことは、古代ギリシアのピタゴラス教団では知られており、完全数と呼ばれ崇拝の対象となっていた。ユークリッドの「原論」では公倍数や公約数、素数に関する基礎的な定理が記されている。 本テキストでは、こうした整数の性質や関係について取り扱う。

目次

  1. 整数列

    本章では、整数列について議論する。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. 二項係数
    2. 線形回帰数列

  2. 整除性

    倍数、約数、素数、合同式といった整数論における基本的かつ重要な概念は整除関係（ある整数が別の整数を割り切る関係）により定義される。したがって整除性は整数論の最も重要なテーマと言ってもよい。本章では整除性によって定まる、整数論における重要な概念について取り扱う。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. 倍数と約数
    2. 倍数と約数（公倍数と公約数に関するその他の事実）
    3. Euclidの互除法とBezoutの補題
    4. 素数
    5. 素因数分解

  3. 合同式

    合同式は、2つの整数を、ある与えられたもうひとつの整数で割ったときの余りが一致していることを言っている。言い換えれば、整数全体を、与えられた整数で割った余りで類別したときに同じ類に属していることを言っている。したがって、合同式について考えることは、整数を整数で割った余りについて考えることである。本章では、合同式に関する基本的な性質と、その応用について解説する。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. 合同式の導入
    2. Fermatの小定理とEulerの定理
    3. 乗法的位数
    4. 多項式の合同の基礎
    5. 原始根と指数
    6. 中国式剰余定理
    7. 平方剰余
    8. 合成数を法とする合同式
    9. Carmichael関数

  4. 円分多項式

    $1$の冪根を解にもつ多項式、およびその値の性質について解説する。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. 円分多項式
    2. 円分多項式の値

  5. Lucas数列

    2階の[線形回帰数列](/textbooks/初等整数論/整数列/線形回帰数列)の中でも、数論上重要な性質をもつ特別なものについて取り扱う。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. 定義と例
    2. 関係式
    3. 整除性および合同
    4. LTEの補題
    5. 原始素因数

  6. 数論的関数

    正の整数に対して定義される関数を数論的関数 (arithmetic function) という。本章では、主要な数論的関数の基本的な性質および加法的関数と乗法的関数の概念について解説する。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. 素因数の個数
    2. 約数関数
    3. Eulerのtotient関数
    4. 加法的関数と乗法的関数
    5. メビウス関数
    6. 接合積
    7. メビウスの反転公式
    8. 約数総和関数
    9. Dirichlet級数

  7. 素数の分布

    この章では、素数の個数に関する初等的な結果を証明する。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. $x$ 以下の素数の個数
    2. Chebyshev関数の初等的評価
    3. ζ関数
    4. Mertensの定理

  8. 素数判定

    本章では、与えられた数が素数であるか否かをどのように判定するかについて解説する。

    $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$
    1. 合同式に基づく古典的な素数判定法
    2. Fermat数

参考文献

[1]
G. H. Hardy and E. M. Wright, revised by D. R. Heath-Brown and J. H. Silverman, An Introduction to the Theory of Numbers, 6th Ed., Oxford University Press, 2008
[2]
G. H. Hardy and E. M. Wright, 訳: 示野 信一、矢神 毅, 数論入門I 原書6版, 数学クラシックス, 丸善出版, 2022
[3]
G. H. Hardy and E. M. Wright, 訳: 示野 信一、矢神 毅, 数論入門II 原書6版, 数学クラシックス, 丸善出版, 2022
[5]
D. P. Parent, Exercises in Number Theory, Springer-Verlag, 1984
[6]
Trygve Nagell, Introduction to Number Theory, Reprint Edition, American Mathematical Society (original: John Wiler & Sons, Inc.), 2001
[7]
Paulo Ribenboim, The New Book of Prime Number Records (3rd ed. pbk.), Springer, 2013
[8]
Martin Davis, Hilbert's Tenth Problem is Unsolvable, Amer. Math. Monthly, 1973, 233
[9]
Edouard Lucas, Théorie des nombres, Gauthier-Villars, 1891
[10]
Edouard Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math., 1878, 184
[11]
D. P. Parent, Exercices des théorie des nombres, BORDAS, 1978
[12]
H. C. Pocklington, The determination of the prime or composite nature of large numbers by Fermat's theorem, Proc. Cambridge Phil. Soc., 1914, 29
[13]
D. H. Lehmer, Tests for primality by the converse of Fermat's theorem, Bull. Amer. Math. Soc., 1927, 327
[14]
John Brillhart and J. L. Selfridge, Some factorizations of $2^n\pm 1$ and related results, Math. Comp., 1967, 87
[15]
F. Proth, Théorèmes sur les nombres premiers, C. R. Acad. Sci., 87, 926