整数の応用を軽く学ぼう

整数問題解法シリーズ（コンパクト版）

（※）パソコン、タブレットなどの大きめの端末での閲覧を推奨します。
本稿は、整数問題の代表的な考え方をコンパクトに整理するとともに、

整数を学びたいけれど、何を学べばよいのか分からない
という方へ、今後調べていくためのキーワードをまとめた記事です。
一つ一つの内容を完全に解説する百科事典ではありませんが、整数問題を学ぶうえでの確かな土台と地図になることを目指します。

---

目次

1. ご挨拶と本稿の説明
2. 整数問題の本質――離散性と絞り込み
3. 解き始める前に確認したいこと
4. 整数問題の三大解法
5. 三大解法を組み合わせる
6. テーマ別に見る整数問題
7. さらに学びたい人へのキーワード
8. 数そのものに関する話題
9. 整数と他分野との接続
10. 練習問題・演習問題
11. 最後に

---

ご挨拶と本稿の説明

ご挨拶

本稿をご覧くださった皆さま、ごきげんよう。
フラワと申します。
本稿は「整数問題解法シリーズ」のコンパクト版です。
詳しい理論を一からすべて証明する記事というより、整数問題の全体像を眺め、

• どのような考え方があるのか
• どのような場面で使うのか
• 次に何を調べればよいのか
  を知るための記事となっています。
  コンパクト版ですから、これだけで整数問題のすべてが完璧になるとは言いません。むしろ、整数の世界には本稿だけでは語り切れないものがまだまだあります。
  ただし、整数問題を本格的に学ぶための確かな土台にはなるはずです。
  ぜひ一度最後まで読み、演習を積んだ後にもう一度戻ってきてください。初めて読んだときとは違った景色が見えると思います。

対象者と本稿の位置づけ

本稿は、もともと私の友人Aがその友人Bに整数を教えるにあたり、学習の指標となるものが欲しいという話から作成したものです。
そのため、因数分解や基本的な方程式などは一度学んだことがある方を主な対象としています。
一方で、整数問題にまだ自信のない方も、

本稿に出てくる言葉や考え方を少しずつ理解できるようになる
ことを一つの目標にしてもらえれば十分です。

本稿での約束

• 本稿では、特に断らない限り自然数は正の整数を表します。
• 素数とは、$1$より大きい正の整数で、正の約数が$1$とその数自身しかないものをいいます。
• 「平方数」「立方数」「$k$乗数」は、特に断らない限り整数の平方、立方、$k$乗として表される整数を指します。
• 発展的な項目には、検索や今後の学習の入口として名前だけを紹介するものもあります。
  では、早速内容に参りましょうか。

---

整数問題の本質――離散性と絞り込み

なぜ、整数問題はほかの分野と区別され、特別な考え方が必要になるのでしょうか。
その大きな理由は、整数のもつ離散性にあります。
実数の世界では、$1$と$2$の間にも無数の数が存在します。しかし整数の世界では、$1$と$2$の間に整数は存在しません。
整数は数直線上に飛び飛びに並んでおり、異なる二つの整数の差の絶対値は必ず$1$以上です。
この「隙間」が整数問題における最大の武器になります。

例えば、実数$x$について
$$1\leq x\leq6$$
と分かっても、$x$は一つには定まりません。それどころか候補は無数にあります。
しかし$x$が整数なら、候補は
$$1,2,3,4,5,6$$
の六つしかありません。
このように、無限に見える候補を有限個へ落とすことを、本稿では絞り込みと呼びます。

整数問題に現れるさまざまな技法も、その働きに注目すれば、結局はこの「絞り込み」を行っています。

---

解き始める前に確認したいこと

いきなり技巧的な変形を探す前に、まず現在の条件を整理しましょう。

1．文字の範囲と定義

• 整数か、自然数か、正の整数か
• $0$を許すか
• 分母が$0$になる場合はないか
• 平方根の中身は$0$以上か
• 指数や添字に範囲があるか
  分母を払ったり式を割ったりする前には、割るものが$0$でないことを確認する必要があります。

2．正負・偶奇・大小

