[정수론] 4. 합동

합동

만약 $m | a-b$라면 $a \equiv b \mod m$이다.

 

꽤 심플한 정의이다.

"$a,b$을 $m$으로 나눈 나머지가 같다"라고도 표현할 수 있다.

예를들어 $5 \equiv 12 \mod 7$이다.

특히 $m=2$라면 짝홀을 구분할 수 있다.

그리고 $0 \le a < m$이고 $a \equiv b \mod m$이면 $b = a+mk  (k \in \mathbb{Z})$라고 나타낼 수 있다.

 

1차 합동방정식

$ax \equiv b \mod m$꼴의 방정식을 1차 합동방정식이라고 한다.

실수세계에서는 단순히 양변을 나눔으로써 해결할 수 있었다.

정수세계에서는 $(\mathbb{Z}, /)$이 이항연산이 아니기 때문에(현대대수 참고) 양변을 나눌 수 없다.

 

우선 합동방정식을 해결하는 가장 편리한 방법은 $x$에 $0, 1, ..., m-1$을 넣는것이다.

$3x \equiv 1 \mod 4$를 풀면 $x=3$이 나오는데 여기서 끝이 아니고 $x=3+4k (k \in \mathbb{Z})$라고 표현해야 한다.($x \equiv 3 \mod 4$ 도 가능)

하지만 이 방법은 $m$이 커지면 직접 할 수 없다.(ps에서 자주 쓰이는 $1,000,000,007$만 봐도 컴퓨터로 시간내에 연산할 수 없다.)

합동방정식의 성질을 이용하여 좀 더 아름답게 구해보자.

 

합동방정식의 성질

1. $a \equiv b \mod m$이고 $c \equiv d \mod m$이면 $a \pm c \equiv b \pm d \mod m$

2. $a \equiv b \mod m$이고 $c \equiv d \mod m$이면 $ac \equiv bd \mod m$

 

$c \equiv d \mod m$이라면 $c=d$도 가능하기 때문에 양변을 같은 수로 곱하는 것도 허용된다.

 

다만 주의할점은 아래는 성립하지 않는다.

1. $ac \equiv bc \mod m$이면 $a \equiv b \mod m$이 아니다.

2. $ab \equiv 0 \mod m$이면 $a \equiv 0 or b \equiv 0 \mod m$이 아니다.

 

1번은 $a=1, b=3, c=2, m=4$를 넣으면 알 수 있고 2번은 $a=2, b=3, m=6$을 넣으면 알 수 있다.

 

다시 성질을 이용하여 $3x \equiv 1 \mod 4$를 풀어보자.

양변에 $3$을 곱한다.

$9x \equiv x \equiv 3 \mod 4$이 되어 답을 구할 수 있다.

 

더 심화된 방법으로 구해보자.

실수 방정식 $3x = 4$를 구할 때 $x=\frac{4}{3}$이 나온 과정을 생각해보면 양변에 $\frac{1}{3}$을 곱해서 결과가 나온것이었다.

$\frac{1}{3}$은 $3$($x$의 계수)의 곱셈에 대한 역원이다.

그래서 엄밀히 말하면 방정식을 풀 때 양변을 $3$으로 나눈게 아니라 양변을 $3$의 역원을 곱한 것이라고 말할 수 있다.

 

합동방정식도 같은 방법으로 구할 수 있다.

$3$을 $4$로 나눈 나머지연산의 역원을 구할 수 있다면 그 수를 양변에 곱하여(성질 2에 의하여 가능) 해를 구할 수 있다.

그 수는 $3 \times 3 = 9 \equiv 1 \mod 4$이므로 역원은 $3$이고 이를 곱하면 해를 구할 수 있다.

그래서 성질을 이용하여 해를 구할 때 $3$을 곱한것이다.

역원은 나중에 쉽게 구하는 방법을 알아볼 것이다.

 

마지막으로 디오판투스 방정식을 이용하여 해를 구해보자

$3x \equiv 1 \mod 4$는 $3x=1+4k (k \in \mathbb{Z})$로 나타낼 수 있다.

$3x-4k=1$인 디오판투스 방정식을 얻었고 $\gcd(3,4) = 1$이므로 해가 존재한다.

지난시간에 디오판투스 방정식의 해를 구하는 법을 알았으니 그 방법을 이용하여 구하면 된다.

 

여기서 관찰할 점은 1차 합동방정식의 해가 존재할 조건은 디오판투스 방정식의 해가 존재할 조건에 의해 $\gcd(a,m) | b$여야 한다.