For a better world

가우스 소거법을 이용하여 연립 방정식의 해를 구하는 과정이며, 아래에서 $R_2$는 2열을 의미한다.

Reference

[1] http://blog.naver.com/PostView.nhn?blogId=alwaysneoi&logNo=100194836897

개요

중국인의 나머지 정리의 경우 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이며 그 기원은 다음과 같다.

중국의 5세기 문헌인 『손자산경(孫子算經)』에는 다음과 같은 문제가 있다고 한다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

정의

$gcd(n,m) = 1$면 $\begin {cases} x \equiv b\ (mod\ n) \\ x \equiv c\ (mod\ m) \end {cases}$는 $1 \leq x \leq nm$에서 단 하나의 해를 갖는다.

증명

$x \equiv b\ (mod\ n)$    (1)

$x \equiv c\ (mod\ m)$    (2)

$x \equiv b\ (mod\ n)$이므로 $x = ny + b$를 만족하는 $y \in Z$가 존재할 것이고, 이를 (2)에 대입하면 다음과 같다.

$ny \equiv c -b\ (mod\ m)$

위 정의에 의해 위 합동식은 $1 \leq y \leq m$에서 유일한 해 $y_0$를 갖고, 따라서 $x = ny_0 + b$는 $1 \leq x \leq nm$에서 유일한 해 $x_0$를 가진다. 따라서 다음과 같다.

$x_0 = ny_0 + b$

여기서 $x_0$는 (1)의 해다. 이제 $ny_0 \equiv c -b\ (mod\ m)$에 $ny_0 = x_0 - b$를 대입하면 다음과 같다.

$x_0 \equiv c\ (mod\ m)$

$x_0$은 (2)의 해가 된다. 증명 끝.

Reference

[1] https://namu.wiki/w/중국인의%0나머지%0정리 

[2] https://freshrimpsushi.tistory.com/493

군, 환, 체의 경우 대수학에서 사용되는 개념으로 기본적이면서 가장 중요한 개념으로 여겨진다.

군 환 체 정의

군

공집합이 아닌 집합 G 위에 다음 세 조건을 만족하는 이상연산 $\circ$가 정의될 때 $<G, \circ>$를 군이라 한다.

군의 공리

• 결합법칙 : $G$의 임의의 원소 $a, b, c$에 대해 다음이 성립한다.
  • $(a \circ b)\ \circ \ c\ =\ a\ \circ \ (b \circ c)$

• 항등원 : $G$의 모든 원소 $a$에 대해 다음이 성립하는 $e \in G$가 존재해야하며, 이 때 $e$를 $G$의 단위원 또는 항등원이라한다.
  • $a \circ e\ =\ e\circ a = a$

• 역원 : $G$의 각 원소 $a$에 대해 다음이 성립하는 $a^{-1}이 $G$에 존재해야 하며, 이 때 $a^{-1}$를 $a$의 역원이라한다.
  
  • $a \circ a^{-1} = a^{-1} \circ a = e$

• 닫힘 : 어떤 집합의 임의의 두 원소(순서쌍)간에 연산이 행해질 때, 그 결과 역시 그 집합의 원소가 되는 것을 의미한다.
  • $a \circ b$ 연산의 결과도 집합 $G$에 속하며 순서쌍 $(a,b)$들의 곱(카테시안 곱) 연산에 대해 닫혀있음

군은 결합법칙, 항등원, 역원, 닫힘의 네 가지 특성을 가지고 있어야 한다.

군의 종류

• 가환군 or 아벨군
  • 군의 네 가지 특성에 추가적으로 교환법칙까지 성립할 경우 이를 아벨군(abelian group) 또는 가환군(commutative group)이라 한다.

• 순환군(Cyclic Group)
  
  • 한 원소로 군의 모든 원소를 표시할 수 있는 군을 의미하며, 이 때 해당 원소를 생성원(generator)라 한다.