• 両辺の符号は一致するか
• 偶数・奇数のどちらでなければならないか
• 一方が他方より大きいことは分かるか
• 絶対値を付ければ評価しやすくならないか
  素数が現れたら、偶数の素数$2$を最初に分けるだけで一気に進むこともあります。

3．対称性

条件が$x,y,z$について対称なら、一般性を失うことなく
$$x\geq y\geq z$$
などとおける場合があります。
ただし、順序を付けて調べた後は、順列を戻す必要があるか、同じ値があるため重複が生じないかを確認しましょう。

4．最大公約数

複数の整数が現れたら、最大公約数を取り出すことで本質的な部分が見える場合があります。
例えば
$$x=da,\qquad y=db,\qquad \gcd(a,b)=1$$
とおけば、共通部分$d$と互いに素な部分$a,b$を分離できます。

5．小さい値の実験

実験は証明ではありませんが、

• どのような答えになりそうか
• 何の倍数になりそうか
• どの法で規則が見えそうか
• どの因数分解が役立ちそうか
  を予想するためには非常に有効です。
  整数では試行錯誤が超超超重要です。

---

整数問題の三大解法

整数問題には、無限降下法、鳩の巣原理、素因数の指数に注目する方法など、さまざまな名前の付いた手法があります。
しかし、それらが整数をどのように絞り込んでいるかに注目すれば、すべての手法は次の三大解法のいずれか、または複数の組合せに含まれます。

実際の入試問題では、三つがきれいに一つずつ出てくるわけではありません。
因数分解した後に不等式で因数の大小を比べ、さらに合同式で候補を消す、といったようにごちゃまぜになります。
まずは一つずつ見ていきましょう。

---

1．因数分解

因数分解はなぜ効くのか

整数問題における因数分解の目的は、単に式をきれいにすることではありません。

$N$が$0$でない一定の整数なら、その約数は有限個です。したがって、左辺の二つの因数としてあり得る組も有限個になります。
この背景にあるのが、素因数分解の一意性です。
正の整数$N\geq2$は、異なる素数$p_1,p_2,\ldots,p_r$と正の整数$e_1,e_2,\ldots,e_r$を用いて
$$N=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$
と表せ、この表し方は素数の並べる順序を除いて一意です。
したがって$N$の正の約数は、各$p_i$の指数を$0$以上$e_i$以下から選ぶことで尽くされます。
特に、$N$の正の約数の個数は
$$(e_1+1)(e_2+1)\cdots(e_r+1)$$
です。
$N$が素数$p$なら、整数の範囲では因数は
$$\pm1,\ \pm p$$
に限られます。
$N=p^m$なら、正の約数は
$$1,p,p^2,\ldots,p^m$$
に限られます。
なお、右辺が$0$なら約数を列挙するのではなく、積が$0$であることから、少なくとも一方の因数が$0$であると場合分けします。

因数分解後の基本手順

1. 積が一定値になる形を作る。
2. 正負を含めて約数の組を考える。
3. それぞれの組から元の未知数を求める。
4. 自然数条件、大小関係、互いに素などの条件を確認する。
5. 得られた候補を元の式へ代入し、十分性を確認する。
   最後の確認を忘れると、変形の途中で混入した不適な候補まで答えにしてしまうことがあります。

二変数一次式――変数を片付ける意識

これは、二変数一次の不定方程式で非常によく現れる変形です。

私なりの見方は、

変数は因数の先頭に置き、変数同士の積に負号が付かないように調整する。あとは欲しい積になるように定数を補う。
というものです。
因数分解では「こうなってくれたらうれしいなあ」を大事にしてください。

一方の文字について解く方法

同じ式でも、必ず因数分解だけを使う必要はありません。
先ほどの式は
$$x(y-2)=2y$$
とも書けます。
$y=2$は元の式を満たさないため、$y-2$で割って
$$x=\frac{2y}{y-2}=2+\frac{4}{y-2}$$
とできます。
$x$が整数であるためには、$y-2$が$4$の約数でなければなりません。

二次式を含む整数方程式

$$ax^2+hxy+by^2+cx+dy=e$$
のような二次式を含む方程式では、主に次の三方向を考えます。

方向1　一次式どうしの積を作る

