Number Theory - 4.4 선형 합동식과 중국인의 나머지 정리
선형 합동식의 해가 존재할 필요충분조건, 해의 개수
$ax \equiv b \pmod n$의 형태를 선형 합동식이라 하고, 이 방정식의 해는 $ax_0 \equiv b \pmod n$ 을 만족하는 정수 $x_0$ 이다.
이는 $n \mid ax_0-b$의 필요 충분조건이며, 따라서 어떤 정수 $y_0$이 존재하여
$ax_0-b=ny_0$이고, $ax_0-ny_0=b$ 에 대한 해를 구하는 문제가 된다.
따라서, $gcd(a,n) \mid b$가 해가 존재할 필요충분조건이다.
Theorem 4.7
$d=gcd(a, n)$이라 할 때,
선형 합동식 $ax \equiv b \pmod n$의 해가 존재할 조건은 $d \mid b$ 이다.
이 조건이 만족되면 법 $n$에 대해 $d$개의 서로 합동이 아닌 해를 가진다.
증명
$ax-ny=b$의 해 $(x,y)$가 존재할 조건은 $d \mid b$이다. 이것은 증명되었다. 2단원 참고
해가 있을 때, 이를 만족하는 $(x,y)$의 해는 무수히 많고, 특이해 $(x_0, y_0)$에 대해,
는 일반해이다.
2-5 디오판투스 방정식 단원 참고
법 $n$에 대한 완전잉여계
$t$가 연속적인 값 $t=0,1,2,\dots ,d-1$ 일 때를 생각하자.
이 정수들은 법 $n$에 대해 완전잉여계를 형성한다. 그렇지 않다고 하자.
$(0 \le i, j < d, i \ne j)$ 에 대해,
$x_0+i(n/d) \equiv x_0+j(n/d) \pmod n$이고, $(i-j)(n/d) \equiv 0 \pmod n$ 이 된다.
양변에서 $n/d$ 를 소거하여 $gcd(n, n/d)=n/d$ 이기 때문에 $(i-j) \equiv 0 \pmod d$ 를 얻는다.
그런데 $\lvert i-j \rvert < d$ 이기 때문에 $i=j$ 가 되야해서 모순이다. 따라서 완전잉여계를 형성한다.
$d$개의 법 $n$에 대한 서로 다른 해를 구했고, 임의의 해가 이 $d$개 중 하나와 합동을 이룸을 보이자.
임의의 해 $x_0+(n/d)t$ 에 대해 $t=qd+r$ 을 만족하는 $q,r~(0 \le r < d)$ 가 유일히 존재한다.
나눗셈 정리
$0 \le r < d$ 이기 때문에 이는 앞서 구했던 $d$개의 해 중 임의의 해와 합동이므로 선형 합동식 $ax \equiv b \pmod n$ 가 해가 존재한다면, 어떤 해는 법 $n$에 대해 $d(=gcd(a,n))$개의 서로 다른 해를 가짐이 증명된다. $\square$
Corollary 1
$gcd(a,n)=1$ 이면, $ax \equiv b \pmod n$의 단 하나의 해가 존재한다.
나머지 연산의 곱셈 역원
$ax \equiv 1 \pmod n$이 유일한 해를 가질 조건은 $gcd(a,n)=1$ 일 때 뿐이며, 이를 Inverse of a modulo $n$ 이라 부른다.
PS에서 나머지 연산의 곱셈 역원은 큰 수에 대해서 나머지를 구하려는 식에 나눗셈이 포함되어 있는 경우 굉장히 유용하고 중요하다.
대개 확장 유클리드 호제법이나 페르마의 소정리로 구해진다.
$ax \equiv 1 \pmod n$인 합동식에 대해서 $x$를 구한다는 것은, 합동식의 어떤 $a$에 $x$를 곱해서 $1$ 을 만드는 역원을 활용할 수 있다는 의미이고, 나눗셈 연산대신 이 역원이랑 곱셈 연산을 해줌으로써 합동식에서의 해를 구할 수 있기 때문이다.
예시
예를 들어, $_N\mathrm{C}_K=\dfrac {N!}{K!(N-K)!}$ 인데, 이것의 법 $m$에 대한 나머지를 구하고 싶다고 하자.
그럼 우린 $K!$와 $(N-K)!$ 에 대해 법 $m$에 대한 Inverse modulo를 구하면, $N!$ 에 그걸 곱해주고 $m$으로 나눠줌으로써 $_N\mathrm{C}_K$를 $m$으로 나눈 나머지를 구할 수 있다는 의미이다.
하지만 앞서 설명했듯이 $gcd(a, n)=1$ 일 때만 Inverse modulo가 존재하여 활용할 수 있다.
그래서 문제에서 대개 $m$은 소수로 주어지는 편이다.
연립 선형 합동 방정식
연립 선형 합동 방정식을 간단한 형태로 정리하는 법을 살펴본다.
연립 선형 합동방정식
가 있을 때, 모두 해가 있다면,
$d_k=gcd(a_k, m_k)$ 일 때, 어떤 $k$에 대해 $d_k \nmid b_k$ 라면 해가 없다.
라고 둔다면,
로 변환되며 더 나아가 임의의 $i, j(i \ne j)$에 대해 , $n_i \ne n_j$ 를 만족하는 꼴로 정리할 수 있다.
이 때, $gcd(a'_k, n_k)=1$이므로
$\because d_k=gcd(a_k, m_k)$
$a'_kI_k \equiv 1 \pmod {n_k}$ 를 만족하는 Inverse modulo $I_k$가 존재하고, 이를 $(1)$ 에서 각 양변에 곱해준다면,
를 얻는다.
중국인의 나머지 정리
중국인의 나머지 정리는 PS에서 종종(?) 나올 정도로 실용적인 경우가 있는데, 이 글에서 소개하는 이론적인 내용도 중요하지만 좀더 실용적인 방법으로 코드를 짤 수 있다.
관련한 내용들은 따로 정리를 할 예정이다.
Theorem 4.8 - 중국인의 나머지 정리(Chinese Remainder Theorem)
$n_1, n_2, \dots, n_r$ 을 $i \ne j$에 대해 $gcd(n_i, n_j)=1$ 인 양의 정수라 할 때, 연립 선형합동식
은 법 $\displaystyle \prod_{k=1}^r n_k$ 에 대해 유일한 공통 해를 갖는다.
증명
$N=\displaystyle \prod_{k=1}^{r} n_k$ 라 하고, $N_i=N/n_i$ 라 하자.
$gcd(N_i, n_i)=1$ 이다.
$\because$ 유클리드 보조정리에 의해
따라서 $N_kx_k \equiv 1 \pmod {n_i}$ 를 만족하는 해 $x_k$가 존재한다.
$x=\displaystyle \sum_{k=1}^r a_kN_kx_k$ 라 하면, 이 해가 주어진 연립 선형합동식을 만족하게된다.
어떤 $i(1 \le i \le r)$에 대해, $i \ne j$인 $a_jN_jx_j$는 $n_i$로 나누어 떨어진다.
$\because n_i \mid N_j$
따라서 $x \equiv \displaystyle \sum_{k=1}^r a_kN_kx_k \equiv a_iN_ix_i \equiv a_i \pmod {n_i}$ 이다.
$\because N_ix_i \equiv 1 \pmod {n_i}$
이렇게 모든 $i$에 대해 $x$가 선형합동식을 만족하는 해이기 때문에 해의 존재성이 증명된다.
해의 유일성
$x \ne x'$ 인 또 다른 해 $x'$ 가 있다고 가정하자.
어떤 $k$에 대해 $x-x' \equiv 0 \pmod {n_k}$ 이다.
$gcd(a,b)=1$ 일 때, $a \mid c,~b \mid c \Rightarrow ab \mid c$ 이므로,
Theorem 2.4 - corollary 2 이다.
위 식에서 모든 $n_i$가 서로 서로소이기 때문이다.
$x-x' \equiv 0 \pmod {\sum_{k=1}^r n_k}$가 되는데 이는 모순이다.
따라서 또 다른 해 $x'$는 존재하지않고 유일성이 증명된다. $\blacksquare$
미지수가 2개인 연립 선형합동식
변수가 $2$개인 선형 합동식
이 해가 존재할 조건은, $gcd(a,b,n) \mid c$ 이다.
Theorem 4.9
다음 연립 선형합동식
은 $gcd(ad-bc)=1$ 일 때, 법 $n$에 대해 유일한 해를 가진다.
증명
$(ad-bc)t \equiv 1 \pmod n$인 유일한 해인 $t$에 대하여 $\textcircled{1}$에 양변을 곱해주면,
이는 연립합동식의 해 $x$가 존재함이 보인다.
이와 비슷하게
이 과정은 사실 중학교때 배우는 연립방정식을 푸는것과 다르지 않다.
Comments