整数

更新日時 2023/02/26

連続するn個の整数の積と二項係数

整数論の有名な公式

連続する $n$ 個の整数の積は $n!$ の倍数である。

上記の公式について，3通りの証明を紹介します。

→ 連続するn個の整数の積と二項係数

ルジャンドルの定理（階乗が持つ素因数のべき数）

ルジャンドルの定理

$n!$ に含まれる素因数 $p$ の数は以下の式で計算できる：

${\displaystyle \sum_{i=1}^{\infty}\Big\lfloor \dfrac{n}{p^i} \Big\rfloor}=\Big\lfloor \dfrac{n}{p} \Big\rfloor+\Big\lfloor \dfrac{n}{p^2} \Big\rfloor+\Big\lfloor \dfrac{n}{p^3} \Big\rfloor+\cdots$

ただし， $\lfloor x \rfloor$ は $x$ を超えない最大の整数を表す。

→ ルジャンドルの定理（階乗が持つ素因数のべき数）

無限降下法の整数問題への応用例

このページでは，無限降下法について解説します。
無限降下法とは何か？
無限降下法の簡単な応用例：3\sqrt{3}3​ が無理数であることの証明
無限降下法の難しい応用例：フェルマーの最終定理の n=4n=4n=4
→ 無限降下法の整数問題への応用例

ピタゴラス数の求め方とその証明

ピタゴラス数とは，直角三角形の3辺の長さとなるような3つの整数の組のことです。例えば，3辺の長さが $(3,4,5)$ であるような直角三角形が存在するので， $(3,4,5)$ はピタゴラス数です。

→ ピタゴラス数の求め方とその証明

オイラーのファイ関数のイメージ

オイラーのファイ関数

自然数 $n$ に対して， $1$ から $n$ までの自然数の中で $n$ と互いに素なものの数 $\phi(n)$ は， $\phi(n) = n \prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)$ ただし， $p_i$ は $n$ の素因数。

オイラーの $\phi$ 関数（トーシェント関数）についての話です。

→ オイラーのファイ関数のイメージ

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

ユークリッドの互除法（ごじょほう）とは，大きな数字たちの最大公約数を素早く計算する方法です。
この記事では， ユークリッドの互除法のやり方 や ユークリッドの互除法の不定方程式への応用方法 などを解説します。
→ ユークリッドの互除法の証明と不定方程式

一次不定方程式ax+by=cの整数解

不定方程式とは， $3x+5y=2$ のように，方程式の数よりも未知変数の数が多いような方程式のことです。

この記事では， $ax+by=c$ という不定方程式の整数解について，重要な定理の証明と，実際に不定方程式の一般解を求める方法を説明します。

→ 一次不定方程式ax+by=cの整数解

素数が無限にあることの4通りの証明

素数は無限に存在する。

→ 素数が無限にあることの4通りの証明

フェルマーの小定理の証明と例題

フェルマーの小定理

$p$ が素数， $a$ が任意の自然数のとき

$a^{p}\equiv a \pmod{p}$

特に $p$ が素数で， $a$ が $p$ と互いに素な自然数のとき

$a^{p-1}\equiv 1\pmod{p}$

→ フェルマーの小定理の証明と例題

合同式の意味とよく使う６つの性質

合同式について，合同式の意味，6つの性質，合同式が何の役に立つのか，などを整理しました。

→ 合同式の意味とよく使う６つの性質

平方剰余と基本的な問題

平方数に関する重要な性質

1：平方数を3で割った余りは必ず0か1。余りが2になることはない。

2：平方数を4で割った余りは必ず0か1。余りが2か3になることはない。

→ 平方剰余と基本的な問題

因数分解公式（ソフィージェルマンの恒等式）

ソフィー・ジェルマン(Sophie Germain)の恒等式

$a^4+4b^4=(a^2+2ab+2b^2)(a^2-2ab+2b^2)$

一見因数分解不可能な式も因数分解できるので，整数問題で威力を発揮します。