二次の部分
$$ax^2+hxy+by^2$$
が整数係数の範囲で因数分解できる場合、全体も
$$\text{（}x,y\text{の一次式）}\times\text{（}x,y\text{の一次式）}=\text{定数}$$
となる可能性があります。
ただし、二次の部分が常に因数分解できるわけではありません。

方向2　平方完成する

一方または両方の文字について平方完成し、
$$A^2+B^2=N$$
や
$$A^2-B^2=N$$
の形を作ります。
和の場合は各平方が$0$以上であることから範囲を絞れます。差の場合は
$$A^2-B^2=(A-B)(A+B)$$
とさらに因数分解できることがあります。

方向3　一方の文字の二次方程式と見る

例えば$x$について
$$A(y)x^2+B(y)x+C(y)=0$$
と見ます。
$A(y)=0$となる場合は別に調べます。$A(y)\neq0$で整数解$x$をもつなら、判別式は
$$D=B(y)^2-4A(y)C(y)=(2A(y)x+B(y))^2$$
となるため、$D$は$0$以上の平方数でなければなりません。
ただし、$D$が平方数であることは普通は必要条件にすぎません。解の公式の分母で割り切れるか、得られた値が元の条件を満たすかまで確認しましょう。

倍数の証明に因数分解を使う

連続する整数がすべて正で、最初の整数を$m$とすると、
$$\frac{m(m+1)\cdots(m+k-1)}{k!}={}_{m+k-1}C_k$$
は整数です。
途中に$0$を含む場合は積が$0$なので明らかです。すべて負の場合も、符号を除けば連続する正の整数の積に直せます。

ここでは$n(n+1)(n+2)$よりも$(n-1)n(n+1)$の方が、
$$(n-1)(n+1)=n^2-1$$
と計算しやすく、元の$n^3$へ合わせやすくなっています。
まさに、連続する整数の積を無理やり作って帳尻合わせです。

因数分解は一通りとは限らない

例えば
$$n^3+1=p^m$$
なら、左辺を
$$n^3+1=(n+1)(n^2-n+1)$$
と因数分解する方向があります。
一方で
$$p^m-1=n^3$$
と移項し、指数$m$の性質に応じて$p^m-1$を因数分解する方向もあります。
どちらが効くかは問題によります。一つの形に固執せず、複数の方向を試しましょう。

---

2．不等式による範囲の絞り込み

整数問題における不等式の主な目的は、次の三つです。

1. 文字の候補を有限個にする。
2. 二つの整数の差を$1$未満にし、一致を強制する。
3. 隣り合う平方数や累乗数の間に挟み、特殊な形ではないことを示す。

簡単な不等式を自分から作る

問題文に不等式がなくても、定義や正負から自分で作れます。
例えば、床関数について
$$\lfloor x\rfloor\leq x<\lfloor x\rfloor+1$$
ですから、
$$x-1<\lfloor x\rfloor\leq x$$
が得られます。
また、$a,b,c$について条件が対称なら、一般性を失わないように
$$a\geq b\geq c$$
とおき、最大のもの・最小のものに注目できます。

和や積を一項ずつ見る

各項が$0$以上なら、和の一部を捨てることで下から評価できます。
また、正の整数$a,b$がともに$2$以上なら
$$ab-a-b=(a-1)(b-1)-1\geq0$$
より
$$ab\geq a+b$$
です。等号は$a=b=2$のときに限ります。
「和より積の方が大きくなりやすい」という感覚は、条件を確認したうえで使いましょう。

隣り合う特殊な数で挟む

より一般に、ある整数が隣り合う二つの$k$乗数の間にあることを示せれば、その整数は$k$乗数ではありません。

増加の速さを比較する

整数問題では、片方が多項式、もう片方が指数関数や階乗となることがあります。
底$a,r$を$a>1,r>1$の固定された実数、次数$d$を固定された正の整数とすると、十分大きな自然数$n$に対して
$$\log_a n< n^d< r^n< n!< n^n$$
となります。
大切なのは、この並びを条件なしで使うことではなく、

