合同式 (Congruence)

ａ≡ｂ (mod　ｍ)
読み方	mを法としてaとbが合同
意味	a-bはmで割り切れる。
性質	a,b,c,dを整数、kを自然数とするとき、 １．　ａ≡ｂ (mod　ｍ)かつ　ｃ≡ｄ (mod　ｍ)　なら 　　ａ＋ｃ≡ｂ＋ｄ(mod　ｍ)　　 　　ａ−ｃ≡ｂ−ｄ　(mod　ｍ)　 　　ａｃ≡ｂｄ (mod　ｍ) 　　−ａ≡−ｂ (mod　ｍ)　 　　 kａ≡kｂ (mod　ｍ) ２．　ｋａ≡ｋｂ (mod　ｍ)のとき 　(k,m) = 1 (ｋとｍが互いに素)ならば 　　　　ａ≡ｂ (mod　ｍ)

　

剰余類（合同類）	n で割って i 余る数を 　( i : mod n)　　( i = ０、１、２、３、…、n-1) 　とあらわし、mod n に関する i の剰余類（合同類）といいます。
既約類	特に( i,n ) = 1のとき mod n の既約類といいます。

例）　mod 7 に関する i の剰余類

( 0 : mod 7) = {…、-14 、-7 、0、7、14、…}

( 1 : mod 7) = {…、-13 、-6 、1、8、15、…}

( 2 : mod 7) = {…、-12 、-5 、2、9、16、…}

( 3 : mod 7) = {…、-11 、-4 、3、10、17、…}

( 4 : mod 7) = {…、-10 、-3 、4、11、18、…}

( 5 : mod 7) = {…、-9 、-2 、5、12、19、…}

( 6 : mod 7) = {…、-8 、-1 、6、13、20、…}

完全剰余系	任意の自然数が、 　集合A{ ai ｜i = 1、2、3、…、n} 　のうちの一つと( mod n )に関して合同であるとき、集合Aを 　( mod n )に関する完全剰余系といいます。
既約剰余系	( mod n )に関する完全剰余系Aの中で、n と互いに素な数全体の集合を 　( mod n )に関する既約剰余系といいます。

＜多項式の合同＞

f (x)、g (x) を整数係数の多項式とします。f (x)、g (x) それぞれの x のべきの係数が ( mod n )に関してすべて合同なら、f (x)、g (x) は ( mod n ) において多項式として合同といいます。

f (x) ≡ g (x) ( mod n )

とあらわします。

たとえば、

(7x² + 5x + 8) ≡ (3x² - 3x + 4) ( mod 4 )

となります。

＜位数＞

(a,n) = 1 で、

a^b ≡ 1 ( mod n )

を満たす最小の自然数 b を a の ( mod n ) の位数といい、

b = ordn(a)

とかく。

たとえば、

3¹ ≡ 3 ( mod 4 )、3² ≡ 1 ( mod 4 ) より、

2 = ord₄(3)

位数に関する定理

(a,n) = 1 なら、 ab ≡ 1 ( mod n )　⇔　ordn(a)|b 　特に、ordn(a)|φ(n) である。

＜原始根＞

方程式、

x⁴ = 1

の解を考えてみましょう。

x = e^2πik/4 ( k = 0、1、2、3 )

= 1、i、-1、-i

この４つの解の中で、i と　-i は４乗して初めて１になります。このような解を原始４乗根といいます。このような方程式における原始根は合同式では次のようにあらわされます。

a を p-1 乗して初めて

a^p-1 ≡ 1 ( mod p )

となるとき、a は ( mod p ) における原始根といいます。また、上の式は次のようにもあらわすこともできます。

a^φ(p) ≡ 1 ( mod p )

＜示数 ( index ) ＞

g^b ≡ a ( mod p )

のとき、

b ≡ Indg(a) ( mod p-1 )

と書き、”b は g を 底とする a の示数”といいます。

示数に関する定理

(i)　Indg(a1・a2) ≡ Indg(a1) + Indg(a2) ( mod p-1 ) (ii)　Indg(ak) ≡ k Indg(a) ( mod p-1 )

（i の証明）

Ind_g(a1・a2) ≡ x₁、Ind_g(a₁) ≡ x₂、Ind_g(a₂) ≡ x₃ ( mod p-1 )

とおくと、これらは定義より、

g^x1 ≡ a₁a₂ 、g^x2 ≡ a₁ 、g^x3 ≡ a₂ ( mod p )

なので、

g^x2g^x3 = g^x2+x3 ≡ a₁a₂ = g^x1 ( mod p )

∴x₁ ≡ x₂ +x₃ ( mod p-1 )

∴Ind_g(a1・a2) ≡ Ind_g(a₁) + Ind_g(a₂) ( mod p-1 )

（証明終）

　合同式 (Congruence)