巨大素数

Last-modified: 2020-06-08 (月) 11:53:33

巨大素数とは、巨大な素数である。定義ははっきりされていないが、10,000桁が基準とされている。

素数ニュース

(この欄では、50位以上の素数更新や、形の1位更新などをニュースにしますが、手動更新のため更新頻度は低いです。)
2020年2月14日、51位の巨大素数 2×3^5570081+1 (2,657,605桁)が発見されました!この素数は、円分多項式に2を代入したものの倍数でもある素数でもあり、その形の中で当時1位の素数です。(ページ
2020年2月29日、 20位の巨大素数 6962×31^2863120-1 (4,269,952桁)が発見されました!(ページ
2020年3月7日、48位の巨大素数 11×2^9381365+1 (2,824,074桁)が発見されました!この素数は、6を底とする一般化フェルマー数の約数でもあり、その形の中で当時1位の素数です。(ページ
2020年3月13日、37位の巨大素数 9×2^11158963+1 (3,359,184桁)が発見されました!この素数は、5を底とする一般化フェルマー数の約数でもあり、その形の中で当時1位の素数です。(ページ
2020年3月13日、30位の巨大素数 9×2^11500843+1 (3,462,100桁)が発見されました!この素数は、12を底とする一般化フェルマー数の約数でもあり、その形の中で当時1位の素数です。(ページ
2020年3月26日、33位の巨大素数 9×2^11366286+1 (3,421,594桁)が発見されました!この素数は、一般化フェルマー数でもあり、当時3位の素数です。(ページ
2020年3月29日、28位の巨大素数 9×2^12406887+1 (3,734,847桁)が発見されました!この素数は、3を底とする一般化フェルマー数の約数でもあり、その形の中で当時1位の素数です。(ページ
2020年3月31日、26位の巨大素数 9×2^13334487+1 (4,014,082桁)が発見されました!この素数は、3を底とする一般化フェルマー数の約数でもあり、その形の中で当時1位の素数です。(ページ
2020年4月17日、巨大素数 3555×2^1542813-4953427788675×2^1290000-1 (464,437桁)が発見されました!この素数は、3連続の等差数列の項であるような素数の中で当時1位の素数です。

目次

素数

素数は、自然数のうち、正の約数が1とそれ自身のみであるものを言うが、それを判定するのは難しく、巨大な素数が発見されるようになったのはコンピュータが発達した現代になってからである。2020年3月現在最大の素数は2^82589933-124,862,048桁である(ページ

巨大素数の歴史

それ以前にも6桁の素数の存在は知られていたが、1772年、2^31-1=2,147,483,647(10桁)を偉大な数学者オイラーが発見した。
そのあと、1885年、(2^64+1)/274177=67,280,421,310,721(14桁)をトーマス・クラウセンが発見した。
ここまでは、試し割りを改良したとても根気のいる方法だったが、その後新しい素数判定法が生み出される。
1876年、2^127-1(39桁)をエドゥアール・リュカがリュカ-レーマーテスト(Lucas-Lehmer Test)を用いて発見した。
1951年、(2^148+1)/17(44桁)をAimé Ferrierがプロスの定理(Proth's Theorem)を用いて発見した。
その後は、電子計算機を使って素数が発見されていった。
1952年、2^521-1(157桁)が発見された。これは100桁を超える初めての素数である。
1961年、2^4423-1(1,332桁)が発見された。これは1,000桁を超える初めての素数である。
1979年、2^44497-1(13,395桁)が発見された。これは10,000桁を超える初めての素数である。
1992年、2^756839-1(227,832桁)が発見された。これは100,000桁を超える初めての素数である。
1999年、2^6972593-1(2,098,960桁)が発見された。これは1,000,000桁を超える初めての素数である。
2008年、2^43112609-1(12,978,189桁)が発見された。これは10,000,000桁を超える初めての素数である。
このように、巨大素数発見の歴史はコンピュータ発達の歴史といっても過言ではない。

巨大素数が簡単に発見できるような方法を見つけた場合、人類は長らくこの方法を得られてないのでとてもすごい。ぜひ発見してみてほしい(おそらくニュースにも乗る)

素数判定

素数判定は「確実に素数といえる」ものと「確実に素数とはいえない」ものがある。
確実に素数といえる判定法は決定的素数判定法という。
確実に素数とはいえない判定法は確率的素数判定法という。
しかし、決定的素数判定法は、だいたいの自然数に対しては結構遅く1万桁以上になってくるとかなりきついので、巨大素数の判定は確率的素数判定法を使う場合が多い。
アルゴリズムには、Pythonコードを載せたけど間違いがあるかもしれないので、そのときは直します。計算量についても、それを勉強してからまた追記したいと思う。

素数判定の確信性

確率的素数判定法について、たとえば、フェルマーテストは確率的に素数判定を行う。その判定法はこの項目では詳しく説明しないが、「フェルマーテストに落ちたなら、その数は素数ではない」ことは確実に言えるが、「フェルマーテストを通ったなら、その数は素数である」とは言えない。
しかも、フェルマーテストに強い非素数というものが存在して(カーマイケル数)、小さい方から561, 1105, 1729, 2465,…と続く(数列)。
ただ、素数の桁数が多くなると、フェルマーテストを通る自然数はいい感じの確率で素数となる。このような数を、「確率的素数(PRP)」という。桁数が多くなるほど、PRPが素数である確証は高くなるが、数学的に「素数である」という保証はないため、素数であるとは認められない。そのようなPRPを完全に素数だと証明するには、ECPPテストが人気である。しかし、その判定法は遅く、せいぜい4万桁くらいが限界である。

計算量の話

以下に乗せているコードはPythonなので、若干他の言語と計算速度が左右するかもしれないが、アルゴリズムが一致していればだいたいは共通していると思う。(時間)計算量は、素数判定する数の大きさや、(確率的素数判定なら)試行回数などに左右される。アルゴリズムによって計算量の評価をしたいとき、計算量を関数で表すことがある。これはオーダー記法またはランダウの記号といわれ、O(f(x)) というように表す。f(x)は、定数倍は無視した形となる。また、アルゴリズムにかかわる数のうち、一番影響を及ぼす(急激に増える)ものだけを採用する。
例1: 計算量5n+9のとき、O(n)
例2: 計算量2n²+40n+9のとき、O(n²)
例3: 計算量5×n!+n⁵のとき、O(n!)←階乗は強すぎ
例4: 計算量10のとき、O(1)
たとえば、1~nを全て足す問題を考える。単純に1から順番に足していけばよい。このとき、計算量はn回足すことを繰り返すのでO(n)となる。しかし、1~nまでの総和は n(n+1)/2 と表されるので、こちらを使ってもいい。これを実行した場合は掛け算1回とわり算1回だけで済むので、これはO(1)になる。後者のほうが、Oの中身は軽いので「より速い」アルゴリズムとなる。
まあアルゴリズムというのはそんなに固い言葉には思わず、ある問題を解決するための計算みたいなことなんだなあと思ってくれてもいい。なんなら、さきほどの1~nを全て足す問題で、1からnまで順番に足すのもひとつのアルゴリズムだし、n(n+1)/2を使うのもひとつのアルゴリズムである
ところで、n(n+1)/2を使うやり方は順番に足すものと比べたら難しいが、ドイツの有名な天才数学者ガウスは7歳のころに先生にこの問題を出された瞬間このやり方で即答したらしい。天才かな?

計算量に使う関数

ここは超適当な説明のため、計算量オーダーの求め方を総整理! ~ どこから log が出て来るか ~を参考にすることをオススメします。

n^m

mが大きいほど, n^mは急激に増加する。m≧2だとn≧100000の計算は厳しいかもしれない。
注意してほしいのは m=1/2のとき、n^(1/2)=√n はnよりも緩やかに増加する。
m=0のとき、n^0=1より O(1)と表せる。これはnがなんであれ速く計算できる。
m<0のとき、nが増えると逆に計算量が減る。こんなアルゴリズムは見たこと無いので、ぜひ知ってたら教えてほしい。

log n

logは対数であるが、このとき底は書かない。なぜかというと、底がなんであれ、底の変換公式で底が2の対数の定数倍になってしまうからである。たとえば log₁₀n = log₂n / log₂10 は log₂nの定数倍である。このlog nという関数は、m>0の場合のn^mより弱い。桁数が1つ増えると, log nは定数だけ増える。しかし、n^mは桁数が1つ増えるとだんだん急速に増えていく。やがてn^mは log nを追い越す。
例1: 計算量log₂n + 5nのとき、O(n)
例2: 計算量 nlog₂n+nのとき、O(nlogn)
例3: 計算量 log₂(log₂ n)のとき, O(loglogn)

2^n

指数関数はlog nの逆関数である。つまり、「めちゃくちゃ急激に増加」する。nが1増えると、2^nは2倍になる。2倍,2倍…と繰り返すとやがて膨大な数になる。n=30くらいが限界かなと思う。3^nなどでも同様である。この2^nは、{A1, A2, … An}というnつの集合の部分集合を表す。これは、A1について選ぶか選ばないかで2通り、A2について選ぶか選ばないかで2通り、と繰り返すと 2^nになるからである。

n!

n!は階乗であり、n!=1×2×3×…×nと定義される。この関数は超超超急激に増加する。なぜなら、(n+1)!はn!の(n+1)倍になるからである。たとえば、7!=5040だが、8!は7!×8=5040×8=40320である。これをn≧15でやったらもうコンピューターでは追いつかない。でも、n≦10だといけるし、一番単純に実装するとこうなるアルゴリズムもある(特に順列関係)。今までみたものだと、この関数は最強である。

強さランキング

≡速い≡
O(1)…最 強 最 速
O(log n)…最高!!何桁でも余裕!!(さすがにn=10^10^8は時間かかる)
O(√n)…超強い n≧10^16は時間かかる
O(n)…強めな方 n≧10^8は時間かかる
O(nlogn)…普通 n≧10^6は時間かかる
O(n²)…遅い n≧10^4は時間かかる
O(n³)…遅すぎ n≧10^3は時間かかる
O(2^n)…遅すぎて泣く n≧27は時間かかる
O(n!)…遅すぎて号泣 n≧11は時間かかる
≡遅い≡

決定的素数判定法

決定的素数判定法はnが素数だと確定することが可能である。10^15以下くらいの一般の小さい素数に対しては、改善された試し割り法がよく使われる。

一番単純な試し割り法

素数の定義は、正の約数が1とそれ自身のみであるものであるので、nを素数とすると当然2以上n-1以下の全ての整数に対しては、割った余りが0とはならない(割り切れない)。逆に2以上n-1以下の全ての自然数でnが割り切れなければ、nは素数である。
計算量はO(n)である。

(単純な)試し割り法
2以上n-1以下の整数m に対して、 n mod m ≠0 を判定する
def isprime(n):
	""" nが素数であるかどうか判定します """
	for k in range(2, n):
		if n % k == 0:
			return False
	return True
print(isprime(1000003))

実行結果: True
しかし、もしnが素数の場合n≧100万の場合単純に「割った余りを求める」作業を100万回行うので少し大きいだけの素数でも時間がかかる。この方法では100億以上の自然数の素数判定は数分以上かかる
2~10,000の素数を列挙するのにかかる時間:0.39992785453796387秒
2~100,000の素数を列挙するのにかかる時間:31.709169149398804秒
2~1,000,000の素数を列挙するのにかかる時間:非常に長い(おそらく10分以上)
以下の改善された試し割り法が圧倒的に速い。

改善された試し割り法

自然数nが合成数のとき、ある自然数a,bを用いてn=abと表される。このとき、自明にa,bはnの約数であるが、aとbのどちらかは√n以下である。理由は、a,bのどちらも√nより大きいとすれば、ab>nであるからである。逆にa,bのどちらも√nより小さいとすれば、ab<nである(まあこれはあまり気にしなくてもいい)。たとえば、243=3×81だが、15<√243<16であるので3<√243である。また、10201=101×101など、a=bのときはちょうどa=b=√nである。
逆に、2以上√n以下の全ての自然数でnが割り切れなければ、nは素数である。これは、nを合成数と仮定するとn=abとなるような自然数a,bが存在して、それのどちらかは√n以下であるが、2以上√n以下の全ての自然数でnが割り切れなければそのような数は見つけられないからである。

試し割り法
2以上√n以下の整数m に対して、 n mod m ≠0 を判定する.

n=2,3だとmが存在しないため、問答無用で素数となる。実際、2と3は素数である。一方、mが初めて存在する4では4 mod 2=0のため、素数ではないので矛盾は起きていないことがわかる。
計算量はO(√n)である。

def isprime(n):
	""" nが素数であるかどうか判定します """
	for k in range(2, int(n**0.5)+1):
		if n % k == 0:
			return False
	return True
print(isprime(1000003))

実行結果: True
上のコードは、一番単純な試し割り法のrange(2, n)の部分がrange(2, int(n**0.5)+1)に変わっただけだが、圧倒的に判定する速度は早くなる。たとえば単純な素数判定では難しかった100億=10^11レベルの素数判定も10万回だけ繰り返せばよく、数分かかる単純な素数判定より10万倍速い約0.01秒で素数判定ができる(10000000019でお試しあれ)nが100倍に増えると計算時間は10倍になる。22桁以上の素数判定は厳しいが、日常で使うレベルの素数を判定するには便利である。
2~10,000の素数を列挙するのにかかる時間:0.012992620468139648秒
2~100,000の素数を列挙するのにかかる時間:0.2184467315673828秒
2~1,000,000の素数を列挙するのにかかる時間:4.860994815826416秒
2~10,000,000の素数を列挙するのにかかる時間:138.74981594085693秒
1855年に発見された素数「67280421310721(14桁)」の素数判定:0.9016158580780029秒

ウィルソンの定理

ウィルソンの定理
2以上の自然数pが素数であるための必要十分条件は (p-1)! ≡ -1 (mod p) である。

この定理はきれいで面白い。証明はフェルマーの小定理を利用されることが多いが、自分が知ってる中で簡潔なものでも原始根定理を使う(この定理の証明は今後理解しようと思う)。ここでは省略する。
さて、パソコンではnの階乗を計算するのは非常に時間がかかり、1000000!でも8秒程度かかる。しかし、nの階乗を自然数pで割る(素数でなくてもよい)ということをやりたければ、その都度pで割ったほうが大きい数を扱わないので、計算量は減る。
計算量はO(n)である。しかし、結局大きい数を掛けたり割ったりするので試し割りよりは非効率である。

def modfact(n, p):
	"""nの階乗をpで割った余りを返す"""
	ans = 1
	for i in range(1, n+1):
		ans = ans * i % p
	return ans

これを少し変形して、(p-1)!をpで割った余りが-1(p-1)となっているか判定する。しかし、pで割った余りが0となったら、そこから先は全部0となるため、この時点で素数ではないとする。また、p>4のときには合成数は必ず (p-1)!をpで割った余りが0になる。これを利用する。

def isprime(n):
	if n == 4:
		return False
	ans = 1
	for i in range(1, n):
		ans = ans * i % n
		if ans == 0:
			return False
	return True

2~10,000の素数を列挙するのにかかる時間:1.0970637798309326秒
面白いけど普通に試し割りの方が速いことがわかった。

確率的素数判定法

フェルマーテスト

フェルマーの小定理
pを素数とする。 a, pが互いに素であるとき、a^(p-1) ≡ 1 (mod p)

これは数論でも結構重要な定理だが、確率的素数判定でも使える。フェルマーの小定理の対偶をとると、「aとnが互いに素であって、a^(n-1) ≡ 1 (mod n)を満たさないようなaが存在するとき、nは合成数である。」しかし、nが合成数であっても、偶然a^(n-1) ≡ 1 (mod n)を満たすaが存在することがあり、これの存在により、フェルマーテストは確率的素数判定となる。特に、nと互いに素な全てのaに対して, a^(n-1) ≡ 1 (mod n)を満たさないaが存在しないものをカーマイケル数という。

フェルマーテスト
nに対して、2以上n-2以下の自然数aをランダムに選ぶ。a^(n-1) ≡ 1 (mod n) ならば, nは合成数である。しかし、偶然合成数とは判定されないケースがあるので、k回繰り返す。kは多いほど精度が高い。

a^(n-1)をnで割った余りを求めるためには普通に考えると掛け算を繰り返すので計算量はO(n)となるが、二分累乗法というアルゴリズムを利用するとO(logn)となる。よって、フェルマーテストの計算量はO(k logn)となる。これは改良された試し割り法よりも高速である。

import random
def isprime(n, k):
	if n==1: return False
	if n==2 or n==3: return True
	for _ in range(k):
		a = random.randrange(2, n-1)
		if pow(a, n-1, n) != 1:
			return False
	return True
print(isprime(10000000019, 5)

フェルマーの小定理の性質上、素数に対しては必ず「素数」と判定する。一方合成数に対してはたまに間違って素数と判定してしまう。その確率を減らすためにはk(試行回数)を増やすしかない。しかし、その分だけ計算量が増える。isprime(n, k)はnに対してk回試行するフェルマーテストとする。
isprime(15, 1):誤判定確率 16.70%
isprime(15, 2):誤判定確率 2.79%
isprime(15, 3):誤判定確率 0.47%
isprime(55, 1):誤判定確率 3.80%
isprime(55, 2):誤判定確率 0.14%
isprime(91, 1):誤判定確率 38.69% 100以下の整数ではこれが一番ひどい。
isprime(561, 1):誤判定確率 57.02% 1000以下の整数ではこれが一番ひどい。これはカーマイケル数である。
isprime(1729, 1):誤判定確率 74.83% 1729はラマヌジャンにからむ有名な数だから知っている人も多いが、実はこれもカーマイケル数である。
isprime(1729, 10):誤判定確率 5.61% まだ5%もある。

素数の種類

素数にはたくさんの種類がある。
以下に紹介する素数に、「最大の素数」「桁数」「難易度」「20位桁数」というものを載せているが、最大の素数は2020年3月現在その形で発見された最大の素数、桁数はその素数の桁数、難易度は桁数によって変化するThe Prime Pageの指標とする。20位桁数とは、今まで発見されたその形の素数を大きい方から並べて20位の桁数とする。逆にそれを超えた素数を発見すれば、The Prime Pageに新しい巨大素数として登録できるということである。

メルセンヌ素数

一番有名なのがメルセンヌ素数である。メルセンヌ素数は2^n-1という形で表される素数である。
現在51個見つかっている。2020年3月現在、一番大きい素数はこのメルセンヌ素数の形をしている。
2^n-1が素数となるためにはnが素数でなければならない という定理が存在するので、素数を見つけるときはこれを使う。
素数判定にはリュカ-レーマー・テスト(Lucas-Lehmer Test)を使うことで、比較的簡単に判定することができる。(それでも普通のパソコンでは1000万桁以上のメルセンヌ数に対しては判定1回につき軽く100日かかることが多い。)。この時間のかかる判定の前に小さい素数で試し割りすることで、ある程度素数候補をふるい落とすことができる。

もっと重要なのは、メルセンヌ素数が完全数と関係があるということである。完全数とは、それ自身を除く正の約数の和に等しい自然数である。たとえば、28の約数は1,2,4,7,14,28であるが、28を除く正の約数の和は1+2+4+7+14=28である。よって、28は完全数である。
2^n-1が素数ならば、2^{n-1}(2^n-1)は完全数である。ということは簡単に証明できる。実は最初に証明を与えたのはユークリッド(紀元前3世紀)である。
また、18世紀にオイラーが偶数の完全数はメルセンヌ素数に限ると証明した。
それにも関わらず、奇数の完全数は発見されていない。奇数の完全数が存在するかどうかは、未解決問題である。

最大の素数2^82589933-1
桁数24,862,048
難易度56.4713
掲載桁数227,832

二重メルセンヌ素数

2^(2^p-1)-1の形をしたものが二重メルセンヌ数である。もうよくわからないが、pが少し大きくなると2^(2^p-1)-1は超巨大になる。いまのところ4つ知られている。最小でも2^(2^61-1)-1(69京桁)はまだ素数でないことが証明されてないし、今のPCの技術では扱えないくらいでかい。

双子素数

(3,5), (5,7), (11,13), ... というふうに差が2つの素数のペアを双子素数という。双子素数は無限にあると予想されているが、証明されてない。この予想は「双子素数予想」と言う。
双子素数の逆数を無限に足していくと、どういう数になるかは未解決問題である。Viggo Brun氏によって1919年に、双子素数の逆数は収束することが証明された。この値はブルンの定数(Brun's constant)と呼ばれている。その推定値は1.902160578である。
ちなみに, 双子素数とは言わないが、差が246より小さい素数のペアは無限にあると証明されている。
また, (m, m+2)が双子素数であるための必要十分条件*1は、4{(m-1)!+1}≡-m (mod m(m+2)) *2 であるという不思議な定理がある。これはClement氏によって1949年に証明されたが、いまのところ実用には全く向かない。

最大の素数2996863034895×2^1290000-1
桁数388,342
難易度43.7286
掲載桁数37,936

階乗素数

n! = 1×2×…×n を階乗?という。この階乗という関数は、面白い性質がたくさんあっていろいろ紹介したいのだが、今回は巨大素数ということで巨大素数に関する話だけをしたいと思う。
まずn!というもの自体が使う記号の通りびっくりするほど急激に増加する関数である。どのくらい急激かと言われれば、1!=1で, 5!=120とここまではそんなだが、10!=3628800と爆発し、100000!にいたっては456574桁の数になる。
さて、n!±1が素数であるものを、階乗素数という。n!の定義より、n!は2,3,…,nの全てで割り切れる。ということは、n!±1は2,3,…,nの全てで割り切れないということである。この時点でもう素数っぽいが、実はn!±1は必ず素数になるわけではない。たとえば、4!+1=25は2,3,4では割り切れないが5で割り切れて素数ではない。それどころか、nが巨大になってくると素数でない確率の方が高い。また、この考えを利用して、n!+k (k=2,3,4,...,n)は必ず合成数になる。なぜかというと、n!+kはkで割り切れるからである。
n!±1の形で現在見つかっている素数はたったの48個しかない。n!±1の形で表される素数が無限個あるかどうかは未解決である。一方、n!+1の形で表される合成数が無限個あることは証明されている。(簡単な証明:ウィルソンの定理よりpが素数のとき、(p-1)!+1はpで割り切れ合成数である。素数は無限個存在するのでn!+1で表される合成数は無限個ある。)

最大の素数208003!-1
桁数1,015,843
難易度46.6812
掲載桁数1,000

カレン素数

1905年にジェームズ・カレンが研究を開始した素数の形で、n×2^n+1の形をしている。素数判定は、LLRが使える。カレン素数が無限にあるかどうかはわからない。

最大の素数6679881×2^6679881+1
桁数2,010,852
難易度48.7752
掲載桁数1,423

一般カレン素数

n×b^n+1の形をした素数の形である。bは2以上の自然数であれば何でも良い。

最大の素数2805222×5^5610444+1
桁数3,921,539
難易度50.8216
掲載桁数367,072

ウッダル素数

1917年にカレン数に関連して研究を開始された素数の形で、n×2^n-1の形をしている。素数判定は、Prothの定理が使える。ウッダル素数が無限にあるかどうかはわからない。

最大の素数8508301×2^17016603-1
桁数5,122,515
難易度51.6396
掲載桁数1,603

一般ウッダル素数

n×b^n-1の形をした素数の形である。bは2以上の自然数であれば何でも良い。

最大の素数2740879×2^13704395-1
桁数4,125,441
難易度50.9768
掲載桁数417,693

コメント

  • 今はまだ書きたいことの20%くらいしか出来てないから、次は重要で有名な「エラトステネスのふるい」「フェルマー数」「ウィルソンの定理」「フェルマーの小定理(フェルマーテスト)」のどれかを書きたいと思う -- 書いてる人? 2020-05-24 (日) 23:36:14
  • カレン素数・ウッダル素数・ウィルソンの定理について書いた。次は「フェルマーの小定理」「エラトステネスのふるい」「リュカ–レーマー・テスト」のどれかを書こうと思う -- 冬眠? 2020-05-26 (火) 15:00:34
  • フェルマーテスト・計算量について書いた。記事の完成度は30%くらい。 -- 2020-06-06 (土) 17:07:57
  • 次は、証明が非常に難しいアルゴリズム群をかきたい。個人的に興味がすごく湧いてる -- 冬眠? 2020-06-07 (日) 01:10:10
  • スッゲー -- 2020-06-08 (月) 11:53:33

URL B I U SIZE Black Maroon Green Olive Navy Purple Teal Gray Silver Red Lime Yellow Blue Fuchsia Aqua White

観覧者数

現在?
今日?
昨日?
合計?

タグ

Tag: 数学


*1 これは, (m, m+2)が双子素数ならば4{(m-1)!+1}≡-m (mod m(m+2) )が成立し、逆に4{(m-1)!+1}≡-m (mod m(m+2) )が成立するならば(m, m+2)が双子素数である、ということが両方成り立つという意味である。詳しくは、高校数学Ⅰの命題を参照。
*2 -m (mod m(m+2) )とは, m(m+2)で割った余りが-mであることである。詳しくは合同式で検索!