→ 因数分解公式（ソフィージェルマンの恒等式）

フェルマー数とその性質

非負の整数 $n$ を用いて $F_n=2^{2^n}+1$ と表される整数をフェルマー数と呼ぶ

フェルマー数には様々な性質があります。このページでは特に重要な性質を3つ紹介します。

→ フェルマー数とその性質

ウィルソンの定理とその２通りの証明

ウィルソン (Wilson) の定理

$2$ 以上の整数 $p$ について， $p$ が素数 $\iff (p-1)!\equiv -1 \pmod{p}$

→ ウィルソンの定理とその２通りの証明

クロネッカーの稠密定理とその証明

クロネッカーの稠密定理

任意の無理数 $x$ と $0\leq a < b \leq 1$ を満たす任意の実数 $a, b$ に対して $a \leq \{nx\} \leq b$ を満たす自然数 $n$ が存在する。

$\{X\}$ は $X$ の小数部分という意味です。

→ クロネッカーの稠密定理とその証明

素因数分解の難しさと素数判定

素数について，理系なら知っておくべき知識について整理しました。

→ 素因数分解の難しさと素数判定

整数論のテクニック：平方数でないことの証明

平方数でないことを証明するためには以下の2つの方法が有効な場合が多い。

1：平方剰余を考える

2：両側から1違いの平方数で挟む

→ 整数論のテクニック：平方数でないことの証明

ペル方程式に関する基本的な性質まとめ

整数 $x$ と $y$ に関する不定方程式： $x^2-dy^2=1$ をペル方程式と言う

ペル方程式について入試レベルで知っておくと便利な知識を整理しました。

→ ペル方程式に関する基本的な性質まとめ

中国剰余定理の証明と例題（二元の場合）

中国剰余定理 (二元の場合)

$n_1$ と $n_2$ が互いに素なとき，

$x\equiv a_1 \pmod{n_1},$

$x\equiv a_2 \pmod{n_2}$

を満たす $x$ が $0$ 以上 $n_1n_2$ 未満の範囲に唯1つ存在する。

連立合同式，中国剰余定理の本質的な部分を理解するためにこのページでは二元の場合で $n_1, n_2$ が互いに素な場合のみを考えます。より一般の場合は→中国剰余定理と法が互いに素でない場合への拡張

→ 中国剰余定理の証明と例題（二元の場合）

中国剰余定理と法が互いに素でない場合への拡張

中国剰余定理 (一般の場合)

$n_i\: (i=1,2,\cdots, k)$ たちが互いに素なとき， $k$ 本の連立合同式

$x\equiv a_i \pmod{n_i}$

を満たす $x$ が $0\leq x <n_1n_2\cdots n_k$ の範囲にただ1つ存在する。

→ 中国剰余定理と法が互いに素でない場合への拡張

原始根の定義と具体例（高校生向け）

原始根

（ $3$ 以上の）素数 $p$ と $1$ 以上 $p$ 未満の整数 $r$ が以下の性質を満たすとき $r$ を法 $p$ に対する原始根と呼ぶ。

「 $r,r^2,\cdots,r^{p-2}$ のいずれもが $p$ で割って余り $1$ でない」

（また， $r=1$ は $p=2$ に対する原始根である，とする。）

→ 原始根の定義と具体例（高校生向け）

ルジャンドル記号とオイラーの規準

$n^2\equiv a\pmod{p}$ となる整数 $n$ が存在するとき $a$ を $p$ の平方剰余と言います。平方剰余の基本的な話題は平方剰余と基本的な問題を参照して下さい。このページでは平方剰余に関するより発展的な話題を扱います。

→ ルジャンドル記号とオイラーの規準

フェルマーの二平方和定理

$2$ つの整数 $x,y$ を用いて $n=x^2+y^2$ と表される

$\Leftrightarrow n$ を素因数分解したときの $4k+3$ 型の素数の指数が全て偶数

