1. 선형 합동식(Linear Congruence)

선형 합동식
미지수 $x$에 대한 선형 합동식은 $ax \equiv b (\mod{n})$의 꼴로 나타나는 방정식이다.

위 방정식의 해 $x_0$은 $ax_0 \equiv b(\mod{n})$을 만족하는 정수다.

합동의 정의에 따라

이므로, $ax \equiv b(\mod{n})$의 모든 해를 구하는 것은 Diophantine equation $ax-ny = b$의 모든 해를 구하는 것과 같다.

단 선형 합동식의 해의 개수는 조금 다르게 센다는 점에 주의하자. $ax \equiv b (\mod{n})$의 해의 개수는 이 합동식을 만족하는, 법 $n$에 대해 서로 합동이 아닌 해의 개수를 말한다.

예를 들어 $x = 3$과 $x = -9$는 모두 $3x \equiv 9(\mod{12})$라는 합동식을 만족하지만, $3 \equiv -9 (\mod{12})$이므로 이 두 해는 서로 다른 해로 세지 않는다.

Thm 1.

선형 합동식 $ax \equiv b (\mod {n})$은 $d = gcd(a, n)$에 대해, $d | b$일 때, 오직 그럴 때만 해를 가진다. 또한 $d| b$일 때 이 합동식은 법 $n$에 대해 서로 합동이 아닌 $d$개의 해를 가진다.

$pf$
정수론 기초의 정리들을 보자.

Theorem 1.4
(i) $a≡b(\mod{n})$이고 $c ≡ d(\mod{n})$이면 $(a±c)≡(b±d)(\mod{n})$이다.
(ii) $a≡b(\mod{n}),c≡d(\mod{n})$이면 $ac≡bd(\mod{n})$이다.
(iii) $k>0∈ \mathbb{Z}$에 대해, $a≡b(\mod{n})$이면, $ak≡bk(\mod{n})$이다.​

