5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime)

서로소

$\text{gcd}(x,y) = 1$이면, $x$와 $y$는 서로소^{relatively prime}이다.

합동식^{Congruent Expression}

정수 $x,y$의 차가 $n$의 배수인 경우, 법^Modular $n$에 대해, 정수 $x,y$가 합동^Congruent이라 하고 아래와 같이 나타낸다.

$$x \equiv y (\mod n)$$

예를들어 $10\equiv 1 (\mod 3)$, $5\equiv 9 (\mod 4)$이다.

합동식의 곱셈의 역원

어떤 합동식 (예, $3x \equiv 7 (\mod 4)$)에 대하여, 올바른 $x$를 합동식의 해라 하는데, 특히 $xx^{-1} \equiv 1 (\mod n$꼴의 합동식에서, $x^{-1}$을 합동식의 곱셈의 역원^{Moular Multiplcative Inverse}이라 한다.

$$\text{ex) } 3\cdot2 \equiv 1 ( \mod 5)$$

$x=3, x^{-1}=2$이다.

확장된 유클리드 호제법^{Extended Euclidean Algorithm}

확장된 유클리드 호제법을 이용하여 합동식의 곱셈의 역원을 구할 수 있다.

$xx^{-1} \equiv 1 (\mod n)$일 때, $x,n$의 최대공약수를 구하면 된다.

합동식의 성질

$$\text{rem}(b, n) \equiv b (\mod n)$$

$b$를 $n$으로 나눈 나머지는 $b-q\cdot n$이다. 

$b-q\cdot n \equiv b (\mod n)$이므로 $n|-q\cdot n$이 된다.

$$a+k\equiv b+k (\mod n)$$

$a+k$와 $b-k$의 차는 $a,b$의 차와 변하지 않으므로, $a,b$에 정수 $k$를 더해도 여전히 합동이다.

$$a\cdot k \equiv b \cdot k (\mod n)$$

$ka - kb$도 여전히 $n$의 배수이므로 합동이다.

$(a1, b1)$, $(a2, b2)$가 각각 $n$에 대해 합동일 때,

$$a1\mp a2 \equiv b1 \mp b2 (\mod n)$$

$$a1\cdot a2 \equiv b1\cdot b2 (\mod n)$$

$$a^k \equiv b^k (\mod n)$$