既約剰余類群

数学 プログラミング Python

剰余類

まずは剰余類の説明からします。例えば15の剰余で考えます。2と17と32は15で割ると余りが2になります。これらは同じとみなして剰余類と呼びます。

H0 = { …, -15, 0, 15, 30, … }
H1 = { …, -14, 1, 16, 31, … }
H2 = { …, -13, 2, 17, 32, … }
…

-13を15で割ると余りは2とするとそれだけで分類できるので都合がよくなります。だからPythonの仕様はこうなっています。C++等で余り-13となっているのはその昔演算回路がそうなっていたのを未だに引きずっているだけの話です。
そうすると、加減乗が成り立ちます。例えば、H1とH2の積は、

H1 * H2 = { …, -14 * -13, -14 * 2, -13 * 1, 1 * 2, … }
= { …, 182, -28, -13, 2, … } = H2

となります。それぞれ代表元を1と2として

1 * 2 = 2

とするのと同じことです。

既約剰余類群

上の例なら15と既約の剰余類だけ並べます。3とか5とか6は可約なので、それを除いて代表元で表して並べると、

{ 1, 2, 4, 7, 8, 11, 13, 14 }

となります。これが乗法について群になっていることは、逆元の存在を確かめればあとは明らかでしょう。aの逆元は、

ab = 15k + 1

でaが15と互いに素だから、解が存在します。これが既約剰余類群です。

素数の法のときの生成元の判定法

以下、8 ≡ 1(mod 7)のような書き方は面倒なので、法が明らかな場合は8 = 1と書きます。
素数の法のとき、生成元があります。生成元とはその元のべき乗を並べると全ての元が現れるような元のことです。例えば7の法のとき、2は

2 -> 4 -> 8 = 1

だから周期3で生成元ではありませんが、3は

3 -> 9 = 2 -> 6 -> 18 = 4 -> 12 = 5 -> 15 = 1

だから周期6で生成元になっています。
今度は法61で考えてみましょう。生成元なら周期は60になるはずです。そして、各元の周期はこの約数になります。

1 2 3 4 5 6 10 12 15 20 30 60

よって、元aが

a60 = 1
ae ≠ 1 (eは60の真約数)

を満たすなら生成元です。
しかし、a20 ≠ 1ならa10 ≠ 1が成り立つことになりますよね。つまり全ての約数について調べる必要は無いということです。では、どの約数について調べればいいでしょうか。まず、60は調べる必要がありますよね。そして、60以外の真約数になっている数は調べる必要がありません。例えば上の10です。しかし、60以外の真約数になっていなければ調べる必要があります。これは60をそれぞれの素因数で割った数です。素因数は2と3と5ですから、30と20と12です。すなわち、

a60 = 1 a30 ≠ 1 a20 ≠ 1 a12 ≠ 1

がaが生成元である必要十分条件です。
コードもつけておきます。引数に生成元かチェックする元と法です。法の素数チェックはしていません。

from itertools import *
import sys

def factorize(n):
	def f(n, p0):
		if n == 1:
			return ()
		
		for p in takewhile(lambda p: p * p <= n, count(p0)):
			if n % p == 0:
				return (p,) + f(n / p, p)
		else:
			return (n,)
	
	return list((k, len(list(v))) for k, v in groupby(f(n, 2)))

def is_generator(n, d):
	ps = [ p for p, e in factorize(d - 1) ]
	return (pow(n, d - 1, d) == 1 and
				all(pow(n, (d - 1) / p, d) != 1 for p in ps))

def pows_mod(n, d):
	m = 1
	while True:
		yield m
		m = m * n % d

def is_generator_naive(n, d):
	m = next(k for k, m in islice(enumerate(pows_mod(n, d)), 1, None) if m == 1)
	return m == d - 1

if len(sys.argv) != 3:
	exit()
n = int(sys.argv[1])
d = int(sys.argv[2])
print is_generator(n, d)
print is_generator_naive(n, d)

素数の法のときの周期の分布

例えば法が7のとき、各元の周期は、

1 2 3 4 5 6
1 3 6 3 6 2

となります。周期1は1個、周期2は1個、周期3は2個、周期6は2個です。
これは、整数の剰余の加算に対する群と同型だという事実を使うと簡単にわかります。すなわち、6を法とした0〜5の剰余類からなる群を考えます。先ほどの法が7の既約剰余類群で3が生成元なので、3eをeと対応させればよいことがすぐにわかります。

1 3 2 6 4 5
0 1 2 3 4 5

上の乗法が下の加法に対応しています。例えば、2 * 6 = 12 = 5と2 + 3 = 5です。
さて、下の加法のほうは、周期1が0、周期2が3、周期3が2と4、周期6が1と5となります。もうちょっと難しくして、法61の既約剰余類群の周期20の元の個数を求めたいとします。法60の加算剰余類群と同型だから、20a = 0となる元aは20個あります。しかし、その中には4a = 0となる元が4個、10a = 0となる元が10個あり、さらに両方に含まれる2a = 0となる元が2個あるので、20 - 4 - 10 + 2 = 8個あることになります。

Project Eulerに必要な用語集