素数にまつわる覚えておくべき性質まとめ

【素数についての性質】

• $p$ が素数，$m, n$ が整数で，$mn=p$ なら $m$ か $n$ のどちらかの絶対値が $1$
  これは素数の定義から当たり前の事実ですが不定方程式を解くときなどに使う基本的な性質です。

• 素数 $p$ と任意の自然数 $a$ に対して $a^p\equiv a\pmod{p}$
  →フェルマーの小定理の証明と例題

• その他，受験で役立つ機会は少ないですがマニアックな定理として，ウィルソンの定理やアイゼンシュタインの定理があります。
  →ウィルソンの定理とその2通りの証明
  →アイゼンシュタインの定理

• 大きな数の素因数分解はとてもむずかしい。
  →素因数分解の難しさと素数判定

• 素因数分解の高速なヒューリスティックス
  →素因数分解の高速なアルゴリズム（ロー法）

• 素因数分解の一意性
  →素因数分解の一意性とその証明について

• 素数は無限に存在する
  →素数が無限にあることの4通りの証明

• $a ,b$ が互いに素な自然数のとき $an+b$ （$n$ は自然数）の形で表される素数は無限個存在する。（ディリクレの算術級数定理）
  →整数論の美しい定理7つ

• 素数の逆数和は発散する
  →素数の逆数和が発散することの証明

• エラトステネスのふるい
  →エラトステネスのふるいとその計算量

• 双子素数
  →双子素数にまつわるいくつかの話題

• 素数表
  →素数一覧（5桁以下，10万以下，番号つき）

【「互いに素」についての性質】

• $ab\equiv ac\pmod{p}$ で $a$ と $p$ が互いに素なら $b\equiv c\pmod{p}$
  →合同式の意味とよく使う6つの性質

• $x, y$ についての不定方程式 $ax+by=1$ が整数解を持つ
  ⇔ $a$ と $b$ は互いに素。
  →一次不定方程式ax+by=cの整数解

• フィボナッチ数列の隣り合う二項は互いに素。（一般の三項間漸化式で表される数列に対しても同様な議論が考えられる）
  →フィボナッチ数列の5つの性質（一般項・黄金比・互いに素）

• 法が互いに素だと連立合同式が解きやすい
  →中国剰余定理の証明と例題（二元の場合）

• 「$n$ と $n+1$ は互いに素」など
  →互いに素の意味と関連する三つの定理