「素数」の性質と使い方まとめ

それではいきましょう！

はじめに

東大や京大をはじめとする入試問題で「素数」という条件はよく出題されます．

「整数」という条件だけでも強力であることはわかっていると思いますが，整数の中でも「素数」は圧倒的に強い条件です．

ですので問題に「素数」が出てきた場合は，他の条件そっちのけで利用しにいくぐらいの意識を持っておいてください．

今回はそんな「素数」の性質や使い所をまとめていきましょう．

素数条件の利用

素数である以前に整数ですから，いつもの「3ヶ条」と結びつけて考えていきます．

（3ヶ条の記事を読んでいない場合はこちら(click!)から．）

まず素数とは「1と自身以外に約数を持たない2以上の自然数」と定義されます．1が素数ではないことは注意しておきたいですね．

この定義から考えると，3つのうち「約数・倍数関係」と「剰余系」との相性が良さそうです．

特に「約数・倍数関係」は，素因数分解の一意性を利用するものでしたからなおさらと言ったところでしょうか．

素数と約数・倍数関係

約数・倍数関係は（整数の積）＝（約数の分かる値）の形を作ることが重要でした．．

約数の分かる値とは，素因数が分かる数のこと．つまり素数が右辺にあれば良いのですね．

これが大前提の性質です．平方数$a^2$が$p$の倍数なら$a^2$は$p^2$の倍数など，応用できますね．

以下のような問題を考えてみましょう．

さてどう考えたでしょうか．右辺が定数で，左辺が因数分解できる，と考えましたか？

$x(2x^2+2x+5)=2p-5$

ここで困ったはずです．
右辺の約数が分かるでしょうか？素数$p$を含んでいても，$2p-5$のように和の形になってしまうと素因数はわからないのですね．

この式の中で，素因数が分かるのは$2p$と$-5$の2つです．左辺を因数分解することを意識すると，$2p$を残して$-5$を移項すべきでしょう．

あとは$2p$を素因数に分けて，因数分解した左辺に分配していきましょう．細かいところは約数・倍数関係の記事(click!)をみてください．

例題解答

「素数について解く」と素数の条件が使いやすくなりますね．

素数と剰余系

素数は自然数の最小単位です．例えば，「偶数の素数」は2しかありませんし，「3の倍数の素数」は3しかありません．

つまり，剰余系の条件と組み合わせて使うことで素数はかなり絞り込まれるのです．

素数は小さいものから$2,3,5\cdots$ですから，だいたいはmod$2,3,5$あたりの出題が多い印象を受けます．さて以下のような問題を考えてみましょう．

早稲田大学の入試問題からです．例題にしては少し難しいかもしれませんね．

こうした問題の多くは$n$は有限個だろうと見切りをつけて，実験していきましょう．

$n=1$で2,5,11
$n=2$で5,19,17

と，この2つは解となりますね．

続いて，$n=3$で10,21,29は満たさず，$n=4$で17,35,101とこちらも満たしません．

もう少し実験を続けても良いですが，この時点でも$n$が3を超えたあたりから様子が変わっていることに気づくと思います．

特に$n=4$では35のみ素数ではない数（＝合成数）が出てきていることに注目すれば，5を法とする剰余系の利用を考えつくのではないでしょうか．

他の場合を見ていても，常に5の倍数は登場しているようです．あとは合同式の代入計算を行いましょう．

素数と剰余系に関しては，もう一つ

という性質を覚えておいて欲しいのですが，また別の記事で説明することにします．

まとめ