[이산수학] Contruence Modulo n, Equivalence Class, Bezout's Identity

Contruence Modulo n (모듈로 합동)

정의

• n이 1보다 큰 자연수이고, 정수 집합에 속하는 a, b에 대해 n이 a-b를 나누면 (n|(a-b)) 즉, $a = b + kn$ 이면 a 와 b가 모듈로 합동이다.
• $ a \equiv b (mod n) $ 이라고 쓴다.
• ex) $ 17 \equiv 2 (mod 5) $  17 = 2 + 3 X 5

정리1

모듈로 합동은 정수 집합 $Z$ 위에서 equivalence relation(동치관계)이다.

 

 

Equivalence Classes

• Equivalence relation은 어떤 집합을 분할할 수 있다.
• $n$ 이 2 이상인 경우 정수집합 $Z$ 를 n개의 equivalence class로 나눌 수 있다.
  • ex) n = 6 일 때, 7과 1은 나머지 1에 대해서 equivalence class 라고 한다.

 

$Z_n$ : 모듈러 연산 집합

• n으로 나눈 나머지를 기준으로 분류된 집합
• $Z_n = \{ [0], [1], ... , [n -1] \}$
• 닫혀 있는 두 연산이 정의 된다. $( +, \cdot  )$
  • $[a] + [b] = [a+b] $
  • $[a] \cdot [b] = [a][b] = [ab]$
  • ex) n = 7에 대해서, [2] + [6] =  [2+6] = [8] = [1], [2][6] = [12] = [5]

$Z_n$ 은 Field인가?

정리2

n이 1보다 큰 자연수일 때 두 가지 닫힌 연산 $(+, \cdot )$ 에서 $Z_n$은 Commutative Ring with Unity 이다.

• [1] : 곱셈의 단위원
• [0] : 덧셈의 항등원

$<Z_{{\color{Red} 5}},+,\cdot>$은 Field 이다.  -> 곱하기에 대해서 역원이 존재하기 때문에

모든 원소에 항등원이 되는 값이 존재한다. => 역원

• + 에 대해서 2의 역원은 3
• $\cdot$ 에 대해서 2의 역원은 3

$<Z_{{\color{Red} 6}},+,\cdot>$ 은 Field가 아니다. 

2, 3, 4는 항등원을 만드는 값이 존재하지 않는다. => 역원이 없다.

여기서 2, 3, 4는 연산 시 0이 나오는 경우가 있다. 

어떤 두 원소 a와 b가 0이 아닐 때,$a \cdot b = 0$이 되는 경우, a나 b는 Zero Divisor라고 한다.

 

Unit (단위 원소)

• $Z_n$ 집합에 속하는 클래스 [a], [b]에 대해 [a][b] = 1을 만족하는 경우 [a]를 [b]에 대한 multiplicative inverse(곱셈 역원)이라고 한다. 
• [a]가 집합 $Z_n$에서 Unit이 되려면 multiplicative inverse를 가져야 한다.

이는 즉,

• 어떤 정수 a가 mod (n)에 대한 Unit이라면 $ab \equiv 1 mod (n)$ 이 되는 어떤 정수 b가 존재한다.

 

$Zn$ with a prime n : n이 소수일 때 $Z_n$은 Field 이다. 

정리 3

$Z_n$은 n이 소수일 때만 Field가 된다.

 

증명 1

n이 소수라고 가정하고 0 < a < n인 어떤 a에 대해 생각해보자. n이 소수이기 때문에 gcd(a, n) = 1 이다. 우리는 베주의 공식을 이용하여 as + tn = 1을 만드는 s, t가 존재함을 알 수 있다.

 

as = 1 - tn에서 양 변을 modulo n 연산을 취한다. tn은 n으로 나누어지므로 0이 된다.

이를 통해 $ as = 1 mod n $ 식을 얻을 수 있다. 즉, [a][s] = [1] 이다. [a]는 항등원을 만드는 [s]를 가지기 때문에 Unit이 된다.

그렇기에 $Z_n$은 필드이다.  

 

Bezout's Identity (베주 항등식)

두 정수 a, b의 최대 공약수 d에 대해 ax + by = d를 만족하는 두 정수 x, y가 존재한다.
(단, x, y는 유일하지 않음)

 

ax+by = 1(서로소인 두 수)을 만족할 수 있는 x, y가 존재한다는 것은 a와 b의 선형 결합을 통해 어떤 정수든 만들 수 있음을 뜻한다.

 

 

증명2

n이 소수가 아니라고 가정하고 1 < n1, n2 < n 인 두 수 n1, n2에 대해 생각해보자. [n1] != 0이고 [n2] != [0]이다. 하지만 [n1][n2] = [0]이 된다. 따라서 $Z_n$은 zero divisor를 가지게 되며, 이는 Field가 될 수 없는 이유가 된다. 

 

Integral domain : zero divisor가 없고 + commutative ring(Associative, Commutative)을 만족한다.

 

증명3

$Z_n$이 Field라고 하자. [a]는 0에서 n사이의 Unit이다.

그러면 [a][s] = [1]인 Inverse [s]가 존재한다.  $\textbf{as \equiv 1(mod n)}$ 그리고 $\textbf{as = 1 - tn}$식을 만족한다.

 

베주의 항등식에 따르면 a와 n의 양수 선형 결합은 gcd를 구해준다. $\textbf{as + tn = gcd(a, n)}$이다. 

이 경우 gcd(a, n)이 1이므로 a와 n이 서로소임을 나타낸다.

 

모든 0이 아닌 원소가 multiplicative inverse를 가지려면, n이 소수여야 한다.

 

 

정리4

$Z_n$에서 [a]가 Unit이 되는 것은 gcd(a, n)이 1일 때

 

증명

두 수 a와 n이 어떤 관계인지 알아보는 과정에서 $ab = 1 + qn$이라는 방정식을 가지고 있다.

 

1. 위 방정식을 재정리 하여 $ ab - qn = 1 $ 이라는 식을 만든다.

2. 여기서 a와 n이 공통의 약수 d를 가진다고 가정하자, 이는 d가 a와 n을 나눌 수 있다는 의미가 된다.

3. d가 a와 n을 나눌 수 있다면, ab - qn의 값인 1도 나눌 수 있어야 한다. 그러나 1을 나눌 수 있는 유일한 수는 1이다. 

4. 결과적으로 d = 1이어야만하며, 이는 a와 n이 서로소라는 것을 의미한다.

 

a와 n이 공통 약수가 1일 때만 ab - qn = 1을 만족시킬 수 있다.

 

증명2

$Z_n$에 속하는 [a]가 있고 [a]의 multiplicative inverse는 [s]이다.

[as] = [a][s] = [1]이 되며, $as \equiv 1 (mod n) $ 이고 Z에 속하는 t에 대해 $ as = 1 + tn $이다. 

그러므로 gcd(a, n) = 1이다.