分野: 整数問題


ルジャンドルの定理
$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$ を超えない最大の整数を表す。


無限降下法(後ろ向き帰納法)と呼ばれる証明方法を紹介します。無限降下法の簡単な応用例として $\sqrt{3}$ が無理数であることの証明を紹介し,発展的な応用例としてフェルマーの最終定理の $n=4$ の場合の証明を行います。


ピタゴラス数を全て作り出す公式:
$a^2+b^2=c^2$ を満たす自然数の組$(a,b,c)$ をピタゴラス数と呼ぶ。
ピタゴラス数の中で $a,b,c$ の最大公約数が $1$ のものは,ある正の整数 $m,n$ を用いて $a=m^2-n^2,b=2mn,c=m^2+n^2$
(または $b=m^2-n^2,a=2mn,c=m^2+n^2$)
という形で表せる。

この公式を知っているとピタゴラス数にまつわる入試問題の見通しがよくなります。


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

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


$x,y$ に関する二元一次不定方程式 $ax+by=c$ が整数解を持つ
$\iff$ $c$ はgcd$ (a,b)$ の倍数
特に, $ax+by=1$ が整数解を持つ
$\iff$ $a$ と $b$ は互いに素

gcd$ (a,b)$ は $a$ と $b$ の最大公約数を表します。


平方数に関する重要な性質:
1:平方数を3で割った余りは必ず0か1。余りが2になることはない。
2:平方数を4で割った余りは必ず0か1。余りが2か3になることはない。


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

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


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

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


原始根の定義:
($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つの自然数の二乗和で表される自然数はどんなものか?という疑問に答える非常に有名な定理です。


約数の個数の公式:正の整数 $n$ が,$n=p_1^{a_1} p
_2^{a_2}\cdots p_k^{a_k}$ と素因数分解できるとき,$n$ の約数の個数は$(a_1+1)(a_2+1)\cdots (a_k+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 x\rfloor$ ではなく $[x]$ と書くこともあります(むしろ大学入試では後者の記号を用いることが多い)。


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


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

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


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

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


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

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


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

エラトステネスの篩(ふるい)の概要と,愚直に計算するよりも速いこと(計算量が $O(n\log\log 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)$
のいずれかに必ず一回だけ登場する。


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

言わずと知れた大定理です。


二つの整数 $m,n$ の最大公約数が $1$ のとき,$m$ と $n$ は互いに素(たがいにそ)であると言う。

「互いに素」に関連する定理を解説。定理1,2は基本的な内容ですが,定理3は玄人向け(美しい!)です。