아직 모르는게 너무 많아!

# n | a
  - a는 n의 배수이다.
 
# a mod n
  - a를 n으로 나누었을 때 나머지 값
 
# a ≡ b mod n
  - a와 b는 n으로 나누었을 때 그 나머지가 같다. (a와 b는 합동이다)
 
# 모듈러 연산의 특성
  - a ≡ b mod n 이면, a - b는 n의 배수이다. -> (a - b) mod n = 0
  - mod n = Zn = { 0, 1, ..., n - 1 }
 
# 모듈러 연산 법칙
  - [(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) x (b mod n)] mod n = (a x b) mod n
 
# Galois Fields - GF(p) [아직 명확히 이해 못함. 위수가 단순히 원소의 개수인 것인지... 유한체는 뭔지...]
  - 소수 p에 대하여 위수가 p인 유한체
  - GF(p)는 정수 { 0, 1, ..., p-1 }의 집합 Zp로 정의
  - p가 소수이므로 Zn상의 모든 정수들에 대해 곱셈의 역원이 존재함

회사에서 세미나하는 내용인데 번개같이 넘어가는 바람에 뭔말인지 모르겠어요. ㅋㅋㅋ
이해도 할겸 복습하며 예문 위주로 정리합니다.
내가 이해한대로 정리한거라 틀릴수도 있으니 책임은 못 집니다.

# GCD(a, b) : a와 b의 최대 공약수 (Gratest Common Divisor)
ex) GCD(49, 21) = 7

# 서로소 : GCD(a, b) = 1 인 정수 a와 b를 서로소라 한다
ex) GCD(5, 7) = 1
ex) GCD(6, 11) = 1
ex) GCD(10, 21) = 1

# 소수 : 1 과 자신만으로 나누어지는 1보다 큰 양의 정수
ex) 2, 3, 5, 7, 11, 13, ...

# 합성수 : 소수가 아닌 양의 정수 (1과 자신 이외에 다른 값으로 나누어지는 자연수)
ex) 4, 6, 8, 9, 10, 12, 14, 15, ...

# 모든 정수(n > 1)는 소수의 곱만으로 표현할 수 있으며, 순서를 무시한다면 그 표현방법은 유일하다.
ex) 15 = 3 x 5
ex) 50 = 2 x 25 = 2 x 5 x 5
ex) 100 = 2 x 50 = 2 x 2 x 5 x 5

# 유클리드 알고리즘 : a = bq + r 이면 GCD(a, b) = GCD(b, r)
ex) 49 = 28 x 1 + 21 -> GCD(49, 28) = GCD(28, 21)
ex) 54 = 14 x 3 + 12 -> GCD(54, 14) = GCD(14, 12)
~ a를 b로 나눈 나머지(r)는 항상 최대 공약수의 배수이다. 따라서 b와 r의 최대공약수도 동일하다.

# 유클리드 호제법(互除法 : 번갈아가며 제거하는 방법)
- 유클리드 알고리즘을 반복적으로 적용하여 최대공약수를 구하는 방법
ex) 나머지가 0 이면 작은 값이 최대 공약수 

GCD(1020, 790)	1020 = 1 x 790 + 230
GCD(790, 230)	790 = 3 x 230 + 100
GCD(230, 100)	230 = 2 x 100 + 30
GCD(100, 30)	100 = 3 x 30 + 10
GCD(30, 10)	30 = 3 x 10 + 0

# 베주의 정의 (bezout's identity)
- 동시에 0이 아닌 두 정수 a, b에 대해서 GCD(a, b) = ax + by를 만족하는 정수 x, y가 존재한다.

# 확장 유클리드 알고리즘 : 베주의 정의 GCD(a, b) = ax + by의 해(x, y)를 구하는 방법
- 위 유클리드 호제법 풀이의 나머지 값 외에는 a, b를 대입할 수 있다.
- 이를 이용해 나머지가 최소공약수가 될 때 까지 나머지를 a와 b로 표현하는 방식으로 정리한다.
ex) 위 유클리드 호제법을 사용한 예제. 위 호제법 풀이의 오른쪽 풀어놓은 식에 대입
1020 = 1 x 790 + 230 (위 유클리드 호제법의 풀이에서 가져온 식)
-> a = 1 x b + 230 ^[각주:1]
-> 230 = a - (1 x b) = a - b ^[각주:2]
-> 따라서, 230 = a - b
790 = 3 x 230 + 100 (위 유클리드 호제법의 풀이에서 가져온 식)
-> b = 3 x (a - b) + 100 ^[각주:3]
-> 100 = b - (3 x (a - b)) = b - (3a - 3b) = -3a + 4b ^[각주:4]
-> 따라서, 100 = -3a + 4b
230 = 2 x 100 + 30 (위 유클리드 호제법의 풀이에서 가져온 식)
-> a - b = 2 x (-3a + 4b) + 30 ^[각주:5]
-> 30 = a - b - (2 x (-3a + 4b) = a - b - (-6a + 8b) = 7a - 9b ^[각주:6]
-> 따라서, 30 = 7a - 9b
100 = 3 x 30 + 10 (위 유클리드 호제법의 풀이에서 가져온 식)
-> -3a + 4b = 3 x (7a - 9b) + 10 ^[각주:7]
-> 10 = -3a + 4b - (3 x (7a -9b)) = -3a + 4b - (21a - 27b) = -24a + 31b ^[각주:8]
-> 따라서, 10 = -24a + 31b

10 은 GCD(1020, 790)의 해, 즉 최대공약수이므로 a와 b에 원래의 값을 대입하면
-> GCD(1020, 790) = -24 x 1020 + 31 x 790
-> a = 1020, b = 790 일 경우 GCD(a, b) = ax + by 를 만족하는 x와 y는
※ x = -24, y = 31

확인 : 1020 x -24 + 790 x 31 = -24480 + 24490 = 10