11 배수 판정법 - 11 baesu panjeongbeob

나머지 구하는 법을 배우고 나서도 7, 13으로 나눈 나머지를 구하는 과정은 좀 까다로웠을 것이다. 그래도 기억해 놓도록 하자. 이 글에서 나누어 떨어지는 경우에 쓸 수 있는 더 쉬운 방법을 알아볼 테지만, 앞서 배운 3자리씩 끊어서 더하고 빼는 방식을 섞어서 쓰면 큰 숫자에 대해서 더 효율적으로 확인할 수 있게 되니 알아두면 요긴하다. 

각설하고, 주어진 숫자가 7, 11, 13으로 나누어 떨어지는 지만 확인하려면 이렇게 하면 된다. 방법이 셋 다 비슷하다는 것에 놀란다.

7로 나누어 떨어지는 지 확인하는 법

맨 마지막 자리를 제외한 숫자에다가 맨 마지막 자리를 2배한 숫자를 뺀다. 그 숫자가 7의 배수, 즉 7로 나누어 떨어지면, 원래 숫자도 7의 배수이다. 이것은 계속 반복해도 되기 때문에 한 눈에 7의 배수가 보일 때까지 계속 반복하면 된다.

11로 나누어 떨어지는 지 확인하는 법

맨 마지막 자리를 제외한 숫자에다가 맨 마지막 자리의 그 숫자를 뺀다. 그 숫자가 11의 배수이면 원래 숫자도 11의 배수이다. 이것은 계속 반복해도 되기 때문에, 한 눈에 11의 배수가 보일 때까지 계속 반복하면 된다.

13으로 나누어 떨어지는 지 확인하는 법

맨 마지막 자리를 제외한 숫자에다가 맨 마지막 자리의 숫자를 4배한 숫자를 더한다. 그 숫자가 13의 배수이면 원래 숫자도 13의 배수이다. 이것은 계속 반복해도 되기 때문에, 한 눈에 13의 배수가 보일 때까지 계속 반복하면 된다.

왜 이렇게 되나?

바로 설명 시작하기 전에 힌트로 시작해 보자. 이것만 가지고 저렇게 되는 법을 알 수 있을까?

 20 = 3 \times 7 -1 

 10 = 11 - 1 

 40 = 3\times 13 + 1 

뭔가 알 것 같으면 스크롤을 멈추고, 공책을 꺼내서 써 보자 :)

7의 배수 판별법 증명

문자로(대수적으로) 증명하기 전에 숫자 예제로 먼저 해 보자. 첫 번째 예제 2275는 2\times 1000 + 2\times 100 + 7 \times 10 + 5 로 나타낼 수 있다. 이 숫자가 정말로 7의 배수라면 7 \times \text{something} 형태로 나올 것이다. something이라고 길게 쓰면 잉크가 아깝기 때문에 k라고 줄여 쓰면,

 \begin{aligned}2\times1000+2\times100+7\times10+5&=7k\\ 2\times1000+2\times100+7\times10+5 - 5\times21&=7k-5\times21\\ 2\times1000+2\times100+7\times10 - 5\times20&=7k-5\times21\\ 10\times(\underbrace{2\times100+2\times10+7 -5\times2}_A)&=\underbrace{7k-5\times3\times7}_\text{7의 배수}\end{aligned}  

10에다가 무언가를 곱한 것이 7의 배수가 된다는 게 무슨 말일까? 그 무언가를 위에서 처럼 A라고 하자. 7과 10은 서로소(coprime, 공약수가 1외에는 없는 두 숫자)이기 때문에, 10 안에는 7의 배수가 될 만한 게 있을 수가 없으니, A가 7의 배수가 되어야만 10 곱하기 A가 7의 배수가 된다. 그러므로 2\times 100 + 2\times10 + 7 - 5\times2 가 7의 배수이다. 말로 풀면, 원래 숫자의 마지막 자리를 뺀 숫자( 227 )에서 마지막 자리 숫자의 두 배 ( 5\times2 ) 를 뺀 숫자가 7의 배수가 된다는 이야기이다.

이제 이것을 문자를 도입해서 일반화해 보겠다. 일의 자리 숫자를 a_0 십의 자리 숫자를 a_1 , 그런 식으로 해서 10^n 자리 숫자를 a_n 이라고 하자. 그러면 주어진 자연수는 다음과 같이 나타낼 수 있다.

 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0 

 예를 들어 앞에서 든 예제인 2275라면, a_3=2, a_2=2, a_1=7, a_0=5 이므로 다음과 같이 쓸 수 있을 것이다.

 10^3\times2+10^2\times2+10^1\times7+5   

