2014/08/24

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

分野: まとめ

素数について,ついでに互いに素な2つの整数について,覚えておくべきことを整理しました。比較的レベルが高い内容になっています。

素数の基本的な性質,定理

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

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

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

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

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

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

・フィボナッチ数列の異なる二項は互いに素。(一般の三項間漸化式で表される数列に対しても同様な議論が考えられる)
→フィボナッチ数列の一般項と数学的帰納法

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

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

教養としての素数の知識

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

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

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

・素数は無限に存在する
→素数が無限にあることの美しい証明

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

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

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

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

・素数表
→素数一覧(4桁以下,番号つき)

「素数」の意味を理解するのは簡単ですが,非常に奥が深い分野です。
分野: まとめ