忘れっぽい数学。整数論
忘れっぽくて何度も調べなおして思い出す際にインターネットや本から検索するのがめんどくさいので、ここにあらかじめまとめておく。
整数論について。
ここでは厳密な数学上の定義を示しているわけではない。
基本的なとこ
ここでは何も注釈がない場合自然数は0を含まないこととする。
・法
・公約数
・最大公約数
・合同式
a,bを整数 nを自然数とするとき、a-bがnで割り切れるとき
aとbは法nをもとに合同であるという。
(a is congruent to b modulo n)
a≡b(mod n)
時計の世界を思い出すと考えやすい
a≡b(mod n) ⇔ a mod n = b mod n
任意の整数aについて、ある正整数 x ∈ {0,1,....,n-1}がただ一つ存在して、
a≡x(mod n)
次を同値関係という
(1)反射的,反射律
任意の整数aについて a≡a(mod n)
(2)対称的,対称律
任意の整数a,bについて
a≡b(mod n) ⇒ b≡a(mod n)
(3)推移的,推移律
任意の整数a,b,cについて
a≡b(mod n) かつ b≡c(mod n) ⇒ a≡c(mod n)
a,b,c,dを整数とするとき
a≡b(mod n) かつ c≡d(mod n)を満たすとき、
(1) a + c ≡ b + d (mod n)
(2) a - c ≡ b - d(mod n)
(3) a × c ≡ b × d (mod n)
剰余類と剰余系、剰余環
nで割った余り(剰余) r が(r = 0,1,2,....,n-2,n-1)であるような整数全体の集合をCrで表すと、整数の集合ZはC0,C1,C2,....,Cn-2,Cn-1のn個の部分集合に分類できる。この各部分集合をnを法とする剰余類とよぶ。
nZと表記する場合もある。
各剰余類をそれぞれ0,1,2,....,n-2,n-1で代表させたとき、その集合をZnと書き、mを法とする完全な代表の一組または剰余系とよぶ
(Z/nZと表してる人もいた。剰余環とかぶる)
例 7を法とする剰余系
{0,1,2,3,4,5,6}
{0,1,2,3,-3,-2,-1}
{7,-6,9,-4,-10,-9,13}
nを自然数とおき、nの倍数の集合nZ = {na | aは整数}(nを法とする剰余類)とし、Z/nZ = {0, 1 , ......, n-1}とする
この集合を剰余環と呼ぶ。
整数mに対して、法mに関するすべての剰余類を元とする集合を法mに関する剰余環と表す。Z/mZ
剰余系 Z/nZ上の演算
a,bがZ/nZの要素のとき、+n, -n, ×nは次のことを表す
(1)a +n bは整数Z上での(a + b) mod n
(2)a -n bは整数Z上での(a - b) mod n
(3)a ×n bは整数Z上での(a × b) mod n
またa^xはa ×n a ×n a ×n a ×n ...... ×n aを表す(x回)
nを自然数とし、a,b,c ∈ Z/nZとするとき次が成り立つ
(1) a +n b ∈ Z/nZ , a ×n b ∈ Z/nZ
(2)(a +n b) +n c = a +n (b +n c),
(a ×n b) ×n c = a ×n (b ×n c)
(結合法則)
(3)a +n b = b +n a, a ×n b = b ×n a
(交換法則)
(4)a +n 0 = a, a ×n 1 = a
(5)a ×n (b +n c) = a ×n b + a ×n c
（分配法則）
剰余系7Z(Z/nZ)上でのa=bは、Z上でのa≡b(mod n)と置き換えても良い
例 :
7Z(Z/7Z)上の3,10
3 = 10は 3 = 10(mod 7)と置き換えてもよい
整域
(integral domain)
任意の要素について、以下を満たす集合のことをいう。
ab = 0 ⇒ a = 0 または b = 0
整数集合Zが整域であることは、当たり前のように感じる。
Z/nZについて、必ずしも整域になるとは限らない。
pを素数とする。Z/pZは整域である
pを素数とする。このとき、(Z/pZ)* = Z/pZ \ {0}とおく。(\は差集合)
つまり、(Z/pZ)* = {1,2,3,.....,p-1}となる。
a ∈ (Z/pZ)*, b ∈ (Z/pZ)とする。このとき、次が成り立つ。
ab = 0 ならば b = 0
フェルマーの小定理
pを素数とする。このとき、(Z/pZ)* = Z/pZ \ {0}とおく。(\は差集合)
つまり、(Z/pZ)* = {1,2,3,.....,p-1}である。
(Z/pZ)*というのは群という概念で色々語れることがあるみたいだが、現状群についての知識が乏しいので、知識を得たら書き足すとする()
フェルマーの小定理
pを素数, a ∈ (Z/pZ)*とする。このとき、Z/pZ上で次が成り立つ
a^(p-1) = 1
(つまり、a^(p-1) = a ×p a ×p a ×p ....... ×p a [p-1回分])
Zと合同式を用いて言い直すと
a^(p-1) ≡ 1 (mod p)
a ∈ (Z/pZ)*とする。
関数fa : ∈ (Z/pZ)* ⇒ (Z/pZ)*を次で定義する。
任意のx ∈ (Z/pZ)* について
fa(x) = ax
この関数faは全単射である。
(faは (Z/pZ)* 上の元を並べているに過ぎない)
例 : p = 7とし、
a = 3としてみる。
f3(x) :
x = 1 ⇒ 3
x = 2 ⇒ 6
x = 3 ⇒ 9
x = 4 ⇒ 12
x = 5 ⇒ 15
x = 6 ⇒ 18
(Z/pZ)*を考えると (mod 7)
3 ⇒ 3
6 ⇒ 6
9 ⇒ 2
12 ⇒ 5
15 ⇒ 1
18 ⇒ 4
になり、(Z/pZ)*に全単射する。
オイラー関数
nを自然数、このとき(Z/nZ)*を次で定義する
(Z/nZ)* = {x ∈ Z/nZ | gcd(x,n) = 1}
(Z/nZ)*について次が成り立つ
(1)(Z/nZ)* ⊆ Z/nZ
(2)nが素数のとき、(Z/nZ)*は(Z/pZ)* と一致する
(3)任意のa,b ∈ (Z/nZ)*に対して、
ab ∈ (Z/nZ)*となる
a ∈ (Z/nZ)*, b ∈ Z/nZとする。このとき次が成り立つ
ab = 0 ならば b = 0
(Z/nZ)*上で考える関数fa
a ∈ (Z/nZ)*に対して、
fa : (Z/nZ)* ⇒ (Z/nZ)* を
fa(x) = axで定義する
この時関数faは全単射である
オイラー関数
(Z/nZ)*の個数をφ(n)で表す。
オイラー関数と呼ぶ
pを素数とする。このとき、φ(p) = p-1である。
p,qを素数とし、N = pqとする。このとき、
φ(N) = (p - 1)(q - 1)である
オイラーの定理
a ∈ (Z/nZ)∗とする。このとき、Z/nZ上で次が成り立つ。
a^φ(n) = 1
逆元
a ∈ (Z/nZ)∗とする。このとき、Z/nZ上で次を満たすとき、
ay = 1
y ∈ (Z/nZ)∗をaの逆元(inverse)という
nを自然数とおく、任意のa ∈ (Z/nZ)∗に対して、逆元が存在する
逆元について以下が成り立つ
a ∈ (Z/nZ)∗, 0 <= x <= p-1とする。
このとき、 a^xの逆元は a^(p-1-x)である
※フェルマーの小定理から証明できる。
a ∈ (Z/nZ)∗, 0 <= x < φ(n)とする。
このときa^xの逆元はa^(φ(n)-x)である
※オイラーの定理から証明できる
a ∈ (Z/nZ)∗とおく、このとき次は同値である。
Z/nZ上で ay = 1 を満たす y ∈ (Z/nZ)∗を求めること
Z上でnx + ay = 1を満たす y ∈ Zを求めること
拡張ユークリッド互除法
a,b ∈ Zとする。
ax + by = gcd(a,b)の解の組の1つを次のように求めることができる。
(1)
ユークリッド互除法により、gcd(a, b)を求めていく
a = b・q1 + r1
b = r1・q2 + r2
r1 = r2・q3 + r3
...
rk-3 = rk-2・qk-1 + rk-1
rk-2 = rk-1・qk + rk
rk-1 = rk・qk+1
ここでgcd(a, b) = rkである。
(2)
上の式をあまりに関する式に変換する、つまり移行して、riで始まる式にする
r1 = a - b・q1
r2 = b - r1・q1
r3 = r1 - r2・q3
....
rk = rk-2 - rk-1・qk
(3)
次のようにして、rk-2・x + rk-1・y = gcd(a, b)の解の組の1つを求める。
gcd(a, b) = rk = rk-2・1 + rk-1・(-qk)
⇒
rk-2・x + rk-1・y = gcd(a, b)の解の組一つは(1, - qk)である。
ここでi = k - 1とおく、
(4)
方程式 ri-1・x + ri・y = gcd(a, b)の解(x0, y0)と上記の式の中のriで始まる式を用いて、次のようにして
方程式 ri-2・x + ri-1・y = gcd(a, b)の解の1つを求める
(x0, y0)とriで始まる式を用いると次が求まる。
gcd(a, b) = ri-1・x0 + ri・y0
= ri-1・x0 + (ri-2 - ri-1・qi)・y0
= ri-2・y0 + ri-1・(x0 - qi・y0)
⇒ri-2・x + ri-1・y = gcd(a, b)の解の1つの解が(y0, x0 - qi・y0)である
i = i-1として次のようにする。
ただし、r-1 = a, r0 = bとする。
(5)
i = 0のとき ax + by = r-1・x + r0・y = gcd(a, b)の解がすでにも止まっているため終了。それ以外のとき(4),(5)を繰り返す
この記事が気に入ったらサポートをしてみませんか？