7의 배수판정법과 13의 배수판정법의 증명
빌드업
이 포스트에서는 진법에 대한 편의를 위해 다음과 같은 표기를 사용한다. $$ [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_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} $$ 이 $7$ 의 배수면 $[a_{n} a_{n-1} … a_{1} a_{0}]$ 도 $7$ 의 배수고, $$ a_{n} a_{n-1} a_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} $$ 이 $13$ 의 배수면 $[a_{n} a_{n-1} … a_{1} a_{0}]$ 도 $13$ 의 배수다.
설명
이게 무슨 말인가 하면, 각자리의 수를 3개씩 묶어서 교대로 더하고 빼고를 해서 나온 수가 $7$ 의 배수면 원래 수도 7의 배수라는 말이다. 예시를 보고 이해해보자.
예를 들어 $745444$ 를 보면 판정법에 의해 $$ 745-444=7 \cdot 301 $$ 로 7의 배수인데, 실제로 $745444$ 는 $745444=7 \cdot 106492$ 로 $7$ 의 배수다. 더 큰 수인 $11794545$ 를 봐도 위의 판정법은 여전히 잘 먹혀서, $$ -11+794-545 = 238 = 7 \cdot 34 $$ 는 $7$ 의 배수고 실제로도 $11794545$ 는 $11794545=7 \cdot 1684935$ 로 $7$ 의 배수다.
이 정리는 $13$ 의 경우에도 성립하고, 사실 $11$ 의 경우에도 성립한다. 그 이유는 $7$ 의 배수 판정법과 $11$ 의 배수 판정법과 $13$ 의 배수 판정법이 모두 같은 증명에서 나오기 때문이다. 숫자만 바꾸면 완전히 같은 증명이기에 $11$ 의 경우와 $13$ 의 경우는 생략하겠다.
증명
전략: 증명 자체는 아주 기본적인 테크닉만 사용되지만, 기본적으로 길기도 길고 아이디어도 필요해서 쉽지 않다. 핵심적인 아이디어로는 $1001$과 $999999$ 이 $7$ 의 배수라는 사실을 사용한다. $$ 10^{3} +1=1000+1=1001=7\cdot 143 \\ \left( 10^{3} +1 \right) \left( 10^{3} -1 \right) = 10^{6} -1=1000000-1=999999=7\cdot 142857 $$
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& [a_{n} a_{n-1} a_{n-2} ]10^{n-2} +[a_{n-3} a_{n-4} a_{n-5}]10^{n-5} +…+[a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}] \\ =& ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}]) \end{align*} $$
여기서 괄호로 묶은 부분만 보면
$$ \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) \\ &= {[a_{n} a_{n-1} a_{n-2}]10^{3} +([a_{n} a_{n-1} a_{n-2}]-[a_{n} a_{n-1} a_{n-2}])+[a_{n-3} a_{n-4} a_{n-5}]} \\ &= {([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n} a_{n-1} a_{n-2}])- ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= {[a_{n} a_{n-1} a_{n-2}]1001-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) \end{align*} $$
즉, $$ ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) $$ 이 $7$ 의 배수면 $$ [a_{n} a_{n-1} a_{n-2} a_{n-3} a_{n-4} a_{n-5}] $$ 도 $7$ 의 배수다. 이제 일반화를 해보자.
$$ \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5} -([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \end{align*} $$
여기서 $[a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5}$ 과 같은 항을 모두 $7$ 로 묶어서 $c$ 로 나타내면
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*} $$
$c$ 가 무엇이든 간에 $7c$ 는 무조건 $7$ 의 배수기 때문에 이제 뒷부분이 $7$ 의 배수면 증명이 끝난다. 그리고 여기서 $999999$ 의 성질이 쓰인다.
$$ \begin{align*} A 10^{6} &=A 10^{6} -A+A \\ &=( 10^{6} -1)A+A \\ &=999999A+A \\ &=7\cdot 142857A+A \\ &=7c+A \end{align*} $$
위 식이 성립하므로, $10$ 의 거듭제곱은 $7$ 로 나누어 떨어지는 상수항을 내놓고 차수를 $6$ 씩 줄일 수 있다.
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*} $$
위 식에서 $n-5, n-11, … ,0$ 은 모두 $6$ 의 배수이므로
$$ \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])+…+([a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}]) \end{align*} $$
따라서
$$ [a_{n} a_{n-1} a_{n-2}]- [a_{n-3} a_{n-4} a_{n-5}]+…+[a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}] $$
이 $7$ 의 배수면 $[a_{n} a_{n-1} … a_{1} a_{0}]$ 도 $7$ 의 배수다.
$1001 = 7 \cdot 143 = 7 \cdot 11 \cdot 13$ 이라는 점을 생각해보면 $11$ 이든 $13$ 이든 증명은 이미 끝난 것이나 마찬가지다.
■