합동
만약 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여야 한다.
'수학 > 정수론' 카테고리의 다른 글
[정수론] 6. 중국인의 나머지 정리 (0) | 2022.04.21 |
---|---|
[정수론] 5. 고차 합동 방정식 (0) | 2022.04.20 |
[정수론] 3. 디오판투스 방정식 (0) | 2022.04.12 |
[정수론] 2. 유클리드 호제법 (0) | 2022.04.06 |
[정수론] 1. 피타고라스 세 수 (4) | 2022.04.06 |