합동식

合同式 / congruence 또는 modular

정수 $a$, $b$, $m$에 대하여, $m\mid(a-b)$일 때[1]

라고 하고, 이를 기호로는

라고 나타내며 $m$을 합동의 법(modulus)이라고 한다. 간단히 말해서, "$a$를 $m$으로 나눈 나머지는 $b~(0\le b<m)$"라는 문장을 수식으로 표현한 것.[4] 한편 mod는 모듈로(modulo)의 약어로 연산(자)을 가리킨다. 여기서 주의할점은 $b \bmod m=a$에서처럼 이 모듈로(mod)에 의해서 등호(=)는 나머지를 의미하게 된다는 점.

일반적으로 나머지(remainder)는 나누는 수보다 작지만, 합동식에서는 $b$값에 제한이 없다는 차이점은 존재한다. 다시 말해 $a\equiv b\pmod m$에서 $b$에 들어갈 수 있는 수 자체는 많이 있고, 그중에 가장 작은 자연수가 초등학교 때 배운 '나머지'이다.

나머지라는 개념 자체가 초등학교 시절 초반에 배우던 것이어서 보통 마치 분수라는 가르치기 어려운 개념을 회피하기 위해 만들어진 것 같아 보인다. 그러나 천만의 말씀. 나머지는 수학에서 가장 신비로운 개념 중 하나로, 덧셈이나 곱셈에만 적용되는 줄 알았던 연산개념이 신기하게도 나머지에서 완전 같은 방법으로 적용된다는 점을 깨닫게 되면 정수론에 대한 관심이 꽃피게 되는 일이 많다.

대학교의 정수론 수업이나 특정 수학 과목의 정수론 파트를 듣지 않는 한 배울 일이 없지만, KMO를 비롯한 수학 경시대회를 준비한다면 반드시 알아놔야 할 것 중 하나. 2차 잉여까지는 알 필요 없지만 아래 기본적인 성질은 모두 숙지하는 것이 좋다.

1. 반사성(reflexivity)

2. 대칭성(symmetry) (교환법칙)

3. 추이성(transitivity)

또한 $a\equiv b\pmod m$은 정수 $k$에 대하여 다음과 같은 법 호환성(compatibility)[5]이 있다.
4. 정수 평행이동에 대한 호환성(compatibility with translation)

5. 정수배에 대한 호환성(compatibility with scaling)

특히 $k$가 음이 아닌 정수일 경우 다음과 같이 지수 연산에 대해서도 법이 불변이다.
6. 지수 연산에 대한 호환성(compatibility with exponentiation)

아래는 두 합동식이 법 $m$으로 같을 때, 즉 $\begin{cases} a\equiv b\pmod m \\ c\equiv d\pmod m\end{cases}$일 경우 성립하는 호환성이다.
7. 덧셈/뺄셈 연산에 대한 호환성(compatibility with addition/subtraction)

8. 곱셈 연산에 대한 호환성(compatibility with multiplication)

아래 세 성질은 상기 정수배에 대한 호환성과 관련이 깊다.
9. $ab\equiv ac\pmod m$이고, $d=\gcd(a,\,m)$이면, $b\equiv c\mathrel{\biggl(\mathrel{\bmod}\dfrac md\biggr)}$이다.[7]

10. $a\equiv b\pmod m$이고, $n$이 $m$의 약수이면, $a\equiv b\pmod n$이다.

11. $a\equiv b\pmod m$이고, $d>0$이 $a$, $b$, $m$의 공약수이면, $\dfrac ad\equiv\dfrac bd\mathrel{\biggl(\mathrel{\bmod}\dfrac md\biggr)}$이다.[8]

일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 $ax\equiv b\pmod m$인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. $d=\gcd(a,\,m)$, 즉 $d$가 $a$와 $m$의 최대공약수라 했을 때, $b$가 $d$로 나누어 떨어지지 않으면($d\nmid b$) 합동식은 정수해를 갖지 않고, $b$가 $d$로 나누어 떨어지면($d\mid b$) 법 $m$에 대해 정확히 $d$개의 서로 다른 해를 갖게된다. 해의 존재성에 대한 증명은 다음과 같다.