どちらが最終的に速く大きくなるかを予想し、必要な範囲で不等式として証明する
ことです。
証明には、差を取る、比を取って$1$と比較する、数学的帰納法を使う、実数の関数として微分する、といった方法があります。

有名不等式を使う

非負の実数$a,b$についての相加相乗平均の関係
$$\frac{a+b}{2}\geq\sqrt{ab}$$
や、実数$a,b,x,y$についてのコーシー・シュワルツの不等式
$$(a^2+b^2)(x^2+y^2)\geq(ax+by)^2$$
も、整数の範囲を絞るために使われます。
また、絶対値について
$$|a+b|\leq|a|+|b|$$
であることも基本です。
有名不等式は、それを使うこと自体が目的ではありません。等号がいつ成立するかまで確認し、整数条件と組み合わせましょう。

整除関係と不等式を組み合わせる

正の整数$a,b$について、$a$が$b$の約数なら$a\leq b$です。
したがって、式から「非常に大きな数が非常に小さな正の数の約数である」と分かれば、それだけで矛盾になることがあります。
因数分解や最大公約数の議論の後に、不等式が最後の一押しとなることも多いです。

---

3．約数・倍数・余りの利用

ここには、

• 約数・倍数
• 最大公約数・互いに素
• 偶数・奇数
• 余り
• 合同式
• 素因数が現れる回数
  などが含まれます。
  特に合同式は、本当に強力な武器です。

合同式の最小限の確認

整数$a,b$を$m$で割った余りが等しいことを
$$a\equiv b\pmod m$$
と書きます。これは$a-b$が$m$の倍数であることと同じです。
合同式では、両辺を足す、引く、掛ける、同じ正の整数乗をする、といった操作ができます。
一方、通常の等式と同じ感覚で割り算をすることはできません。
例えば
$$ac\equiv bc\pmod m$$
から$c$を消して
$$a\equiv b\pmod m$$
とするには、少なくとも$c$と$m$が互いに素であることなどの確認が必要です。

$\pm$を使って対称性を見る

例えば、任意の整数$n$は
$$n\equiv0,\pm1\pmod3$$
のいずれかです。
これを二乗すると符号が消え、
$$n^2\equiv0,1\pmod3$$
となります。
$0,1,2$と書くより$0,\pm1$と書くことで、二乗したときに同じ剰余になる構造が見えやすくなっています。
もちろん、常に$\pm$で書かなければならないわけではありません。符号の対称性を見せたいときに使いましょう。

平方数を割った余り

法$m\geq3$で平方数を考えると、$1$と$-1$の平方が同じになるため、平方数の剰余が$m$種類すべて現れることはありません。
特に次の表は頻出です。

法$3$と法$4$では平方数の剰余が$0,1$しかないため、まず覚えてしまってもよいでしょう。
立方数については、例えば
$$n^3\equiv0,\pm1\pmod7$$
が成り立ちます。

法を選ぶための指針

合同式では、法を何にするかが重要です。
以下は候補を探すための指針です。どれか一つを機械的に使うのではなく、問題の構造に合わせて選びます。

①　まず法$2$――偶奇を見る

偶数の素数が$2$しかないため、素数問題では特に強力です。
平方数や指数を含む式でも、偶奇だけで候補が半分に減ることがあります。

②　式に現れる数と関係する法を見る

例えば右辺が$7^n$なら、法$7$や法$7^2$などを考える候補があります。
ただし「$7$が見えたから法$7$」で終わらず、法$7$で左右がどのように簡単になるかまで確認します。

③　平方数・立方数・累乗数の剰余が少なくなる法を見る

平方数なら法$3,4,5,8$など、立方数なら法$7$などが候補になります。
指数を含む式では、累乗の剰余が短い周期をもつ法を探します。

④　複数の式があるなら、その個数の周辺の法を疑う

式が$n$個あるとき、法$n$は一つの候補です。
ただし、式が$n$個あるだけで法$n$が使えるわけではありません。
法$n$で見たときに、それらの式がすべての剰余類を覆う、または必ず一つが$0$になることを確認する必要があります。
例えば
$$t-10,\quad t,\quad t+10$$
は法$3$で
$$t-1,\quad t,\quad t+1$$
と合同です。これは連続する三整数と同じ剰余をもち、三つのうちちょうど一つが$3$の倍数になります。

