선형합동식은 합동 이론에서 가장 기본적인 방정식이다. 하나의 선형합동식을 푸는 문제는 일차 디오판토스 방정식과 동일하며, 여러 합동식을 동시에 만족시키는 문제는 Chinese Remainder Theorem으로 해결된다.
Linear Congruence와 Diophantine Equation
다음 선형합동식을 생각하자.
정의에 의해 이는 이고, 어떤 에 대해
라는 뜻이다. 따라서 선형합동식의 해 존재 문제는 계수 인 일차 디오판토스 방정식의 해 존재 문제와 같다.
해의 존재 조건
이라 하자. 선형합동식
은 일 때, 그리고 그때에만 해를 갖는다.
증명
해 가 존재하면 어떤 에 대해 이다. 는 을 나누므로 이다.
반대로 라고 하자. Bézout’s Identity로
인 정수 가 존재하고 로 쓸 수 있다. 양변에 를 곱하면
이므로 가 선형합동식의 한 해이다.
해의 개수와 형태
라 하자. 식을 로 나누면
이고
이다. 따라서 는 modulo 에서 역원을 가지며, 유일한 해
를 갖는다.
원래 modulo 에서는 다음 개의 서로 합동이 아닌 해가 존재한다.
이들이 서로 다른 이유를 보자. 두 해가 modulo 에서 같다면
이고, 정리 3의 약분 법칙을 적용하면 이다. 그런데 이므로 이다.
특히 이면 해는 modulo 에서 유일하고
이다.
예제:
이고 이므로 해가 존재한다. 6으로 나누면
이다. 이므로
이다. modulo 42에서는 정확히 6개의 해가 있다.
예제:
이고 이므로 3개의 해가 있다. 3으로 나누면
이고 이므로 이다. 따라서 modulo 30에서
이다.
연립합동식
여러 조건
을 동시에 만족시키는 정수 를 찾고 싶다. 법들이 pairwise relatively prime일 때 Chinese Remainder Theorem이 완전한 답을 준다.
Chinese Remainder Theorem
양의 정수 가 서로 쌍마다 서로소라고 하자. 그러면 임의의 정수 에 대해
를 만족하는 해가 존재하며, 그 해는 modulo
에서 유일하다.
존재성 증명
라 두자. 는 와 서로소이므로 어떤 가 존재하여
이다. 다음 수를 만든다.
고정된 에 대해 modulo 로 보자. 이면 이므로 해당 항은 0과 합동이다. 인 항은 이므로
이다. 모든 에 대해 성립하므로 해가 존재한다.
유일성 증명
가 모두 해라면 각 에 대해 이다. 법들이 서로 쌍마다 서로소이므로 그 곱 도 를 나눈다. 따라서
이다.
CRT 계산 예제
다음 연립합동식을 풀어 보자.
이고
이다. 각각의 역원은
이다. 따라서
이다.
법들이 서로소가 아닐 때
두 합동식
은 항상 풀리는 것이 아니다. 해가 존재할 필요충분조건은
이다.
해 가 존재하면 , 이므로 는 두 차를 모두 나눈다. 따라서 이다. 역방향은 를 두 번째 합동식에 대입하여 선형합동식
의 해 존재 조건을 적용하면 된다.
해가 존재하면 modulo 에서 유일하다.
정리
선형합동식은 일차 디오판토스 방정식으로 바뀌며, 최대공약수가 우변을 나누는지가 해의 존재를 결정한다. 해가 존재하면 modulo 에서 정확히 개의 해가 생긴다. Chinese Remainder Theorem은 서로소인 여러 법에 대한 나머지 정보를 하나의 modulo 곱의 정보로 결합한다.
연습 문제
- 의 모든 해를 구한다.
- 다음 연립합동식을 푼다.
- , 가 해를 갖는지 판단한다.
풀이
1번
이고 이므로 해가 존재한다. 2로 나누면
이다. 이므로
이다. modulo 30에서 두 해는 이다.
2번
이다. , , 이고
이다. 따라서
이다.
3번
인데 가 아니라 실제로 둘 다 2와 합동이므로 조건을 만족한다. 해가 존재한다. 첫 식에서 를 두 번째에 대입하면
이고 이다. 따라서 , 즉 이다.