Theorem 3.3(Euclid's Lemma)
정수 $a,b,c$에 대해, 만약 $a∣bc$이고, $a$와$b$가 서로소이면 $a∣c$이다.

Theorem 3.4
$a,b,n$이 정수라 하자. $a∣n,b∣n,(a,b)=1$이면 $ab∣n$이다.

Theorem 3.7
$a,b$가 $0$이 아닌 정수고, $c$가 정수이면 다음을 만족하는 정수 $x,y$가 존재한다. $ax+by=c⟺(a,b)∣c$

Theorem 3.8
$a,b,c,x_0​,y_0$​이 $ax_0​+by_0​=c$를 만족하는 정수들이라 하자. $x=x_0​+b/(a,b),y=y_0​−a/(a,b)$인 정수 $x,y$ 또한 $ax+by=c$를 만족한다.

Theorem 3.9
$ax_0​+by_0​=c$라면, 임의의 정수 $k$에 대해, 정수 $x=x_0​+kb/(a,b),y=y_0​−ka/(a,b)$또한 $ax+by=c$를 만족한다. 또한, $ax+by=c$의 모든 해들은 위와 같은 형태로 나타난다.

선형 합동식 $ax \equiv b (\mod {n})$가 해를 가짐이 $d|b$와 동치임을 증명

주어진 선형 합동식은 Diophantine equation $ax - ny = b$와 동치고, Theorem 3.7에 따라 이 방정식이 해를 가지는 것은 $gcd(a, n) | b$와 동치다.

$d|b$일 때, 합동식의 해가 정확히 $d$개임을 증명.

$ax-ny=b$의 어떤 해를 $x_0, y_0$이라 하자. Theorem 3.9에 따라 $ax - ny$의 모든 해는 다음과 같은 형식으로 나타난다.

정수 $t$에 대해, $x _ t = x_0 + (n/d)t$라고 하자.

(1) 합동식의 해가 적어도 $d$개임을 증명.

$0 \leq t \leq d-1$일 때의 $x_t$들 중, 법 $n$에 대해 합동인 것은 없음을 증명하면 된다.

$0 \leq t_1 < t_2 \leq d-1$인 정수 $t_1, t_2$에 대해

이라고 가정해보자. Therem 1.4 (i)에 따라

이다.

---

Lemma
$ca \equiv cb (\mod{n})$이면 $a \equiv b (\mod{n/d})$다. ($d = gcd(c, n)$)

$ca \equiv cb (\mod {n})$이므로 어떤 정수 $k$에 대해 $ca - cb = c(a- b) = kn$이라 쓸 수 있다. $gcd(c, n) = d$이므로 $c= dr, n = ds$가 되는 서로소인 정수 $r, s$가 있고, 따라서 다음과 같이 쓸 수 있다.

Theorem 3.3. 유클리드의 보조정리에 따라 $s | r(a-b)$이고 $r, s$가 서로소이므로 $s|a-b$이고다. 따라서 $a \equiv b (\mod {s})$이고, 즉 $a \equiv b (\mod {n/d})$다.

---

다시 증명으로 돌아가서, $gcd(n/d, n) = n/d$이므로 Lemma로부터 다음을 얻을 수 있다.

하지만 $0 \leq t_1 < t_2 \leq d - 1$이므로 $0 < t_2 - t_1 < d$이기에 $d|(t_1 - t_2)$를 만족하는 $t_1, t_2$는 존재할 수 없다. 즉 $0 \leq t \leq d-1$일 때의 $x_t$들 중 법 $n$에 대해 합동인 것은 없다. 즉 주어진 합동식의 해는 적어도 $d$개다.

(2) 합동식의 해가 정확히 $d$개임을 증명

$x_0, x_1, ..., x_{d-1}$ 중 어떤 것과도 합동이 아닌 해 $x_0 + (n/d)t$가 있을 수 없음을 보인다.

$t = qd + r,\ (0 \leq r \leq d-1)$이라 둘 수 있고, 다음과 같이 쓸 수 있다.

따라서 임의의 정수 $t$에 대해, $x_t$는 $x_0, ..., x_{d-1}$ 중 하나와 합동이고, 주어진 합동식은 $d$개보다 많은 해를 가질 수 없다.

Corollary

$gcd(a, n) = 1$이면, 선형 합동식 $ax \equiv b (\mod{n})$은 법 $n$에 대해 유일한 해를 가진다.

2. 중국인의 나머지 정리

Thm2. Chinese Remainder Theorem

$gcd(n_i, n_j) = 1,(i \not= j)$인 양의 정수 $n_1, n_2, ... , n_r$에 대해, 다음의 연립 합동식

$\begin{aligned} x &\equiv a_1(\mod{n_1})\\ x &\equiv a_2(\mod{n_2})\\ &...\\ x &\equiv a_r(\mod{n_r})\\ \end{aligned}$

은 법 $n1, ..., n_r$에 대해 유일한 해를 가진다.

$pf$

(1) 해의 존재성 증명

$n = n_1n_2...n_r$이라 하고, 각 $k = 1, 2, ..., r$에 대해

이라 하자.

각 $n_i$가 모두 서로 서로소이므로, $gcd(N_k, n_k)$도 $1$이다. Thm1의 Corollary에 따라 $N_kx \equiv 1(\mod{n_k})$는 유일한 해를 가지는데, 이 해를 $x_k$라 하자. 다음의 정수

이 주어진 연립 합동식의 해임을 증명한다.

$k$가 아닌 정수 $i$($1 \leq i \leq r)$를 생각해보자. $N_i = n/n_i$이고 $n_i \not= n_k$이므로 $n_k|N_i$고, 따라서 $N_i \equiv 0 (\mod{n_k})$다. 이를 위의 $\bar{x}$에 적용하면,

임을 알 수 있다.

이때 $N_kx \equiv 1 \mod(n_k)$이므로,

다. 이 결과는 $1 \leq i \leq r$인 모든 정수 $i$에 대해 적용되므로, $\bar{x}$는 주어진 연립 합동식 모두의 해가 된다.

(2) 해의 유일성 증명

$x'$가 위 연립 합동식을 만족하는 또 다른 해라고 가정하자. 그러면

이다. 각 $k$에 대해 $n_k | \bar{x} - x'$이고 $gcd(n_i, n_j) = 1$이다.

Theorem3.3에 따라 $n_1n_2...n_r|\bar{x} - x'$다. 즉 $\bar{x} \equiv x' (\mod{n})$이므로 해는 유일하다( $ax \equiv b (\mod{n})$의 해의 개수는 이 합동식을 만족하는, 법 $n$에 대해 서로 합동이 아닌 해의 개수를 말하므로).

Burton, D.M. (2010) Elementary Number Theory. 7th Edition