⑤　$0,\pm1$を作れる法を探す

偶数乗なら符号が消え、奇数乗なら符号が残ります。
したがって$0,\pm1$に整理できる法は、平方・立方・指数を含む問題で見通しをよくしてくれます。

⑥　小さい法から実験する

法$2,3,4,5,7,8,9,11$など、小さな法で剰余を書き出してみるのも有効です。
ただし、最終的には「なぜその法が効いたのか」を言葉にできるようにしましょう。

⑦　複数の法を組み合わせる

法$3$だけ、法$4$だけでは候補が残っても、両方を満たす条件を合わせると大きく絞れることがあります。

素数と小さな法

$5$以上の素数$p$は
$$p\equiv\pm1\pmod6$$
を満たします。
ただし逆は成り立ちません。$6k\pm1$の形であることは素数であるための必要条件にすぎません。
また、ある素数候補$N$が法$p$で$0$となったとき、すぐに合成数と結論してはいけません。
$N$が素数なら
$$N=p$$
という例外が残ります。

フェルマーの小定理

指数が非常に大きいときでも、法$p$では指数を小さく整理できることがあります。

---

三大解法を組み合わせる

実戦では、一つの手法だけにこだわりません。

例えば、

因数分解で約数候補を出す

↓

不等式で因数の大小を制限する

↓

合同式で候補を消す

↓

元の式へ代入する
という流れもあります。
逆に、合同式で偶奇を決めてから因数分解が可能になることもあります。
解法名を当てるゲームではなく、今ある候補を次にどう減らすかを考えましょう。

---

テーマ別に見る整数問題

ここからは、整数問題でよく現れる対象ごとに、主なキーワードをまとめます。
すべてを今すぐ使いこなす必要はありません。知らない言葉に出会ったら、今後調べるための入口にしてください。

素数問題

• 因数分解し、積が素数となる条件を考える。
• 偶数の素数$2$を分ける。
• 小さな素数を法として、必ずその素数の倍数になる式を探す。
• 素数自身が変数なら、その変数が小さな法でどの剰余を取るか調べる。
• ある式が素数$p$の倍数なら、その式自体が$p$となる例外を確認する。
• 複数の式がいずれも素数なら、剰余がすべての類を覆う法を探す。

倍数であることの証明

• 合同式で$0$になることを示す。
• 因数分解して、必要な因数を取り出す。
• 連続する整数の積を作る。
• 既に倍数と分かる式の和や差へ変形する。
• 数学的帰納法を使う。
  そして最後は、愛と勇気と気合の$\mathrm{mod}$です。

平方数・立方数・$k$乗数

• $x^2,y^3,z^k$などとおく。
• 素因数分解したときの指数に注目する。
• 平方剰余・立方剰余を調べる。
• 隣り合う平方数・$k$乗数で挟む。
• 和と差の積などへ因数分解する。
• 互いに素な因数の積が$k$乗数となる条件を使う。
  正の整数$N$について、次は同値です。
• $N$は平方数である。
• $N$の素因数分解に現れる指数がすべて偶数である。
• $N$の正の約数の個数が奇数である。

素因数が現れる回数

素数$p$が正の整数$N$の素因数分解にちょうど$m$回現れることを考えます。ただし、$m$は$0$以上の整数です。
$$v_p(N)=m$$
と表します。
これは
$$N=p^m k$$
と書け、$k$が$p$の倍数でないことを意味します。

等式の両辺が等しいなら、両辺に含まれる$p$の個数も一致します。
また
$$p^m\leq N< p^{m+1}$$
なら、$N$に含まれる$p$は高々$m$個です。
階乗に含まれる素数の個数には、後述するルジャンドルの公式が使えます。

最大公約数・互いに素

• ユークリッドの互除法を使う。
• 共通に割り切る素数が存在すると仮定する。
• 二数の整数係数の一次結合を作る。
• 最大公約数を取り出し、互いに素な部分へ分ける。

共通の約数は$a,b$だけでなく、$a,b$の整数係数の一次結合も割り切ります。
よく使う事実として、次があります。

