합동식과 배수의 판정

$\displaystyle x$와 $\displaystyle a$는 $\displaystyle m$으로 나눈 나머지가 같을 때, $\displaystyle x\equiv a(\mathrm{mod}\, m)$라고 쓰고 '법 $\displaystyle m$에 대하여 $\displaystyle x$는 $\displaystyle a$와 합동이다.'라고 읽는다.e.g. $\displaystyle 5\equiv2(\mathrm{mod}\, 3)$, $\displaystyle 5\equiv-1(\mathrm{mod}\, 3)$

수학경시대회를 준비할 때 배우는 내용이지만, 제시문에 주어지기도 한다. 제시문에 주어져있지 않을 때는 위 내용을 답안 맨 앞에 써주고 풀이에 활용하면 번거로운 반복적인 수식 표현을 줄일 수 있다.

● 사칙 연산과 합동식

합과 곱의 경우 그대로 나머지끼리 연산할 수 있고, 몫의 경우만 주의한다.$\displaystyle \begin{aligned} & x\equiv a(\mathrm{mod}\, m),\ y\equiv b(\mathrm{mod}\, m)\text{ 일 때} \\ & kx\equiv ka(\mathrm{mod}\, m) \\ & x\pm y\equiv a\pm b(\mathrm{mod}\, m) \\ & xy\equiv ab(\mathrm{mod}\, m) \\ & \frac{x}{y}\not\equiv\frac{a}{b}(\mathrm{mod}\, m)\text{(단, }b\ne0\text{)} \end{aligned}$

● 중국인의 나머지 정리(Chinese Remainder Theorem)

$\displaystyle i\ne j$이면 $\displaystyle \gcd(m_{i},m_{j})=1$을 만족하는 $\displaystyle m_{i}$에 대하여연립합동식 $\displaystyle x\equiv a_{i}(\mathrm{mod}\, m_{i}) (i=1,2,3,\cdots,n)$는 법 $\displaystyle \prod_{i=1}^{n}m_{i}$에 대하여 유일한 근을 갖는다.

● 배수의 판정

일반적인 자연수 $\displaystyle N$이 $\displaystyle n$자리일 때 각 자리의 수를 $\displaystyle a_{k}(0\le k\le n-1)$라 하면$\displaystyle N=\sum_{k=0}^{n-1}a_{k}10^{k}$라고 표현할 수 있다.

이 때,$\displaystyle N\equiv a_{0}(\mathrm{mod}\, 2,\ 5),\quad N\equiv a_{1}\times10+a_{0}(\mathrm{mod}\, 2^{2},\ 5^{2}),\quad\cdots$$\displaystyle N\equiv\sum_{k=0}^{n-1}a_{k}(\mathrm{mod}\, 3,\ 9),\quad N\equiv\sum_{k=0}^{n-1}a_{k}(-1)^{k}(\mathrm{mod}\, 11)$임을 알 수 있다.

이와 중국인의 나머지 정리의 원리를 이용해 웬만한 자연수의 배수들은 빠르게 판정할 수 있다.