logo

7의 배수판정법과 13의 배수판정법의 증명 📂정수론

7의 배수판정법과 13의 배수판정법의 증명

빌드업

이 포스트에서는 진법에 대한 편의를 위해 다음과 같은 표기를 사용한다. [anan−1…a1a0]:=an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100 [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} 예를 들어 57145714 는 다음과 같이 나타낼 수 있다. [5714]=5000+700+10+4=5⋅103+7⋅102+1⋅101+4⋅100 \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*}

정리

anan−1an−2−an−3an−4an−5+…+a5a4a3−a2a1a0 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} 이 77 의 배수면 [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] 도 77 의 배수고, anan−1an−2−an−3an−4an−5+…+a5a4a3−a2a1a0 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} 이 1313 의 배수면 [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] 도 1313 의 배수다.

설명

이게 무슨 말인가 하면, 각자리의 수를 3개씩 묶어서 교대로 더하고 빼고를 해서 나온 수가 77 의 배수면 원래 수도 7의 배수라는 말이다. 예시를 보고 이해해보자.

예를 들어 745444745444 를 보면 판정법에 의해 745−444=7⋅301 745-444=7 \cdot 301 로 7의 배수인데, 실제로 745444745444 는 745444=7⋅106492745444=7 \cdot 106492 로 77 의 배수다. 더 큰 수인 1179454511794545 를 봐도 위의 판정법은 여전히 잘 먹혀서, −11+794−545=238=7⋅34 -11+794-545 = 238 = 7 \cdot 34 는 77 의 배수고 실제로도 1179454511794545 는 11794545=7⋅168493511794545=7 \cdot 1684935 로 77 의 배수다.

이 정리는 1313 의 경우에도 성립하고, 사실 1111 의 경우에도 성립한다. 그 이유는 77 의 배수 판정법과 1111 의 배수 판정법과 1313 의 배수 판정법이 모두 같은 증명에서 나오기 때문이다. 숫자만 바꾸면 완전히 같은 증명이기에 1111 의 경우와 1313 의 경우는 생략하겠다.

증명

전략: 증명 자체는 아주 기본적인 테크닉만 사용되지만, 기본적으로 길기도 길고 아이디어도 필요해서 쉽지 않다. 핵심적인 아이디어로는 10011001과 999999999999 이 77 의 배수라는 사실을 사용한다. 103+1=1000+1=1001=7⋅143(103+1)(103−1)=106−1=1000000−1=999999=7⋅142857 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

[anan−1…a1a0]=[anan−1an−2]10n−2+[an−3an−4an−5]10n−5+…+[a5a4a3]103+[a2a1a0]=([anan−1an−2]103+[an−3an−4an−5])10n−5+…+([a5a4a3]103+[a2a1a0]) \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*}

여기서 괄호로 묶은 부분만 보면

([anan−1an−2]103+[an−3an−4an−5])=[anan−1an−2]103+([anan−1an−2]−[anan−1an−2])+[an−3an−4an−5]=([anan−1an−2]103+[anan−1an−2])−([anan−1an−2]−[an−3an−4an−5])=[anan−1an−2]1001−([anan−1an−2]−[an−3an−4an−5])=[anan−1an−2]7⋅143−([anan−1an−2]−[an−3an−4an−5]) \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*}

즉, ([anan−1an−2]−[an−3an−4an−5]) ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 이 77 의 배수면 [anan−1an−2an−3an−4an−5] [a_{n} a_{n-1} a_{n-2} a_{n-3} a_{n-4} a_{n-5}] 도 77 의 배수다. 이제 일반화를 해보자.

([anan−1an−2]103+[an−3an−4an−5])10n−5=[anan−1an−2]7⋅143⋅10n−5−([anan−1an−2]−[an−3an−4an−5])10n−5 \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*}

여기서 [anan−1an−2]7⋅143⋅10n−5[a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5} 과 같은 항을 모두 77 로 묶어서 cc 로 나타내면

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])10n−5+…+([a5a4a3]−[a2a1a0]) \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*}

cc 가 무엇이든 간에 7c7c 는 무조건 77 의 배수기 때문에 이제 뒷부분이 77 의 배수면 증명이 끝난다. 그리고 여기서 999999999999 의 성질이 쓰인다.

A106=A106−A+A=(106−1)A+A=999999A+A=7⋅142857A+A=7c+A \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*}

위 식이 성립하므로, 1010 의 거듭제곱은 77 로 나누어 떨어지는 상수항을 내놓고 차수를 66 씩 줄일 수 있다.

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])10n−5+…+([a5a4a3]−[a2a1a0]) \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,…,0n-5, n-11, … ,0 은 모두 66 의 배수이므로

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])+…+([a5a4a3]−[a2a1a0]) \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*}

따라서

[anan−1an−2]−[an−3an−4an−5]+…+[a5a4a3]−[a2a1a0] [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}]

이 77 의 배수면 [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] 도 77 의 배수다.

1001=7⋅143=7⋅11⋅131001 = 7 \cdot 143 = 7 \cdot 11 \cdot 13 이라는 점을 생각해보면 1111 이든 1313 이든 증명은 이미 끝난 것이나 마찬가지다.

■