平方剰余の分布
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 22:39 UTC 版)
平方剰余は n を法としてランダムなパターンが見られ、これは音響や暗号などの応用で利用されているが、一方でその分布は規則性も示す。 算術級数の素数に関するディリクレの定理、平方剰余の定理、および中国の剰余定理（CRT）を使うと、任意の M > 0 に対して、1, 2, ..., M が全て素数 p を法として剰余であることが簡単にわかる。 例えば、 p ≡ 1 (mod 8), (mod 12), (mod 5), (mod 28) ならば、平方剰余の定理から 2, 3, 5, 7 は素数 p を法として剰余であり、故に1〜10のすべての数字が剰余になる。CRTはこれが p ≡1 (mod 840) の場合と同じであり、ディリクレの定理はこの形式の素数の無限に存在すると主張する。これを満たす素数 p は 2521 が最小であり、実際に12 ≡ 1, 10462 ≡ 2, 1232 ≡ 3, 22 ≡ 4, 6432 ≡ 5, 872 ≡ 6, 6682 ≡ 7, 4292 ≡ 8, 32 ≡ 9, 5292 ≡ 10 (mod 2521) となる。
※この「平方剰余の分布」の解説は、「平方剰余」の解説の一部です。
「平方剰余の分布」を含む「平方剰余」の記事については、「平方剰余」の概要を参照ください。
ウィキペディア小見出し辞書の「平方剰余の分布」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 平方剰余の分布のページへのリンク
