logo

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

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

빌드업

이 포스트에서는 진법에 대한 편의를 위해 다음과 같은 표기를 사용한다. [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*}

정리

an−an−1+…+a1−a0a_{n} - a_{n-1} + … + a_{1} - a_{0} 이 1111 의 배수면 [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] 도 1111 의 배수다.

설명

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

증명

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

[anan−1…a1a0]≡an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100(mod11)≡an(−1)n+an−1(−1)n−1+…+a1(−1)1+a0(−1)0(mod11)≡an−an−1+an−2−…+a2−a1+a0(mod11) \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*} 즉 an−an−1+an−2−…+a2−a1+a0a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0} 이 1111 의 배수면 an−an−1+an−2−…+a2−a1+a0≡0≡[anan−1…a1a0](mod11) 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} 다시 말해, [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] 은 11의 배수다.

■