• 덧셈군(Additive Group)
  
  • 군의 이항 연산이 덧셈 연산인 군

• 곱셉군(Muliplicative Group)
  
  • 군의 이항 연산이 곱셈 연산인 군

• 부분군(Subgroup)
  • 군 $G$의 부분집합으로 군 $G$와 같은 연산 구조를 가지는 군

군의 표기

• $(G, \circ)$ 또는 $<G, $circ>$ 또는 ${G, \circ}$
  • $G$: 군의 원소 집합
  • $\circ$ : 군의 연산
• 군의 차수/위수(order): $|G|$ 또는 $O(g)$ 또는 $G_n$ 또는 $ord(G)$로 나타낼 수 있다.

환

어떤집합 R 및 그 집합 위에 2개의 이항연산$(+, \circ)$이 정의되는 대수 구조를 의미하며 다음과 같이 표기한다.

• $(R, +, \circ)$ 또는 $< R, +, \circ>$ 또는 $환 R$

환의 공리

• 덧셈 연산에 대해 : $(R, +)$는 가환군
  • 닫혀 있음
  • 항등원(`0`)이 존재 $\rightarrow a + 0 = 0 + a = a$
• 각 성분에 대해 역원이 존재함$\rightarrow a + (-a) = (-a) + a = 0$

• 모든 성분에 대해 교환법칙이 성립 $\rightarrow a + b = b + a$

• 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a + b) + c = a + (b + c)$

• 곱셈(\circ) 연산에 대해 : $(R, \circ)$
  • 닫혀 있음
  • 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a\circ b)\circ c = a\circ (b\circ c)$
• 덧셈 및 곱셉 연산에 대해 : $(R, +, \circ)$
  • 모든 성분에 대해 분배법칙이 성립 $\rightarrow a\circ (b + c) = a\circ b + a\circ c, (a + b)\circ c = a\circ c + b\circ c$

추가적인 조건에 따른 환의 종류

• 가환환
  • 추가적으로 곱셈(\circ)에 대해서 가환이 되는 환 : $a \circ b = b \circ a)$

• 단위원을 갖는 환(Ring with Unity)
  • 추가적으로 곱셈 항등원 즉, 단위원을 갖는 환 : $1 \circ a = a \circ 1 = a$

• 나눗셈환
  • 단위원 1을 갖는 환으로써, 곱셈 역원이 존재하는 환 : 각 원소 $a \in R, a \neq 0$에 대해, $a \circ a^{-1} = a^{-1}\circ a = 1$

• 정역(Integraldomain)
  • 단위원 1을 갖는 가환환으로써, 추가적으로 다음 조건을 만족
    • $a \neq 0, b \neq 0$이면 $a \circ b \neq 0$을 만족함 또는
    • $a \circ b = 0$이면, $a = 0$ 또는 $b = 0$ $(a,b \in R)$

체

• 코드(부호) 등을 기술하는데 사용될 수 있는 수학적 대수 구조
  • 예) 실수 $R$, 유리수 $Q$, 복소수 $C$와 같은 수 체계에 대한 추상화
• 특정한 성질을 만족하는 2개의 연산이 정의되는 가환환
  • 그 요소들이 집합을 이루면서, 덧셈과 곱셈 연산 두 쌍을 사용할 수 있는 구조(2개 산술연산자)

체의 공리

• 덧셈 연산에 대해 : $<F, +>
  • 집합 내 원소의 연산 결과가 다시 그집합 내에 있게된다. $\rightarrow\ 닫혀있음
  • 항등원 (`0`)이 존재 : $a + 0 = a = 0 + a$
  • 모든 성분에 대해 덧셈 역원이 존재 : $a + (-a) = 0 = (-a) + a$
  • 모든 성분에 대해 결합법칙이 성립 : $(a + b) + c = a + (b + c)$
  • 모든 성분에 대해 교환법칙이 성립 : $a + b = b +a$