高々2つの整数の二乗和で表される整数はどんなものか？という疑問に答える非常に有名な定理です。

→ フェルマーの二平方和定理

完全数の一覧と性質

完全数 とは「約数の総和が自分の2倍になる」ような正の整数のことです。

→ 完全数の一覧と性質

数オリのテクニック〜Vieta jumping〜

Vieta jumping

ある文字について二次式であるような不定方程式を，解と係数の関係を用いて解くテクニック

数学オリンピックの不定方程式の中でも難し目の問題に使えるテクニックです。

→ 数オリのテクニック〜Vieta jumping〜

約数の個数の公式と平方数の性質

約数の個数を求める公式

約数の個数は「素因数分解して」「それぞれの指数に1を足して」「全部かけあわせる」ことで計算することができます。

約数の個数の公式について，計算例や証明を説明します。また，この公式から導ける平方数に関する重要な定理を解説します。

→ 約数の個数の公式と平方数の性質

位数の性質と原始根の応用

$\mathrm{mod}\:p$ における $a$ の位数を $n$ とする。

$a^m\equiv 1\:\mathrm{mod}\:p$ を満たすなら $m$ は $n$ の倍数である。

位数や原始根の話題は高校範囲を逸脱しますが，整数論の様々な定理の証明に役立ちます。上記の性質は特によく使うものです。

→ 位数の性質と原始根の応用

ガウス記号の定義と３つの性質

ガウス記号

実数 $x$ に対して， $n\leq x <n+1$ なる整数 $n$ がただ一つ存在するので，その $n$ を $\lfloor x\rfloor$ と書く。

例： $\lfloor 2.1\rfloor=2$ ， $\lfloor 3\rfloor=3$ ， $\lfloor -2.3\rfloor=-3$

ガウス記号，フロアー関数，床関数，整数部分，など様々な呼び方があります。また， $\lfloor x\rfloor$ ではなく $[x]$ と書くこともあります（むしろ大学入試では後者の記号を用いることが多い）。

→ ガウス記号の定義と３つの性質

素数の逆数和が発散することの証明

素数の逆数和 $\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{1}{7}+\cdots$ は発散する。

非常に美しい結果です。一見難しそうですが，初等的に（高校数学の範囲で）示せます。

→ 素数の逆数和が発散することの証明

整数論の美しい定理７つ

整数論（数論）の美しい7つの定理を紹介します。素数にまつわる定理が多いです。いずれも証明は難しいので定理の鑑賞にとどめておきます。

→ 整数論の美しい定理７つ

数オリの整数論（難問）に対するテクニック

数学オリンピックの整数問題の中でも難問〜超難問レベルに対してときどき使う，有名なテクニックを解説します。
ppp
 進付値，オーダーの話，Lifting The Exponent Lemma，LTEの補題，などと言われているものです。
JMO本選以降の対策にどうぞ。
→ 数オリの整数論（難問）に対するテクニック

倍数の判定法（２から１２）とその証明一覧

覚えるべき倍数の判定法一覧とその証明です。特に $3$ と $11$ が素因数分解でも活躍するので重要です。

→ 倍数の判定法（２から１２）とその証明一覧

約数の総和を求める二つの公式と証明

正の整数の約数の総和を表す公式を二つ紹介します。一つ目は入試でも頻出の必須公式です。
二つ目はコサインとか出てくる観賞用の公式です。玄人向け。
→ 約数の総和を求める二つの公式と証明

素数の間隔に最大値がないことの３通りの証明

いくらでも長い素数砂漠が存在する。

→ 素数の間隔に最大値がないことの３通りの証明

素因数分解の一意性とその証明について

素因数分解の一意性

全ての正の整数は素数の積として（順番を除いて）一意に表せる。

算術の基本定理とも呼ばれる重要な定理です。一見当たり前ですが実は当たり前ではありません。きちんと証明しようとするとけっこう大変です。

→ 素因数分解の一意性とその証明について