• 連続する二整数は互いに素である。
• 連続する二奇数は互いに素である。
• $gcd(a,b)=1$なら、$gcd(a+b,ab)=1$である。
• 正の整数$a,b$が互いに素で、$ab$が$k$乗数なら、$a,b$はともに$k$乗数である。

分数の整数条件

整数$A,B$について$B\neq0$とします。
$$\frac{A}{B}$$
が整数なら、$B$は$A$の約数です。
また、
$$0<|A|<|B|$$
なら$A/B$は整数ではありません。
分数が整数であると分かっているなら、その値は$0$であるか、絶対値が$1$以上です。
さらに、二つの既約な非整数の分数
$$\frac{a}{b},\qquad\frac{c}{d}\qquad(b,d\geq2)$$
について、$b,d$が互いに素なら、その和は整数になりません。
部分分数分解によって、整数条件を複数の分母の条件へ分けられることもあります。

平方根の整数・有理数条件

整数$N\geq0$について、
$$\sqrt{N}\text{が整数}\Longleftrightarrow N\text{が平方数}$$
です。
さらに、$\sqrt{N}$が有理数なら、実は$\sqrt{N}$は整数です。
したがって、判別式や平方完成から平方根が現れたときは、中身が平方数になる条件を調べます。

指数を含む等式

• 指数関数の増加の速さを利用する。
• $a^n-b^n$や$a^n+b^n$を因数分解する。
• 累乗の剰余の周期を調べる。
• $0,\pm1$となる法を探す。
• 素因数が現れる回数を比較する。
• 二項定理を使う。
  例えば
  $$5^n=(2+3)^n$$
  と見れば、二項定理によって法$3^k$での情報を取り出せることがあります。

階乗

• $n!$は$1,2,\ldots,n$すべての倍数である。
• $n\geq m$なら$n!/m!$は整数である。
• $n\geq m$なら$n!\equiv0\pmod m$である。
• 素因数が現れる回数にはルジャンドルの公式を使う。
• 階乗の増加の速さを不等式で利用する。
  階乗を含む素数問題では、十分大きな変数に対して多くの小さな素数を因数にもつことが強力な制限になります。

方程式と整数

• 一つの解を代入して因数分解する。
• 一方の文字について解き、整数条件を調べる。
• 二次方程式なら判別式が$0$以上かつ平方数となる条件を見る。
• 積が一定値となる形を作る。
• 解と係数の関係を利用する。
• グラフを用いて整数点や交点を視覚化する。
  方程式を実数の範囲で解いて終わりではなく、得られた解のうち整数となるものを選びます。

漸化式

漸化式を法$m$で考えると、各項の剰余は$m$通りしかありません。
一定個数の直前の剰余から次の剰余が一意に決まるなら、それらを一つの「状態」として考えられます。状態は有限個なので、同じ状態が再び現れた後は同じ変化を繰り返します。
したがって、多くの場合で剰余列はやがて周期的になります。
また、
$$\gcd(a_n,a_{n-1})$$
を漸化式によって
$$\gcd(a_{n-1},a_{n-2})$$
へ落とし、最初の項まで戻す方法も頻出です。

ガウス記号・床関数

本稿では、$x$以下の最大の整数を
$$\lfloor x\rfloor$$
と書きます。
定義から
$$\lfloor x\rfloor\leq x<\lfloor x\rfloor+1$$
であり、
$$x=\lfloor x\rfloor+r\qquad(0\leq r<1)$$
とおけます。
また$t\geq0$なら、$0< y\leq t$を満たす整数$y$の個数は$\lfloor t\rfloor$です。
したがって$\lfloor f(n)\rfloor$を、曲線$y=f(x)$の下にある格子点の個数として捉えられる場合があります。
まず具体値を入れて、階段状の変化を観察することも有効です。

二項係数

さらに、$p$が素数で$1\leq k\leq p-1$なら、
$$ {}_pC_k$$
は$p$の倍数です。
二項定理
$$(1+x)^n={}_nC_0+{}_nC_1x+{}_nC_2x^2+\cdots+{}_nC_nx^n$$
をそのまま使うほか、両辺を微分・積分したり、$x=1,-1$などを代入したりすることで、二項係数の和を求められます。