크게 디오판토스 방정식, 유클리드 호제법, 잉여역수를 이용하는 방법으로 나눌 수 있다. 여기서는 다음 예제의 해법을 소개한다.

적당한 정수 $y$에 대하여 $3x+4y=7$이다. 여기서 $x_0=1$, $y_0=1$은 한 해(특수해)임을 쉽게 알 수 있다. $\gcd(3,\,4)=1$이므로 일반해는 $\begin{cases} x=1+4t \\ y=1-3t\end{cases}$이다. 우리가 구하는 것은 $x$와 관련된 것이므로 $x\equiv1\pmod4$가 해이다.

$\gcd(3,\,4)=1$이므로, 적당한 정수 $a$, $b$에 대해 $3a+4b=1$이다(최대공약수 참고). 실제로, $(-1){\cdot}3+1{\cdot}4=1$이다. 이 사실은 우리에게 $1\cdot x$를 얻기 위하여 $x$의 계수를 바꿀 수 있음을 암시한다. 즉, 아래와 같이 된다.

그리고, (1)식에서 (2)식을 빼면, $x\equiv-7\pmod4$가 된다. $-7+2{\cdot}4 = 1$이므로 $-7\equiv1\pmod4$ 이기에, 위 식을 $x\equiv1\pmod4$로 써도 된다.

그래서 답은 $x\equiv1\pmod4$이다.

법 4에 대한 곱셈표는 아래와 같다.[9]

위 표에서 보듯이 $3{\cdot}3\equiv1\pmod4$이다.

원래 식 $3x\equiv7\pmod4$ 의 양변에 3을 곱하면 $3{\cdot}3x\equiv 3{\cdot}7 \pmod4$가 되는데, $3{\cdot}3\equiv1\pmod4$이고, $21\equiv1\pmod4$ 이므로 이를 정리하면 $x\equiv1\pmod4$가 나온다.

일차 합동식과 마찬가지로 미지수의 최대 차수가 2 이상이 되어 항을 여러 개를 갖는 합동식을 말한다. 원래는 미지수가 여러 개가 있는 방정식처럼 다원다차 합동식같은 형태로 표기해야 하나, 기본적으로는 일원다차 합동식. 즉 미지수가 한 개만 존재하는 합동식을 위주로 탐구하게 된다. 수식으로 따지면

의 형태를 띄게 된다.
풀이 과정에 대한 명백한 알고리즘이 있는 것은 아니나, 특수한 경우에 따라 합동식의 근이 가져야 할 성질이 많이 밝혀져 있다.

법 $\bm m$ 위주로 풀이하는 쪽에서 사용한다.
$m$이 쌍마다 서로소인 $m_1,\,m_2,\,m_3,\,\cdots,\,m_t$의 최소공배수라고 하면, 중국인의 나머지 정리는 다음과 같이 사용된다.

합동식을 다룰줄 안다면 여러 경이로운 문제들의 답을 생각보다 쉽게 찾을 수 있다.

$7^{242}$의 10의 자리수와 1의 자리수를 합동식을 이용하여 구하시오.

[힌트]

$7^4$

[풀이]

$7^4 = 2401 \equiv 1\pmod{100} \rightarrow (7^4)^{60} \equiv 1^{60}\pmod{100} \rightarrow 7^{240} \equiv 1\pmod{100}$
$7^{242} = 7^{240} \times 7^2$이니, $7^{242}\equiv7^2\pmod{100}$.
그러므로 답은 $49$이다.

또 다른 풀이: $7^2 = 49 \equiv 1\pmod4 \rightarrow (7^2)^{121} \equiv 1^{121}\pmod4$
$7^2 = 49 \equiv -1\pmod{25} \rightarrow (7^2)^{121} \equiv (-1)^{121} = -1 = 24\pmod{25}$
$7^{242} \equiv 24 \pmod{25} \rightarrow 7^{242} = 25k + 24 \rightarrow 25k + 24 \equiv 1\pmod4 \rightarrow k \equiv 1 \pmod4 \rightarrow k = 4n + 1$, $7^{242} = 100n +49$
따라서 답은 $49$이다.

$7^{7^{777}}$의 1의 자리수를 합동식을 이용하여 구하시오.

[풀이]