フロベニウスの硬貨交換問題

$A$ と $B$ が互いに素なとき， $A$ 円の硬貨と $B$ 円の硬貨を使って支払えない金額の最大値は $(AB-A-B)=\{(A-1)(B-1)-1\}$ 円になる。

フロベニウスの硬貨交換問題（硬貨が二種類の場合）についての美しい結果とその証明の解説。

→ フロベニウスの硬貨交換問題

リーマン予想の意味，素数分布との関係

リーマン予想

ゼータ関数の非自明な零点の実部は $\dfrac{1}{2}$ である。

自明な零点（ゼロ点）とは？リーマン予想に関して現在分かっている基本的なこと，素数との関係，暗号との関係について。

→ リーマン予想の意味，素数分布との関係

エラトステネスのふるいとその計算量

エラトステネスのふるい： $n$ 以下の素数を全て見つけ出す高速な方法。

エラトステネスの篩（ふるい）の概要と，愚直に計算するよりも速いこと（計算量が $O(n\log\log n)$ であること）を解説します。

→ エラトステネスのふるいとその計算量

三角数とは，三角数定理，平方数との関係

1．三角数とは？
2．三角数定理！
3．ペル方程式を使って三角数かつ平方数であるものを明示的に表す公式を導出（←感動！）。
→ 三角数とは，三角数定理，平方数との関係

平方剰余の相互法則の意味と応用

平方剰余の相互法則（など）を用いることで，与えられた素数 $p$ と $p$ 未満の非負整数 $a$ に対して $p$ で割って $a$ 余るような平方数が存在するか否かを素早く判定することができる。

平方剰余の相互法則の意味と応用について解説します。

→ 平方剰余の相互法則の意味と応用

レイリーの定理とその自然な証明

レイリー（Rayleigh）の定理

$\dfrac{1}{r}+\dfrac{1}{s}=1$ を満たす正の無理数 $r,s$ に対して以下が成立する。

全ての正の整数は二つの数列

$\lfloor mr\rfloor \:(m=1,2,3\cdots)$

$\lfloor ns\rfloor \:(n=1,2,3\cdots)$

のいずれかに必ず一回だけ登場する。

→ レイリーの定理とその自然な証明

最大公約数と最小公倍数の積の性質の２通りの証明

最大公約数と最小公倍数の関係

正の整数 $a,b$ に対して，それらの最大公約数を $g$ ，最小公倍数を $l$ とおくと $ab=gl$

（最大公約数と最小公倍数の積がもとの二つの数の積に等しい）

→ 最大公約数と最小公倍数の積の性質の２通りの証明

素数一覧（４桁以下，番号つき）

4桁以下（1万以下）の素数を一覧にしました。番号つきです。

→ 素数一覧（４桁以下，番号つき）

フェルマーの最終定理

$n$ を3以上の整数とするとき， $x^n+y^n=z^n$ を満たす正の整数 $x,y,z$ の組は存在しない。

この記事では，フェルマーの最終定理について，高校数学の範囲で簡単に紹介します。

→ フェルマーの最終定理

二進法と十進法の変換方法と計算例

二進法と十進法について。二進数と十進数を互いに変換する方法と計算例，小数を含む場合についても解説します。

→ 二進法と十進法の変換方法と計算例

格子点の個数を数える問題の5通りの解法

格子点：座標平面（or 座標空間）において，各成分が全て整数であるような点

→ 格子点の個数を数える問題の5通りの解法

互いに素の意味と関連する三つの定理

互いに素とは，2つの整数の最大公約数が1であることを言う。例えば， $3$ と $5$ の最大公約数は $1$ なので， $3$ と $5$ は互いに素。

「互いに素」の意味と，関連する定理を解説します。定理1，2は基本的な内容ですが，定理3は数学マニア向け（美しい！）です。

→ 互いに素の意味と関連する三つの定理

素因数分解の高速なアルゴリズム（ロー法）

