11의 배수판정법 더 간단한 증명

11의 배수판정법 더 간단한 증명

Easy proof of the 11 divisibility Rule

빌드업

이 포스트에서는 진법에 대한 편의를 위해 다음과 같은 표기를 사용한다. $$ [a_{n} a_{n-1} … a_{1} a_{0}] := a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} $$ 예를 들어 $5714$ 는 다음과 같이 나타낼 수 있다. $$ \begin{align*} [5714] =& 5000+700+10+4 \\ =& 5\cdot 10^{3} +7\cdot 10^{2} +1\cdot 10^{1} +4\cdot 10^{0} \end{align*} $$

정리

$a_{n} - a_{n-1} + … + a_{1} - a_{0}$ 이 $11$ 의 배수면 $[a_{n} a_{n-1} … a_{1} a_{0}]$ 도 $11$ 의 배수다.

설명

물론 $7$ 의 배수 판정법 $13$ 의 배수 판정법에서 주어진 수가 $7$, $11$, $13$ 의 배수인지를 판정하는 방법을 얻을 수 있지만, $11$ 의 경우에는 특히 훨씬 쉬운 결과와 간단한 증명이 있다. 다만 $7$, $11$, $13$ 의 경우와 달리 합동식을 사용하기 때문에 아주 기초적인 정수론 지식은 있어야 증명을 이해할 수 있다.

증명

전략: 증명에 쓰이는 핵심 아이디어는 바로 모듈로 $11$ 에서 $10$ 과 $-1$ 이 합동이라는 것이다. 이 힌트만 있으면 증명은 끝난 것이나 마찬가지다. $$ 10 \equiv -1 \pmod {11} $$


$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ \equiv & a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} \pmod {11} \\ \equiv & a_{n} {(-1)}^{n}+ a_{n-1} {(-1)}^{n-1}+…+ a_{1} {(-1)}^{1}+ a_{0} {(-1)}^{0} \pmod {11} \\ \equiv & a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0} \pmod {11} \end{align*} $$ 즉 $a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0}$ 이 $11$ 의 배수면 $$ a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0} \equiv 0 \equiv [a_{n} a_{n-1} … a_{1} a_{0}] \pmod {11} $$ 다시 말해, $[a_{n} a_{n-1} … a_{1} a_{0}]$ 은 11의 배수다.

댓글