선형 합동식의 해가 존재할 필요충분조건, 해의 개수Permalink

$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.7Permalink

$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 1Permalink

$gcd(a,n)=1$ 이면, $ax \equiv b \pmod n$의 단 하나의 해가 존재한다.

나머지 연산의 곱셈 역원Permalink

$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$은 소수로 주어지는 편이다.

연립 선형 합동 방정식Permalink

연립 선형 합동 방정식을 간단한 형태로 정리하는 법을 살펴본다.

연립 선형 합동방정식

가 있을 때, 모두 해가 있다면,

$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)$ 에서 각 양변에 곱해준다면,

를 얻는다.

중국인의 나머지 정리Permalink

중국인의 나머지 정리는 PS에서 종종(?) 나올 정도로 실용적인 경우가 있는데, 이 글에서 소개하는 이론적인 내용도 중요하지만 좀더 실용적인 방법으로 코드를 짤 수 있다.

관련한 내용들은 따로 정리를 할 예정이다.

Theorem 4.8 - 중국인의 나머지 정리(Chinese Remainder Theorem)Permalink

$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개인 연립 선형합동식Permalink

변수가 $2$개인 선형 합동식

이 해가 존재할 조건은, $gcd(a,b,n) \mid c$ 이다.

Theorem 4.9Permalink

다음 연립 선형합동식

은 $gcd(ad-bc)=1$ 일 때, 법 $n$에 대해 유일한 해를 가진다.

증명

$(ad-bc)t \equiv 1 \pmod n$인 유일한 해인 $t$에 대하여 $\textcircled{1}$에 양변을 곱해주면,

이는 연립합동식의 해 $x$가 존재함이 보인다.

이와 비슷하게

이 과정은 사실 중학교때 배우는 연립방정식을 푸는것과 다르지 않다.