다시 원래 일반식으로 돌아가서, 아까 쓴 트릭에 가까운 전개과정을 한 번 적용해 보겠다. 원래 숫자가 7의 배수라면 그 숫자의 마지막 자리, 즉 1의 자리의 값 a_0 을 21번 빼준 것도 7의 배수이다. 왜냐하면 21이 7의 배수이므로 a_0\times21 도 7의 배수이고, 원래 숫자가 7의 배수라면 거기에 7의 배수인 a_0\times21 을 빼도 7의 배수이기 때문이다. 이것을 정리하면 다음과 같이 된다.

 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0=\underbrace{7k}_\text{7의 배수} 

 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0-21a_0=\underbrace{7k-21a_0}_\text{역시 7의 배수}  

그런데 신기한 일은 좌변(left side)에서 일어난다. 원래 자연수에서 일의자리를 뺀 나머지는 10의 배수이다. 일의자리가 0일 때에만 전체 숫자가 10의 배수가 되는데, 원래 1의 자리숫자 a_0 에서 21a_0 을 빼면, -20a_0 이 되므로 1의 자리가 사라진다. 십의 자리만 원래 값보다 2가 줄어들게 된다.

 \underbrace{10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1-20a_0}_\text{10의 배수}=\underbrace{7k-21a_0}_\text{역시 7의 배수}  

 10\times(\underbrace{10^{n-1}a_n+10^{n-2}a_{n-1}+\cdots+a_1-2a_0}_\text{1의 자리를 제외한 숫자에서 1의자리의 두배를 뺀 값})=\underbrace{7k-21a_0}_\text{역시 7의 배수}  

좌변을 10으로 묶으면 남는 모양이 원래 숫자에서 1의자리를 제외하고 만든 숫자에다가 1의자릿값의 두 배를 뺀 값이 된다. 10에다가 그 숫자를 곱해서 7의 배수가 된다는 것은 그 숫자가 7의 배수가 될 때만 가능하다. 그러므로 1의 자리를 제외한 숫자에서 1의 자릿값의 두 배를 뺀 값이 7의 배수이면, 원래 숫자도 7의 배수이다.

다 써 놓은 게 눈 앞에 있으면 어떻게 따라가기는 하겠는데, 애초에 저런 증명은 어떻게 만드는 건가요?

음.. 라마누잔이 아니고서야, 문제를 보자마자 짠 하고 나오기는 힘든 노릇이다. 일단 종이에다가 연필로 몇 가지 예제를 끄적거려 보는 게 처음으로 할 일이고, 두 번째로는 말로 설명된 것을 문자로 나타내는 게 중요하다. 사실 7의 배수 판별법의 증명은 7의 배수 판별법 자체를 대수로 나타내는 것으로부터 증명이 나아가야 하는 방향을 거의 다 잡을 수 있다.

"어떤 자연수가 7의 배수인 것을 판별하려면 그 자연수의 일의 자릿수를 제외한 숫자에서 일의 자릿수의 2배를 뺀 숫자가 7의 배수인지 판별하면 된다."

라는 문장을 하나하나 뜯어서 대수적으로 나타내어 보자.

"어떤 자연수가 7의 배수이다" \Longleftrightarrow 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0=7k 

"그 자연수에서 1의자리 빼고 나머지 부분으로 만든 숫자에 1의자리 2배를 뺀 숫자가 7의 배수이다" \Longleftrightarrow 10^{n-1}a_n+10^{n-2}a_{n-1}+\cdots+a_1-2a_0=7l 

우리가 증명하고 싶은 것은 (1)이랑 (2)가 같은 말이라는 것이다. 여기까지 써 놓고 출발하는 것이다. 그러면 증명 방향이 눈에 보인다. (2)식에다가 양변에 10배를 하면 (1)식이랑 상당히 비슷해지는 것을 알 수 있다.

 10^{n}a_n+10^{n-1}a_{n-1}+\cdots+10a_1-20a_0=70l 

 차이를 보면 (1)식은 a_0 로 끝나는데 (2) 식은 -20a_0 로 끝난다는 것이다. (1)식에서 21a_0 를 빼서 (2)가 만들어졌다는 것을 여기서 알 수 있다. 그리고 그것을 아는 순간, 21이 7의 배수니까,  21a_0 를 빼도 원래 숫자가 7의 배수라면 여전히 7의 배수가 된다는 걸 알 수 있게 된다. 

배수 판별법을 써 놓고 그걸 증명하는 건 고민해서 한다고 쳐요. 배수 판별법 자체는 어떻게 만든 거죠?

좋은 질문이다. 배수 판별법을 증명하는 것 보다 배수 판별법 자체를 만드는 데 더 비상한 아이디어가 필요하다. 이건 어떻게 만든 걸까? 

