Loading [MathJax]/extensions/TeX/mathchoice.js

수학/정수론

[정수론] 4. 합동

riroan 2022. 4. 17. 04:15

합동

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

 

꽤 심플한 정의이다.

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

예를들어 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}, /)이 이항연산이 아니기 때문에(현대대수 참고) 양변을 나눌 수 없다.

 

우선 합동방정식을 해결하는 가장 편리한 방법은 x0, 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의 역원을 곱한 것이라고 말할 수 있다.

 

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

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

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

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

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

 

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

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

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

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

 

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