합동은 정수를 나머지에 따라 분류하는 언어이다. 매우 큰 정수도 일정한 법(modulus) 아래에서는 유한한 개수의 나머지로 줄어들며, 덧셈·곱셈·거듭제곱을 이 작은 대표값으로 계산할 수 있다.
Congruence의 정의
양의 정수 에 대해
은 를 뜻한다. 즉 어떤 가 존재하여 이다.
Division Algorithm으로
라 하면
이다. 따라서 합동은 “으로 나눈 나머지가 같다”는 표현과 정확히 같다.
증명
이면
가 의 배수이다. 따라서 도 의 배수이다. 하지만 이므로 이다. 역방향은 이면 이므로 즉시 성립한다.
Least Residue와 Complete Residue System
각 정수는 modulo 에서 중 정확히 하나와 합동이다. 이를 least nonnegative residue라고 한다.
은 modulo 의 complete residue system이다. 더 일반적으로 서로 합동이 아닌 개의 정수가 모든 합동류를 하나씩 대표하면 complete residue system이다. 예를 들어 modulo 5에서 도 complete residue system이다.
합동의 기본 성질
합동 관계는 다음을 만족한다.
- Reflexive:
- Symmetric: 이면
- Transitive: , 이면
따라서 합동은 정수 집합 위의 equivalence relation이다.
또한
곱셈 성질을 반복하면 에 대해 이다. 정수계수 다항식 에 대해서도
이 성립한다.
합동식의 Cancellation
등식에서는 같은 0이 아닌 수를 약분할 수 있지만, 합동식에서는 조건 없이 약분하면 안 된다. 예를 들어
이지만 이다.
일반적인 약분 정리는 다음과 같다.
이고 이면
이다.
증명
이다. , 라 두면 이고
이다. Euclid’s Lemma에 의해 , 즉 이다.
특히 이면 법이 변하지 않아
이다.
Equivalence Class와
정수 의 합동류를
로 정의한다. 합동이 동치관계이므로 두 합동류는 완전히 같거나 서로 겹치지 않는다. 실제로 라면 어떤 가 두 집합에 속하고, 이므로 이다.
모든 합동류의 집합을
로 쓴다. 문맥이 분명하면 이라고도 쓴다.
Residue Class 위의 연산
합동류의 덧셈과 곱셈을
로 정의한다. 대표원을 다른 정수로 바꾸어도 결과가 같아야 한다. , 이면 합동의 연산 성질에 의해
이므로 이 연산은 well-defined이다.
덧셈에서는 모든 원소가 역원을 가진다. 의 덧셈 역원은 이다. 그러나 곱셈 역원은 항상 존재하지 않는다.
Modular Inverse
의 modulo 곱셈 역원은
을 만족하는 이다. 이를 로 표기한다.
가 modulo 에서 역원을 가질 필요충분조건은
이다.
증명
역원 가 존재하면 이므로
이다. 의 모든 공약수는 1을 나누어야 하므로 최대공약수는 1이다.
반대로 이면 Bézout’s Identity에 의해 인 정수 가 존재한다. modulo 으로 보면 이므로 가 역원이다.
가 소수이면 은 모두 와 서로소이므로 모든 0이 아닌 합동류가 역원을 가진다. 이 때문에 는 finite field가 된다. 반면 에서 는 역원을 가지지 않는다.
큰 거듭제곱의 나머지
합동식은 중간 결과를 계속 작은 나머지로 바꾸어도 결과가 보존된다. 예를 들어 을 구하자.
이므로
이다. 실제 계산에서는 지수를 이진수로 분해하는 repeated squaring을 사용하면 매우 큰 지수도 빠르게 처리할 수 있다.
진법 표현과 배수 판정법
인 진법에서 양의 정수 은
로 표현된다. 여기서 이다.
9의 배수 판정법
10진법에서 이므로 이다. 따라서
이다. 즉 자리 숫자의 합이 9의 배수일 때, 그리고 그때에만 원래 수도 9의 배수이다.
11의 배수 판정법
이므로 이다. 따라서
이다. 교대로 더하고 뺀 값이 11의 배수이면 원래 수도 11의 배수이다.
이 원리는 일반화된다. 이면 자릿수의 합을, 이면 교대합을 이용할 수 있다.
정리
합동은 정수를 같은 나머지를 갖는 동치류로 묶는다. 합동식의 덧셈과 곱셈은 대표원을 바꾸어도 잘 정의되지만, 약분에는 최대공약수 조건이 필요하다. Modular Inverse는 Bézout’s Identity와 동일한 조건에서 존재하며, 진법 표현을 합동으로 해석하면 여러 배수 판정법을 자연스럽게 증명할 수 있다.
연습 문제
- 을 계산한다.
- 이 modulo 에서 역원을 갖는지 판단하고, 존재하면 구한다.
- 10진수 가 11의 배수인지 판정한다.
풀이
1번
이다. 이므로
이다.
2번
이므로 역원이 존재한다. Euclidean Algorithm을 역대입하면
이므로 가 역원이다. 실제로 이다.
3번
오른쪽 자리부터 교대합을 계산하면
이다. 11의 배수가 아니므로 도 11의 배수가 아니다.