앞에 힌트로 주었던 것을 포함해서 중요한 단서를 나열해 보면

1. 원래 숫자에서 7의 배수를 더하거나 뺀 숫자를 7로 나눈 나머지는 원래 숫자를 7로 나눈 나머지와 같다.

2. 일의 자리 a_0 를 없애고 싶으면, a_0 를 빼든지, 11a_0 를 빼든지, 21a_0 를 빼든지 31a_0 를 빼든지, ..., 더해서 없애고 싶으면 9a_0 를 더하든지 19a_0 를 더하든지 29a_0 를 더하든지...

이제 단서 1과 2를 동시에 만족하는 것은? 21a_0 를 빼는 것이다. 7의 배수를 빼는 것이면서 동시에 1의 자리를 없애버릴 수 있으니 말이다.

11의 배수 판별법 증명

1. 원래 숫자에서 11의 배수를 빼거나 더해서 만든 숫자를 11로 나눈 나머지는 원래 숫자를 11로 나눈 나머지와 같다.

2. 마지막 자리 a_0 를 없애고 싶으면, a_0 를 빼든지, 11a_0 를 빼든지, 21a_0 를 빼든지, 31a_0 를 빼든지, ..., 더해서 없애고 싶으면  9a_0 를 더하든지 19a_0 를 더하든지 29a_0 를 더하든지... 

단서 1과 2를 동시에 만족하는 것은 11a_0 빼는 것이다.

 \begin{aligned}10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0&=\underbrace{11k}_\text{11의 배수}\\ 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0-11a_0&=\underbrace{11k-11a_0}_\text{11의 배수}\\ 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1-10a_0&=\underbrace{11k-11a_0}_\text{11의 배수}\\ 10\times\underbrace{(10^{n-1}a_n+10^{n-2}a_{n-1}+\cdots+a_1-a_0)}_\text{1의 자리를 제외한 숫자에서 1의 자리를 뺀 수}&=\underbrace{11k-11a_0}_\text{11의 배수}\end{aligned} 

 10과 11은 서로소이기 때문에 "1의 자리를 제외한 숫자에서 1의 자리를 뺀 수"가 11의 배수가 아니고서는 윗 식이 성립할 수가 없다. 그러므로 "1의 자리를 제외한 숫자에서 1의 자리를 뺀 수"가 11의 배수인지 확인해서 원래 숫자가 11의 배수인지 확인할 수 있다.

13의 배수 판별법 증명

1. 원래 숫자에서 13의 배수를 빼거나 더해서 만든 숫자를 13으로 나눈 나머지는 원래 숫자를 13으로 나눈 나머지와 같다.

2. 마지막 자리 a_0 를 없애고 싶으면, a_0 를 빼든지, 11a_0 를 빼든지, 21a_0 를 빼든지, 31a_0 를 빼든지, ..., 더해서 없애고 싶으면 9a_0 를 더하든지 19a_0 를 더하든지 29a_0 를 더하든지...

단서 1과 2를 동시에 만족하는 것은 39a_0 를 더하는 것이다.

 \begin{aligned}10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0&=\underbrace{13k}_\text{13의 배수}\\ 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0+39a_0&=\underbrace{13k+39a_0}_\text{13의 배수}\\ 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+40a_0&=\underbrace{13k+39a_0}_\text{13의 배수}\\ 10\times\underbrace{(10^{n-1}a_n+10^{n-2}a_{n-1}+\cdots+a_1+4a_0)}_\text{1의 자리를 제외한 숫자에서 1의 자릿수의 4배를 더한 수}&=\underbrace{13k+39a_0}_\text{13의 배수}\end{aligned}  

10과 13은 서로소이므로, "1의 자리를 제외한 숫자에서 1의 자릿수의 4배를 더한 수"가 13의 배수가 아니고서는 윗 식이 성립할 수 없다. 그러므로 "1의 자리를 제외한 숫자에서 1의 자릿수의 4배를 더한 수"가 13의 배수인지 확인해서 원래 숫자가 13의 배수인지 확인할 수 있다.

마치며

배수 판별법은 그 자체는 간단하고, 실제로 유용하기 때문에 많이 익혀두고 쓰는 방식이다. 하지만 왜 그렇게 되는지 모른 채로 쓰는 건 마음이 편하지 않으니까, 원래 이렇게까지 증명하려는 게 아니었건만 여기까지 왔다. 이런데 흥미가 매우매우 느껴진다면, 정수론(number theory)에 있는 몇 가지 재미있는 주제로 건너가도 괜찮겠다.

증명이 끝났으니 다음 글에서는 배수 판별법을 모아 정리해 보겠다.