有理数・無理数

有理数は整数$a,b$を用いて
$$\frac{a}{b}\qquad(b\neq0)$$
と表せます。必要なら$a,b$を互いに素としてよいです。

• 有理数であることを示すなら、この形で表す。
• 無理数であることを示すなら、有理数と仮定して矛盾を導く方法が基本となる。
• 有理数の和・差・積は有理数である。
• $0$でない有理数で割った商も有理数である。
• 有理数は、ある正の整数倍を取れば整数になる。
  一方、無理数どうしの和や積が必ず無理数になるわけではありません。
  平方数でない正の整数$d$と有理数$a,b,c,e$について
  $$a+b\sqrt d=c+e\sqrt d$$
  なら、$\sqrt d$が無理数であることから
  $$a=c,\qquad b=e$$
  が得られます。
  複素数の実部・虚部を比較する感覚と少し似ていますが、その根拠は$\sqrt d$の無理数性です。

---

さらに学びたい人へのキーワード

ここからは、標準的な整数問題の先へ進むためのキーワードです。
名前を覚えることが目的ではありません。「どのような場面で使われるものか」を軽く知り、興味をもったものから調べてみてください。

ディリクレの部屋割り論法

いくつかの対象を、それより少ない個数の箱へ入れると、少なくとも一つの箱には二つ以上の対象が入るという原理です。
整数問題では、余りを箱とみなす使い方が非常に多いです。

素数が無数に存在すること

有限個しかないと仮定し、それらすべての積に$1$を加えた数を考える古典的な背理法です。
素数問題における「既知の素数をすべて避ける数を作る」という発想の原型でもあります。

ベズーの等式

少なくとも一方が$0$でない整数$a,b$の最大公約数を$d$とすると、
$$ax+by=d$$
を満たす整数$x,y$が存在します。
一次不定方程式、逆元、互いに素の証明などにつながります。

中国剰余定理

複数の法に関する合同条件を、一つの合同条件へまとめる理論です。
特に法どうしが互いに素な場合に強力です。

ルジャンドルの公式

素数$p$が$n!$に現れる回数は
$$v_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots$$
で与えられます。右辺は途中から$0$になるため、実際には有限和です。

無限降下法

解が存在すると仮定し、その解からさらに小さい正の整数解を作ります。
同じ操作を繰り返せば正の整数が際限なく小さくなることになり、矛盾します。
正の整数には最小のものが存在するという離散性を、真正面から利用する方法です。

ペル方程式

平方数でない正の整数$d$に対する
$$x^2-dy^2=1$$
のような方程式です。
平方完成、因数分解、無理数、漸化式など多くの話題とつながります。

ヴィエタ・ジャンピング

二変数の対称な二次方程式を一方の文字についての二次方程式と見て、解と係数の関係から別の整数解を作る方法です。
新しく得た正の整数解の方が小さいことを示し、無限降下法へつなげます。

LTEの補題

$a^n-b^n$や$a^n+b^n$に、ある素数$p$が何回現れるかを求める補題です。
公式だけでなく、素数$p$、指数$n$、$a,b$の整除条件を確認して使う必要があります。

完全剰余系・既約剰余系

法$m$におけるすべての剰余を一度ずつ代表するものが完全剰余系です。
そのうち$m$と互いに素な剰余だけを集めたものが既約剰余系です。
オイラーの$\varphi$関数、オイラーの定理、逆元などへつながります。

オイラーの$\varphi$関数とオイラーの定理

$1$以上$n$以下の整数のうち、$n$と互いに素なものの個数を$\varphi(n)$と表します。
$a$と$n$が互いに素なら、
$$a^{\varphi(n)}\equiv1\pmod n$$
が成り立ちます。

シルベスター・シューアの定理

連続する整数の積や二項係数に現れる素因数を扱う定理です。
二項係数が素数の累乗になる場合など、非常に難しい整数問題と関係します。

---

数そのものに関する話題

以下は直接の解法というより、整数の世界を広げてくれる話題です。

完全数

自分自身を除く正の約数の和が、その数自身に等しい正の整数です。
例えば$6$は
$$1+2+3=6$$
より完全数です。