ポラードのロー法という素因数分解の高速なアルゴリズムを解説します。

→ 素因数分解の高速なアルゴリズム（ロー法）

双子素数にまつわるいくつかの話題

$p$ ， $p+2$ がいずれも素数であるときそれらを双子素数と言う。

$(3,5)$ ， $(5,7)$ ， $(11,13)$ などが双子素数です。

→ 双子素数にまつわるいくつかの話題

自然数とは（0を含むこともあるよ）

前半では自然数の二通りの意味を説明します。後半では自然数の公理について軽く触れます。

→ 自然数とは（0を含むこともあるよ）

ナルシシスト数について

ナルシシスト数（Narcissistic Number）の意味，有限個しかないことの証明などを解説します。

→ ナルシシスト数について

メビウスの反転公式の証明と応用

前半は準備（メビウス関数の定義，簡単な性質）です。後半はメビウスの反転公式という美しい定理とその応用例を解説します。

→ メビウスの反転公式の証明と応用

正多角形の作図可能性の条件

正 $n$ 角形が定規とコンパスで作図可能 $\iff$

$n=2^Np_1\cdots p_k$ となる $0$ 以上の整数 $N$ と互いに異なるフェルマー素数 $p_1,\cdots,p_k$ が存在する。

→ 正多角形の作図可能性の条件

ゴールドバッハ予想と関連する命題

命題1（ゴールドバッハ予想）

$2$ より大きな偶数は2つの素数の和で表すことができる。

命題1が真なのか偽なのかは分かっていません。整数論における有名な未解決問題です。

→ ゴールドバッハ予想と関連する命題

Lucasの定理とその証明

Lucasの定理

任意の素数 $p$ と非負整数 $m,n$ に対して，

$\displaystyle{}_{m}\mathrm{C}_{n}\equiv\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}\pmod{p}$

ただし， $m_km_{k-1}\cdots m_1m_0$ は $m$ の $p$ 進数表示， $n_kn_{k-1}\cdots n_1n_0$ は $n$ の $p$ 進数表示。

なお， $m\geq n$ のときは ${}_{m}\mathrm{C}_{n}=\dfrac{m!}{n!(m-n)!}$ ですが，このページではさらに $m < n$ のときは ${}_{m}\mathrm{C}_{n}=0$ とします。

→ Lucasの定理とその証明

カプレカ数（特に3桁の場合）について

3桁のカプレカ数は $495$ のみである。

4桁のカプレカ数は $6174$ のみである。

カプレカ数の意味，および関連する性質について解説します。

→ カプレカ数（特に3桁の場合）について

クンマーの定理とその証明

クンマーの定理（Kummer's theorem）

${}_m\mathrm{C}_n$ が素数 $p$ で割り切れる回数は $m-n$ と $n$ を $p$ 進数表示して足し算をしたときの繰り上がりの回数と等しい。

整数の美しい定理です！

→ クンマーの定理とその証明

リウヴィル数の具体例と性質

以下を満たす実数 $r$ をリウヴィル数（リュービル数）と言う：

任意の正の整数 $n$ に対して，ある正の整数 $p,q\:(q\geq 2)$ が存在して

$0< \left|r-\dfrac{p}{q}\right| < \dfrac{1}{q^n}$ を満たす。

定義がやや複雑ですが「 $r$ が有理数 $\dfrac{p}{q}$ でかなり精度よく近似できる」というイメージです。

→ リウヴィル数の具体例と性質

円分多項式とその性質

$\zeta_n=e^{\frac{2\pi i}{n}}=\cos \dfrac{2\pi}{n}+i\sin\dfrac{2\pi}{n}$ （ $n$ 乗して $1$ になる数のうちの一つ）とおく。多項式

$F_n(x)=\displaystyle\prod_{k\in A_n} (x-\zeta_n^k)$

を円分多項式（円周等分多項式）と言う。

