합동식과 모듈러 산술

합동 관계

오늘이 월요일이면 $15$일 뒤는 화요일이고 $1000$일 뒤는 일요일이다. 이를 알기 위해 날을 하나씩 셀 필요는 없으며, 날수를 $7$로 나눈 나머지만 있으면 된다. 마찬가지로 $5$시간 뒤에는 $9$시에서 세어 $2$시가 되는데, 이는 $12$시간 문자판에서의 일이다. 또한 곱의 마지막 자리 숫자는 인수들의 마지막 자리 숫자에만 의존한다. 세 경우 모두 나머지로 계산하고 몫은 잊는다. 나누어떨어짐과 나머지가 있는 나눗셈 수업은 정수를 자연수로 나눈 나머지에 따라 류로 나누었고, 합, 곱, 거듭제곱의 나머지가 주어진 수들의 나머지에만 의존함을 증명하였다. 이 수업은 이러한 관찰에 고유한 언어, 곧 합동식의 언어를 준다. 이 언어는 가우스가 1801년에 Disquisitiones Arithmeticae에서 도입한 것이며, 이 수업은 그것을 계산의 도구로 만든다. 그 수업에서처럼 정수는 미리 사용하며, 그 연산과 순서의 규칙은 정수 수업에서 정당화된다.

정의 (합동). $n$이 자연수라 하자. 두 정수 $a$와 $b$가 법 $n$에 대하여 합동이라는 것은 $n$이 그 차 $a - b$를 나누는 것을 말한다. $a \equiv b \pmod{n}$로 쓰고 “$a$는 $b$와, 법 $n$에 대하여 합동”이라 읽는다. 자연수 $n$을 이 합동식의 법이라 한다.

예를 들어 $17 \equiv 2 \pmod{5}$인데, $17 - 2 = 15$이기 때문이다. 또 $-3 \equiv 9 \pmod{4}$인데, $-3 - 9 = -12$이기 때문이다. 정수가 짝수일 필요충분조건은 그것이 $0$과 법 $2$에 대하여 합동인 것이다. $a$가 $n$의 배수라는 것은 이제 $a \equiv 0 \pmod{n}$로 쓴다. 법 $1$에 대해서는 모든 정수가 서로 합동이다. $1$은 모든 정수를 나누기 때문이다. 이 경우는 흥미가 없으므로, 예에서 법은 $2$ 이상으로 한다. 세 줄로 된 기호 $\equiv$은 등호를 떠올리게 하는데, 뒤에서 보듯이 합동은 거의 모든 면에서 등식처럼 행동하기 때문이다. 예외인 나눗셈은 역원에 관한 절에서 다룬다.

차를 이용한 정의는 증명에 가장 편리하지만, 처음 예들의 직관은 나머지에 관한 것이다. 다음 명제는 두 기술이 같은 것을 말함을 보장한다. 그 내용은 나누어떨어짐 수업에서 배수 판정법을 정당화할 때 다른 형태로 이미 언급되었으며, 여기서는 모든 단계를 거쳐 증명한다.

특히 모든 정수는 법 $n$에 대하여 자신의 나머지와 합동이고, 그 나머지는 $n$개의 정수 $0, 1, \ldots, n - 1$ 가운데 하나이며, 그 가운데 오직 하나와만 합동이다. 이 수들 중 어느 두 수도 각각 자기 자신의 나머지이고, 서로 다르면 나머지도 다르기 때문이다. 법 $n$에 대하여 계산한다는 것은 각 수를 그 열의 편리한 대표로 바꾸는 것이다. 대표로는 나머지를 쓰고, 때로는 작은 음수를 쓴다. 예를 들어 $-1$을 $n - 1$ 대신 쓴다.