メルセンヌ数・フェルマー数

自然数$n$に対する
$$2^n-1$$
の形の数をメルセンヌ数と呼びます。これが素数なら、指数$n$も素数でなければなりません。
$0$以上の整数$n$に対する
$$2^{2^n}+1$$
の形の数をフェルマー数と呼びます。
素数、因数分解、指数の剰余などと深く関わります。

カタラン数

$$\frac{{}_{2n}C_n}{n+1}$$
で表される整数です。
場合の数に現れる数列ですが、二項係数の整数性や約数の問題として眺めることもできます。

レピュニット数

十進法で
$$1,11,111,1111,\ldots$$
と表される数です。
等比数列、因数分解、合同式、素数問題につながります。

タクシー数

二つの正の立方数の和として、順序の入れ替えを同一視して異なる$n$通りに表される正の整数のうち、最小のものを$n$番目のタクシー数と呼びます。
有名な例として、二番目のタクシー数
$$1729=1^3+12^3=9^3+10^3$$
があります。

---

整数と他分野との接続

格子点と面積

座標平面上で$x,y$が整数となる点を格子点といいます。
整数解の個数を格子点の個数として数えたり、図形の内部・辺上の格子点と面積を結び付けたりできます。
発展事項として、ピックの定理などがあります。

ピタゴラス数

$$a^2+b^2=c^2$$
を満たす正の整数の組$(a,b,c)$をピタゴラス数と呼びます。
$a,b,c$が互いに素な原始ピタゴラス数なら、必要に応じて$a,b$を入れ替えることで、互いに素で偶奇の異なる自然数$u,v$を用いて
$$a=u^2-v^2,\qquad b=2uv,\qquad c=u^2+v^2\qquad(u>v)$$
と表せます。
一般のピタゴラス数は、これらを同じ正の整数倍することで得られます。

$n$進法

十進法だけでなく、二進法、三進法などで整数を表すと、桁の和、倍数判定、繰り上がりなどが見えやすくなる場合があります。
さらに発展的な表し方として階乗進法などがあります。

多項式と整数

整数係数多項式$f(x)$と異なる整数$a,b$について、$a-b$は$f(a)-f(b)$の約数です。
これは値の差が因数分解できるためであり、
$$a-b$$
と
$$f(a)-f(b)$$
の整除関係を調べられます。
有限差分、整数値多項式、チェビシェフ多項式なども関連するキーワードです。

二項定理の微分・積分

二項定理を多項式の恒等式として微分・積分することで、二項係数を含む和を求められます。
整数問題、場合の数、数列、微積分が交わる地点です。

---

練習問題

ここからは、ここまでに登場した考え方を実際に使う問題です。
解法名を先に当てるのではなく、

現在の条件から、次に何を使えば候補が減るか
を考えてみてください。

練習問題（応用）

---

演習問題

ここからは、複数の考え方を組み合わせる問題が中心です。難易度も少し上がります。

---

問題の出典について

出典のある問題については、大学名・年度などで検索すれば、大抵は解答が見つかると思います。
自作問題などについては、今後優先的に解説を追加する予定です。
作問者Twitter（X）リンク

• フラワ
• チェベラウス

---

最後に

ここまで読んでくださり、ありがとうございます。
本稿は、整数問題に現れるすべての理論を一つずつ完全に解説したものではありません。
しかし、

• 整数問題では離散性を使って候補を絞ること
• 因数分解・不等式・約数や余りという三大解法があること
• 実戦ではそれらを組み合わせること
• さらに学ぶべき多くのキーワードがあること
  は見えてきたのではないでしょうか。
  知らないキーワードが残っていても問題ありません。
  演習の中で必要になったときに調べ、使い、もう一度この記事へ戻ってくる。その繰り返しによって、名前だけだった道具が少しずつ自分の武器になっていきます。
  整数は、試行錯誤するほど見えるものが増えていく分野です。
  ぜひ多くの問題に触れ、皆さん自身の「絞り込み方」を増やしていってください。
  みなさまの日常に良き数学の彩りのあらんことを。
  それでは、ごきげんよう。