• 곱셈 연산에 대해 : $<F, \circ>$
  • 모든 성분에 대해 분배법칙이 성립 : $a (b +c) = a b + a c$

위 체의 공리에서 덧셈 공리들 만을 만족할 경우는 아벨군 또는 가환군이며, 곱셈의 역원 존재 만을 제외한 나머지 공리들을 만족하는 경우는 환이다.

체의 공리가 성립하는 예제

• 실수체 : 실수 전체의 집합
• 복소수체 : 복소수 전체의 집합
• 유리수체 : 유리수 전체의 집합

유한개의 원소를 갖는 체 $\rightarrow$ 유한체(갈로이스체)

Reference

[1] https://booolean.tistory.com/300

확장 유클리드 알고리즘

$x, y$에 대한 부정방정식 $ax + by = c$는 $c$의 값이 $gcd(a,b)$의 배수일 때만 정수 해를 가진다 알려져있다. 즉, $ax + by = c$가 정수 해를 가지는 $c$의 최솟값이 $gcd(a,b)$가 되는 것이다. 따라서 확장 유클리드 알고리즘은 $a,b$의 최대공약수를 구하는 것에 더 나아가, $ax + by = gcd(a,b)$를 만족하는 정수 해 $x,y$도 구하는 알고리즘이라할 수 있다. 즉, 다음과 같다.

• 확장 유클리드 호제법을 이용하면 $ax + by = gcd(a,b)$의 해가 되는 정수 $x, y$ 짝을 찾아낼 수 있다. 특히 $a,b$가 서로소$(gcd(a,b)=1)$인 경우 유용한데, 이와 같을 경우 $ax + by = 1$이 되고, 여기서 a는 모듈러 연산의 곱의 역원이 되기 때문이다.

유클리드 확장 알고리즘 증명

유클리드 확장 알고리즘 증명에 앞서 먼저 유클리드 알고리즘은 다음과 같다.

두 양의 정수 a,b의 최대공약수 $gcd(a,b)$는 다음과 같은 절차를 거쳐 구할 수 있다.

$r_0 ← a$

$r_1 ← b$

$r_{i+1} = r_{i-1} - q_i r_i$

$q_i = r_{i-1} \div r_i$

만약 $r_{i+1} = 0$이라면, $r_i$가 바로 $gcd(a,b)$이다.

확장 유클리드 알고리즘의 경우 최대공약수 이외에도 다음을 만족하는 두 개의 정수 $s, t$를 추가로 구할 수 있다.

$sa + tb = gcd(a,b)$

초기 조건은 다음과 같다.

$s_1 = 1,\ s_2 = 0$

$t_1 = 0,\ t_2 = 1$

$r_1 = a,\ r_2 = b$

$as_i + bt_i = r_i\ \ for\ i = 0,1$

초기 조건을 대입하여 확인할 수 있으며, $i >$ 1일 때 참이라 가정하고 수학적 귀납법을 사용하면 다음과 같다.

$r_{i+1} = r_{i-1} -r_iq_i$

$= (as_{i-1} + bt_{i-1}) - (as_i+bt_i)q_i$

$= a(s_{i-1}-s_iq_i)+b(t_{i-1}-t_iq_i)$

$= as_{i+1}+bt_{i+1}$

따라서 $r_{i+1} = 0$일 때, $as_i + bt_i = r_i$는 $sa + tb = gcd(a,b)$가 된다.

모듈러 연산에서 곱셈에 대한 역원 구하기

법 $m$에 대한 모듈러 연산에서 정수 $a$의 곱셈에 대한 역원 $a^{-1}$은 다음을 만족하는 정수 $x$로 정의한다.

$ax \equiv 1\ (mod\ m)$

모듈러 연산의 정의에 의해 $ax - 1 = -my$를 만족하는 정수 $y$가 존재해야하며 이는 다시 말해 다음을 만족하는 정수$x, y$가 존재해야 한다는 의미이다.

