Division Algorithm
a/b가 나머지를 가지지 않을 때 b는 a의 약수이고 b|a 라고 나타낸다.
만약 a/n이 몫 q와 나머지 r을 가진다면 다음 식으로 표현할 수 있는데 이것을 division algorithm 이라고 부른다.
a = q * n + r ( 0 ≤ r ＜ n, q = [a/n] )
Euclidean algorithm (유클리드 호제법)
유클리드 호제법은 두 양수의 최대공약수(GCD)를 구할 때 쓰이고, 정수론의 가장 기본적인 알고리즘에 속한다.
최대공약수가 1인 두 수의 관계를 relatively prime(서로소) 이라고 부른다.
유클리드 호제법에서는 최대공약수를 구하기 위해 나머지를 이용한다.
나눠지는 수를 a, 나누는 수를 b라고 할 때 b는 다음 계산식의 a가 되고, r은 다음 계산식의 b가 된다.
이런 식으로 계산을 반복해서 r=0을 만족하는 순간의 b값이 두 수의 GCD이다.
유클리드 호제법의 전제조건은 a=b*q+r일 때 gcd(a, b)=gcd(b, r)이 성립한다는 점이다.
증명
- G|b && G|r
gcd(a, b)를 G라고 하자. 그러면 G|a이고 G|b이다.
이 경우 G|a*m+b*n이 성립한다. 따라서 G|a-b*q이다.
그런데 r=a-b*q이므로 G|r이다. 따라서 G는 b와 r의 공약수이다.
- gcd(b, r) = G
b와 r의 공약수인 c가 존재한다고 생각해보자.
c|r이면 c|a-b*q인데, c|-b*q이므로 c|a도 성립한다. 그러면 c|a && c|b이다.
따라서 c는 a와 b의 공약수인데, G가 이미 a와 b의 최대공약수이므로 c <=G이다.
따라서 G는 모든 c에 대해 항상 크므로 gcd(b, r) = G가 성립한다.
따라서 gcd(a, b) = gcd(b, r) = gcd(r, r2) ... 를 계속하다보면 gcd(rn, 0)에 도착하는데 0은 모든 수를 약수로 가진다. 따라서 rn이 최대공약수이다.
Extended euclidean algorithm (확장 유클리드 호제법)
유클리드 호제법을 나열하면 다음과 같은 형태이다.
a = b*q0 + r1
b = r1*q1 + r2
r1 = r2*q2 + r3
...
r(i-1) = r(i)*q(i) + r(i+1)
임의의 r값에 대해 a의 계수를 s, b의 계수를 t로 정의하여 GCD를 구하는 알고리즘이 확장 유클리드 호제법이다.
EED의 초기값
s1 = 1, s2 = 0, t1 = 0, t2 = 1
s = s1 - q * s2
t = t1 - q * t2
r2=0이 되는 순간의 r1값이 GCD이다. 달리 말하면 r=0이 될 때 r2값이 GCD이다.
Modular arithmetic
a가 정수이고 n이 양의 정수라고 할 때, a mod n은 a/n의 나머지이다.
이 때 정수 n을 modular 라고 한다.
{(a mod n) + (b mod n)} mod n = (a + b) mod n
{(a mod n) - (b mod n)} mod n = (a - b) mod n
{(a mod n) × (b mod n)} mod n = (a × b) mod n
modular 연산에서는 교환법칙, 결합법칙, 분배법칙이 성립한다.
항등원과 역원
항등원, 역원
연산을 거쳐서 자기 자신이 나오게 하는 식을 항등원, 항등원이 나오게 하는 식을 역원이라고 한다.
항등원과 역원은 항상 연산 기호에 dependency가 있다.
예를 들어 덧셈에 대한 항등원은 0이지만 곱셈에 대한 항등원은 1이다.
또한 역원이 항상 존재하는 것은 아니다. 예를 들어 정수 체계에서 정수 n의 역원은 존재하지 않는다.
이것을 modular 수체계에 적용해보면 a와 n이 서로소일 때만 a mod n의 역원을 찾을 수 있다.
p = a mod n이라고 할 때 p=nk+a
nk+a의 역원은 a가 n과 서로소일 때만 발생한다. 왜냐하면 n|a인 경우 a mod n = 0이고 0의 역원은 존재하지 않기 때문이다
0의 곱셈에 대한 항등원이 너무 많아서인지??
페르마 소정리
소수 p와 양의 정수 a가 서로소일 때, a의 (p-1)제곱을 p로 나누면 나머지가 1이다.
a^(p-1) = 1 (mod p)
오일러 피 함수
φ(n) = n(m)
n보다 작고 n과 서로소인 m의 개수를 구하는 함수이다.