$7 \equiv -1 \pmod4 \rightarrow 7^{777} \equiv (-1)^{777} \pmod4 \rightarrow 7^{777} \equiv -1 \pmod4$.
그렇다면, $7^{7^{777}} = 7^{4n+(4-1)} = 7^{4n+3}$을 만족하는 자연수 $n$이 존재한다.
$7^4 \equiv 1 \pmod{10}$이므로 $7^{4n} \equiv 1 \pmod{10}$다. 따라서 $7^{4n+3} \equiv 7^3 \equiv 3 \pmod{10}$이다.
답은 $3$이다.

$1^2 + 2^2 + \cdots + 98^2 + 99^2$ 의 1의 자리수를 합동식을 이용하여 구하시오. [10]

[풀이]

$1^2 + 2^2 + \cdots + 98^2 + 99^2 \equiv n \pmod{10}$이라 하자.
$1^2 \equiv 11^2 \equiv \cdots \equiv 91^2 \pmod{10}$이며, $2^2 \equiv 12^2 \equiv \cdots \equiv 92^2 \pmod{10}$등등 이니까
$1^2+2^2+\cdots9^2\equiv 11^2+12^2+\cdots19^2\equiv \cdots \equiv 91^2+92^2+\cdots99^2\equiv \cfrac n{10} \pmod{10}$이다.
따라서 $n$은 $10$의 배수가 되는 것이니, 답은 $0$이다.

합동식 $a\equiv b\pmod m$에 대하여 $a$와 $m$이 서로소일 때, $b$와 $m$이 서로소임을 보이시오.

[풀이]

먼저 $b$와 $m$이 서로소가 아니라고 가정해보자. 그렇다면 $a\equiv cd \pmod{cn}$(단, $c>1$)이 성립한다. 그렇다면 $cn\mid(a - cd) \rightarrow cn\biggm|c\biggl(\cfrac ac-d\biggr) \rightarrow n \biggm|\biggl(\cfrac ac-d\biggr)$ 다. 이게 성립하려면 $a$는 $c$의 배수여야하니, $a$와 $m$도 서로소가 아니다.
여기까지 우리가 증명한 건 "$b$와 $m$이 서로소가 아니라면, $a$와 $m$도 서로소가 아니다"인데, 이건 예제에 나오는 명제의 대우다. 따라서 예제의 명제 "$a$와 $m$이 서로소라면, $b$와 $m$역시 서로소다"도 참이다.

소수(prime)에 대한 위의 정의를 가정해본다면 모듈로(나머지 언산자)를 사용하는 모듈러(modular)가 얼마나 강력한 수학 연산자인지 또 다시 알게된다.
2를 제외한 모든 소수는 $4k+1$ 또는 $4k+3$의 합동식으로 구현된다는 것을 조사할 수 있다.(k는 0을 포함한 자연수)
이러한 소수 합동식은 소수 생성에서 장기적으로 동일한 비율로 소수를 생성하는 것으로 알려져있다.
한편 $4k+3$ 꼴의 소수가 무한함은 쉽게 증명할 수 있다. $4k+3$ 꼴의 소수가 유한하다고 하고, 이 유한한 소수들을 작은 순서대로 $p_1, p_2, p_3, ... P$라 놓자.이 때 $N=4*(p_1*p_2*p_3* ... *P)-1$라 놓으면 $N$은 $4*(p_1*p_2*p_3* ... *P-1)+3$이므로 N은 4k+3 형태의 수이다. N이 만약 소수라면 증명이 끝나고, 소수가 아니라면 $p_1, p_2, p_3, ... P$ 중 어느 것에도 해당되지 않는 4k+3 꼴의 소인수를 가지므로 증명이 끝난다.
또 한편 $4k+1$는 허수2차체 구조와 깊은 관련이 있으며, 이러한 꼴의 소수가 무한함은 위와 같이 쉽게 증명할 수 없다. 이는 해석적 정수론을 사용해 증명하는 디리클레의 정리(Dirichlet's theorem)에 의하면 참이다.

이 명제에 의하면 4k+1 꼴의 소수가 무한히 많이 존재함이 도출되며, 더 나아가 임의의 서로소 a, b에 대해 ak+b 꼴의 소수는 항상 무한히 많음을 도출 가능하다.