$ax + my = 1$

$a$와 $m$의 최대공약수가 1, 즉 서로소이면 해가 존재하고 그렇지 않을 경우 $a^{-1}$은 존재하지 않는다.

그렇다면... (추가 기술 필요)

확장 유클리드 알고리즘 의사코드

#1

function extended_gcd(a, b)
    s <- 0;    old_s <- 1
    t <- 1;    old_t <- 0
    r <- b;    old_r <- a
    while r ≠ 0
        quotient <- old_r div r
        (old_r, r) <- (r, old_r - quotient * r)
        (old_s, s) <- (s, old_s - quotient * s)
        (old_t, t) <- (t, old_t - quotient * t)       
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

#2

// 초기화
r1 ← a, r2 ← b

s1 ← 1, s2 ← 0

t1 ← 0, t2 ← 1



// 루프
while(r2 > 0)
{
　q ← r1 / r2

　r ← r1 - q*r2
　r1 ← r2
　r2 ← r

　s ← s1 - q*s2
　s1 ← s2
　s2 ← s

　t ← t1 - q*t2
　t1 ← t2
　t2 ← t
}

Reference

[1] https://codepractice.tistory.com/79?category=885924

[2] https://brilliant.org/wiki/extended-euclidean-algorithm/

[3] https://ko.wikipedia.org/wiki/유클리드_호제법

[4] https://codeonwort.tistory.com/295

[5] https://joonas.tistory.com/25

[6] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

정의

유클리드 호제법이란 두 정수 사이에 최대공약수(GCD)를 보다 효과적으로 구하는 것으로, 인류 최초의 알고리즘이라 한다. 

두 개 자연수 $A, B$가 있고 $A\ \%\ B = r$이면 다음과 같다. (단, $A > B$)

$GCD(A,B) = GCD(B,r)$

이 때, $A\ \%\ B = r$에 의해 다음과 같은 식이 기본적으로 유도된다.

$A = Bq + r$

증명

두 자연수 $A,B (A > B)$의 최대공약수를 $G$라 하자. $G$는 공약수이므로 두 서로소 $a, b$에 대해 다음 식이 성립한다.

$A = aG, B = bG$

위의 식을 사용하여 $A = Bq + r$에 대입하면 다음과 같다.

$aG = bGq + r$

$r = aG - bGq$

$ r = (a - bq)G$

$A = aG, B = bG$에서 $a, b$가 서로소라면 $G$가 최대공약수이기 때문에 $b, a - bq$가 서로소임을 증명하면 된다.

이를 증명하기 위해서는 가정에 모순을 확인하는 귀류법을 사용하여 해결할 수 있다.

$b$와 $a - bq$가 서로소가 아니라면 두 수는 공약수 $k$를 가지기 때문에 다음과 같이 나타낼 수 있다.

$a - bq = mk$

$b = nk$

위 식의 항을 옮기고 대입하여 정리하는 과정은 다음과 같다.

$a = mk + bq$

$a = mk + nkq$

$a = (m+nq)k$

따라서 다음과 같은 식을 확인할 수 있다.

$a = (m+nq)k$

$b = nk$

하지만 $a$와 $b$는 서로소이나 공약수 $k$를 가지므로 거짓 명제이다.

따라서 $a-bq$와 $b$는 서로소이다.

Reference

[1] https://baeharam.github.io/posts/algorithm/extended-euclidean/

잉여류

잉여류는 정수 $a$와 법 $m$에 대해 합동인 모든 정수의 집합이다.

예를 들어 7을 5로 나누면 2가 남으며 이러한 수는 7, 12, 17, 22, $\dots$가 될 수 있다.

이를 법 5에 ~대한 7의 잉여류/합동류라 표현할 수 있다.

합동의 정의

• 정수론에서는 합동을 $a, b$를 $m$으로 나눈 나머지가 같을 때, $a$와 $b$가 법$(modulo)\ m$에 관하여 합동 (Congruence)이라고 하고, $a \equiv b(mod\ m)$으로 나타낸다.

