分野: 整数問題

整数論の有名な公式：
連続する $n$ 個の整数の積は $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辺の長さとなるような3つの整数の組のことです。例えば，3辺の長さが $(3,4,5)$ であるような直角三角形が存在するので，$(3,4,5)$ はピタゴラス数です。

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

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

素数は無限に存在する。

フェルマーの小定理：
$p$ が素数，$a$ が任意の自然数のとき
$a^{p}\equiv a \:\mathrm{mod}\:p$
特に $p$ が素数で，$a$ が $p$ と互いに素な自然数のとき
$a^{p-1}\equiv 1\:\mathrm{mod}\:p$

平方数に関する重要な性質：
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$ と表される整数をフェルマー数と呼ぶ

ウィルソン(Wilson)の定理：
$2$ 以上の整数 $p$ について，
$p$ が素数 $\iff (p-1)!\equiv -1 \:\mathrm{mod}\:p$

クロネッカーの稠密定理：
任意の無理数 $x$ と $0\leq a <b\leq 1$ を満たす任意の実数 $a, b$ に対して $a \leq \{nx\} \leq b$ を満たす自然数 $n$ が存在する。

平方数でないことを証明するためには以下の2つの方法が有効な場合が多い。
1：平方剰余を考える
2：両側から1違いの平方数で挟む

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

中国剰余定理(二元の場合)：
$n_1$ と $n_2$ が互いに素なとき，
$x\equiv a_1 \:\mathrm{mod}\: n_1,$
$x\equiv a_2 \:\mathrm{mod}\: n_2$
を満たす $x$ が $0$ 以上 $n_1n_2$ 未満の範囲に唯1つ存在する。

中国剰余定理(一般の場合)：
$n_i\: (i=1,2,\cdots, k)$ たちが互いに素なとき，$k$ 本の連立合同式
$x\equiv a_i \:\mathrm{mod}\: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$ に対する原始根である，とする。）

定理：$2$ つの整数 $x,y$ を用いて $n=x^2+y^2$ と表される
⇔ $n$ を素因数分解したときの $4k+3$ 型の素数の指数が全て偶数

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

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$

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

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

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

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

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

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

平方剰余の相互法則（など）を用いることで，与えられた素数 $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$
（最大公約数と最小公倍数の積がもとの二つの数の積に等しい）

フェルマーの最終定理：
$n$ を3以上の整数とするとき，$x^n+y^n=z^n$ を満たす正の整数 $x,y,z$ の組は存在しない。

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

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

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