整数の基本3ヶ条とその利用

はじめに

今回は整数問題を解く上で理解すべき3つの性質をまとめます．

これから整数問題を解く際には「３つのどれを使って解くのか」と方針を考えますし

間違えた問題に対しても「３つの内どの視点を用いたら解けたのか」を意識していくことになります．

整数は苦手とする人が多い分野ですが，理解した時には視野が大きく広がっているはずです．

整数は数直線上の数（実数）とは大きく異なる性質があります．

問題を解くときは，それらを用いて「整数解を有限個に絞り込む」ことを意識します．

まだピンとこないとは思うので各性質のところにリンクされている記事や例題を通して実感してください．

（(click!)で３つの重要事項の記事を見れます．）

性質１：素因数分解の一意性

「あらゆる（正の）整数は唯一通りに素因数分解することが出来る」

という性質です．

例えば$12$は$2^2 \times 3$でこれ以外の素因数分解は存在しません．

これは非常に重要な性質で約数・倍数関係(click!)に利用されます．

約数や倍数は，整数の最小単位である素因数が決定しています．

ですので「素数」という条件は非常に強力であり，問題で与えられた場合はここをとっかかりにすることが多いです．

性質２：離散性

「整数は１飛ばしに点在する」

という性質です．

数直線上の点を適当に選んだときそれは実数です．連続的に存在しています．

一方で，整数は１飛ばしに綺麗に並んでいます．これを整数の離散性と呼びます．

「連続関数$f(x)$」に対し，定義域が整数値しか取り得ない関数$g(n)$は「離散関数」と呼ばれます．

こちらも非常に重要な性質で大小関係（不等式評価）(click!)に利用されます．

性質３：剰余

「（正の）整数について割り算と余りが設定できる」

という性質です．

実数で割り算はまだしも余りを定義することはいまいちピンと来ませんね．

「整数」の中だからこそ割り算や商，余り（剰余）を定めることが出来ます．

これを利用するのが剰余系（合同式）(click!)です．

整数全体を何かの数で割った余りで分類します．

無限個ある整数を有限個のグループに分けて扱うことが出来るという点で優れていますね．

まとめ