• 두 정수 $a,b$에 대해서 $a-b$가 $m$의 배수일 때,  $a$와 $b$는 $m$을 법으로 합동(Congruent modulo m)이라한다.

합동의 기본 성질

$a\equiv b(mod\ m)$이고, $c\equiv d(mod\ m)$이면, 다음과 같다.

1. $a + c \equiv b + d(mod\ m)$
2. $ac \equiv bd(mod\ m)$
3. $a^n \equiv b^n(mod\ m)$

기약 잉여계와 완전 잉여계의 정의

• 기약 잉여계
  • $\{a_1, a_2, \dots , a_m \}$가 법 $m$에 대한 완전 잉여계일 때, 여기서 $m$과 서로소인 원소만 모은 집합을 법 $m$에 대한 기약잉여계라 한다.

• 완전 잉여계
  • $\{a_1, a_2, \dots , a_m \}$에서 $a \equiv a_i \pmod{m}$인 $a_i$가 유일하게 있을 때, $\{a_1, a_2, \dots , a_m \}$ 를 완전잉여계라고 한다.

기약 잉여계와 완전 잉여계의 예시

$4$를 예시로 들면, $\{0, 1, 2, 3\}$은 완전잉여계, 그리고 $4$와 서로소가 아닌 $0, 2$를 제외한 $\{1, 3\}$는 기약잉여계가 된다. 기약잉여계가 중요한 이유는, 곱셈의 역원이 있다는 점 때문이다. 예컨대, 6에 대한 완전잉여계 $\{0, 1, 2, 3, 4, 5\}$와 그것의 기약잉여계 $\{1, 5\}$를 생각하자. $\{1, 5\}$의 원소는 모두 곱셈 역원을 갖는다. 그러나, 다른 완전잉여계 원소는 그렇지 않다. 이는, $m$과 $a$가 서로소일 때, 정수 $x,y$가 존재하여 $ax + my = 1$ 즉, $ax \equiv \ 1(m)$이기 때문이다.

역원의 정의

집합 $S$와 이항연산자 *에 대해, 만약 항등원 e가 존재한다고 할 때, S의 원소 a에 대해

$a * b = b * a = e$를 만족하는 $S$의 원소 b가 유일하게 존재할 때, b를 a의 역원이라고 한다.

오일러 정의

기약 잉여계 개념은 정수론에서 오일러의 정의를 증명하는 데 사용된다. 정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.

• $a$와 $n$이 서로소인 양의 정수일 때, $a^{\varphi(n)} \equiv 1(mod\ n)$이다.
  • 여기서 $\varphi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 개수이다. 오일러 피 함수라고도 불린다.

• 양의 정수 $m$에 대하여, $m$ 이하의 자연수 중에서 $m$과 서로소인 정수의 개수를 $\varphi (m)$으로 나타내고 함수 $\varphi : Z→N$ 를 오일러의 $\varphi$ 함수라고 한다.
  
  • $\varphi$ = varphi

또한 오일러 정리는 대표적인 공개키 암호화 방식 중 하나인 RSA의 가장 중요한 이론이 되는 정리이다.
참고로 오일러 공식, 오일러 방정식과는 다른 것이다.

페르마의 소정리

$p$가 소수일 때, $gcd(a, p)=1$인 정수 $a$에 대하여 $a^(p-1) \equiv 1(mod p)$이다.

증명:  오일러 정리에서 $n=p$대입하고, $\varphi (p)=p-1$ 이용하면 증명

Reference

[1] http://blog.naver.com/PostView.nhn?blogId=dlrbtjd86&logNo=113315940

[2] https://namu.wiki/w/기약잉여계

[3] https://schbeom.tistory.com/367

[4] https://minq.tistory.com/90

[5] https://thewiki.kr/w/오일러%20정리