ただし， $A_n$ は $1$ 以上 $n$ 以下の整数で， $n$ と互いに素なもの全体の集合です。

→ 円分多項式とその性質

ガウス整数とその応用

整数 $a,b$ を用いて $a+bi$ と表される複素数をガウス整数（複素整数）と呼ぶ。

→ ガウス整数とその応用

レプユニット数

全ての桁が $1$ である整数をレプユニット数と言う。

$1$ ， $11$ ， $111$ などです。Rep（繰り返し）Unit（ $1$ ）という意味です。

→ レプユニット数

フォードの円

中心が $\left(\dfrac{q}{p},\dfrac{1}{2p^2}\right)$ で直径が $\dfrac{1}{p^2}$ である円を並べると美しい。

フォードの円と呼ばれる美しい円たちについて紹介します。

→ フォードの円

数列における余りの周期性（特にフィボナッチ数列）

数列における余りの周期性について，以下の2つの話題を紹介します。
漸化式で表される数列における，割り算の余りの周期性（受験レベル）
特に，フィボナッチ数列における周期について（難しい）
→ 数列における余りの周期性（特にフィボナッチ数列）

原始ピタゴラス数の木

すべての原始ピタゴラス数は， $\begin{pmatrix}3\\4\\5\end{pmatrix}$ に対して，3つの行列 $A,B,C$ のどれかをかける操作を何度か繰り返すことで作れる。ただし，

$A=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix}$ ，

$B=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix}$ ， $C=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}$

ピタゴラス数に関する非常におもしろい定理です。この定理の主張と証明を詳しく解説します。

→ 原始ピタゴラス数の木

n進法・n進数の解説と問題例

n進法とは，n種類の記号を用いて数を表現する方法。また，n進法で表された数をn進数という。

n進法は「n進位取り記数法」とも呼ばれます。

→ n進法・n進数の解説と問題例

エジプト分数（単位分数の和）に関する4つの話題

エジプト分数

$\dfrac{1}{2}$ のように，分子が $1$ である分数を単位分数と言います。

$\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}$ のように，分母が異なる単位分数の和のことをエジプト分数（エジプト式分数）と言います。

エジプト分数に関連する4つの話題を紹介します。

→ エジプト分数（単位分数の和）に関する4つの話題

チャンパーノウン定数

チャンパーノウン定数（Champernowne Constant）

$0.$ のあとに正の整数を $1$ から小さい順に並べ続けた数

$0.12345678910111213\cdots$

をチャンパーノウン定数と言う。

定義も名前も印象的な定数です！

→ チャンパーノウン定数

友愛数の意味と友愛数を生み出す公式

友愛数

（自分自身を除いた）約数の総和＝相手となる正の整数のペアのことを友愛数と呼ぶ。

つまり， $m$ の約数の総和を $S(m)$ と書くとき，友愛数とは

$S(m)-m=n$ かつ $S(n)-n=m$ が成り立つペア $(m,n)$ のことです。
$S(m)=S(n)=m+n$ が成り立つペア，とも言えます。

→ 友愛数の意味と友愛数を生み出す公式

最大公約数の4通りの求め方

この記事では最大公約数を求める方法を4通り紹介します。
手っ取り早く計算する方法
はぜひマスターしておきましょう。他にも，
約数をすべて書き出す方法
重要な性質を使う方法
大きい数の場合に高速に計算する方法
も解説します。
→ 最大公約数の4通りの求め方

リュカ数の意味とおもしろい性質

リュカ数（Lucas Number）

$L_0=2,L_1=1,\\L_n=L_{n-1}+L_{n-2}\:(n\geq 2)$

で定まる数列 $\{L_n\}$ に現れる数をリュカ数と呼ぶ。

リュカ数について，3つの話題を紹介します。「一般項」と「フィボナッチ数との加法定理」は大学入試レベルです。最後の「三角関数表示」では複素三角関数が登場します。

→ リュカ数の意味とおもしろい性質

この記事の編集者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！