"어떤 양의 정수 N을 생각해 보자. 이 정수의 모든 자리수 숫자를 더한다. 결과가 여전히 2자리 수 이상이면 1자리가 될 때까지 더한다. 예를 들면, 75298 -> 31 -> 4, 이런 식으로. 그럼 이 결과 숫자 4는 원래 정수 N을 9로 나눈 나머지가 된다. (결과가 9가 나오면 N%9 = 0이 된다.)" 예쁘게 증명하고 나시면 생각해 볼 추가문제. 왜 하필 9일까? 비슷한 방법으로 8이나 7로 나눈 나머지는 구할 수 없을까? 11로 나눈 나머지를 구할 순 없을까?
큰 숫자를 9로 실제로 나누어 보지 않고, 각 자리 숫자를 계속 반복해서 더하는 것만으로 나머지를 알 수 있다니, 신기하지 않은가? 실제로 75,298을 9로 나누면 몫(quotient)은 8,366이고, 나머지는 4이다. 각자리 숫자를 반복해서 더하면,
어떻게 저 모양으로 만들 수 있을까? 아까 기억해 두었던 포인트를 떠올려 보면, \textcolor{red}{7} 은 10000개 중에서 9999개 남겨놓고 하나를 빼 오면 된다. \textcolor{green}{5} 는 1000개 중에서 999개 남기고 하나를 빼 오면 되고, \textcolor{blue}{2} 는 99개 남기고 하나 가져오고 \textcolor{brown}{9}는 9개 남기고 하나 가져오고, \textcolor{purple}{8} 은 그냥 가져 오면 된다.
이제 모양이 다 나왔다. 75298과 정확하게 같은 값을 방식만 바꾸어서 나타내었는데, 앞부분은 모두 9로 묶이기 때문에 9로 나누었을 때의 나머지를 0으로 만들어버리므로 뒷부분의 값 \textcolor{red}{7} +
\textcolor{green}{
5} +\textcolor{blue}{
2} +\textcolor{brown}{
9} +\textcolor{purple}{
8} , 즉, 각 자릿수를 모두 합한 값을 9로 나눈 나머지가 원래 숫자의 나머지와 같아진다. 이 과정은 합한 숫자가 한자리 숫자가 될 때까지 같은 방식으로 반복할 수 있다. 그래서 굳이 9로 나누지 않아도 각자리 숫자를 한자리 숫자가 될때까지 계속 더해서 나온 최종 값이 9로 나눈 나머지가 된다.
증명
1 의 자리 숫자를 a_0, 10 의 자리 숫자를 a_1, 같은 방식으로 10^n 자리 숫자를 a_n 이라고 하자. 예를 들어 4354 라는 숫자가 있으면 a_3=4, a_2=3, a_1=5, a_0=4 이 되고 \underlinesegment{a_3a_2a_1a_0} 으로 표현할 수 있다고 하자. 일반적인 n 자리 숫자는 다음과 같이 나타낼 수 있다.
\begin{aligned}\underlinesegment{a_n a_{a-1} \cdots a_1 a_0}=&10^na_n+10^{n-1}a_{a-1}+\cdots+10a_1+a_0\\
=&\underbrace{\overbrace{99\cdots9}^{n\text{개}}a_n+\overbrace{99\cdots9}^{n-1\text{개}}a_{n-1}+\cdots+9a_1}_{\text{9로 나누면 0이 되는 부분}}\\
&+\underbrace{a_n+a_{n-1}+\cdots+a_2+a_1+a_0}_{\text{각 자릿수의 합}}\end{aligned}
그러므로 원래 숫자를 9로 나눈 나머지는 각 자릿수의 합을 9로 나눈 나머지와 같다. 일반적인 n자리 숫자에 대해서 모두 위와 같이 표현이 가능하기 때문에, 각자리 숫자의 합이 두 자리 이상이 나왔다면 그 결과에 같은 방법을 또 적용해도 그렇게 구한 나머지가 원래 숫자를 9로 나눈 나머지와 같다.
좀 더 빠른 계산
위 증명에서도 보았듯이 9로 나눈 나머지만 구하는 문제에서 우리가 취하는 전략은 9로 나누어 떨어질 부분을 찾아내서 없애버리는 것이다. 각 자리 숫자를 합하는 중에도 9의 배수가 되는 부분을 만날 수 있다. 그런 경우 그 부분을 다 없애고 계산을 하면 좀 더 머리가 편하게 계산할 수 있다. 그럼 전략(strategy) 왜 괄호 안에 뜬금없는 영어단어를 넣는지 궁금하신 분을 위해: 이 블로그 대부분의 글은 제 아이들(한국에서 나서 미국에서 자랐죠)을 대상으로 쓴 글입니다. 그래서 안 접해본 것 같은 단어는 옆에 영어 뜻을 써 놓았습니다. 을 한 번 세워 볼까?
9495298 을 9로 나눈 나머지는?
9+4+9+5+2+9+8 을 9로 나눈 나머지와 같다는 건 이제 알겠다. 하지만 9라는 숫자는 더하든 더하지 않든 나머지값을 바꾸지 않으니 (9로 나누었을 때 나머지가 0이니까) 굳이 9를 더해가며 머리를 아프게 할 필요가 있을까? 더하다가 9가 보이면 건너 뛰자.
\cancel94\cancel952\cancel98 를 9로 나눈 나머지는 4+5+2+8 를 9로 나눈 나머지와 같다. 이제 머리가 좀 상쾌해진 것 같다. 하지만 여기서 더 할 수 있다. 9만 빼고 더하기만 하는 게 아니라 더하다가 9 이상이 되면 그 즉시 나머지를 찾아내서 나머지만 더하는 것이다.
이런 방식이 좀 익숙해지면 이제 앞에서 부터 순서대로 더해가면서 9를 없애고, 9로 나눈 나머지만 더하는 것이 아니라, 숫자가 한 눈에 들어와서 9를 미리 없애고 계산하기 쉬운 순서대로 더하면서 나머지만 남기고 계산해 나갈 수 있게 된다. 이 즈음 되면 9로 나눈 나머지 구하기 마스터라고 해도 되겠다.
왜 하필 9로 나눈 나머지만 되는가?
위 증명에서 보듯이, 10의 거듭제곱에서 1개를 제외한 숫자 (예를 들어, 999나 99999 등)가 모두 9의 배수가 되기 때문에 이것이 가능해진다.
하나 알아둘 것은
3으로 나눈 나머지도 같은 방식으로 가능하다.
라는 것이다. 9의 배수는 3의 배수이기도 하기 때문에, 9의 배수인 부분을 3으로 나눈 나머지는 0이 되고, 따라서 각 자리 숫자의 합을 3으로 나눈 나머지가 원래 숫자를 3으로 나눈 나머지와 같다.
좀 더 빠른 계산을 하는 방식도 비슷하다. 3, 6, 9와 같이 명백하게 3의 배수가 되는 자릿수를 건너뛰고, 각 자릿수를 더하면서 3이 넘어가면 미리 나머지 계산을 하면서 더해 나간다. 숙달이 되면 건너뛸 숫자가 눈에 더 들어 올 것이다. 예를 들어, 3, 6, 9 뿐만 아니라, (5, 7)이나 (8, 4)와 같이 합하여 3의 배수가 되는 숫자 짝이나 숫자 서너개(8, 2, 2 와 같은 것)도 눈에 들어와서 한꺼번에 건너뛸 수 있게 된다. 또한 매번 더하면서 나머지 연산을 하는 것보다 숫자가 어느정도 커질 때까지는 그냥 더하기만 하는 것이 계산 횟수가 적어서 더 좋기 때문에, 하다보면 자신에게 편한 방식으로 익숙해지게 된다. 예를 들어 \textcolor{red}{8}\textcolor{blue}{2} 가 있으면 \textcolor{red}{8} 을 3으로 나눈 나머지 2에다가, \textcolor{blue}{2} 를 더해서 4로 만든 다음, 그것을 다시 3으로 나눈 나머지를 구해서 나머지가 1이 되는 것을 알아내는 것이 아니라, 8+2를 해서 10을 만든 다음 3으로 나눈 나머지 1을 찾아내는 식이다.
다른 숫자로 나눈 나머지
8은 비슷하게 안 되나요? 각 숫자를 두번씩 더해서 한다던가 하면?
각 자리 숫자를 두 번씩 빼내면, 십의 자리는 8이 되겠지만, 100의 자리는 98이 된다(88이 아니고..), 1000의 자리는 998이 되니 역시 8의 배수가 아니다. 그러니 각 자리 숫자를 두 번씩 더하는 방식으로는 할 수가 없다.
그렇다면 방법이 없느냐... 8은 다른 방식으로 한다. 8로 나눈 나머지를 구하기 전에 2로 나눈 나머지, 5로 나눈 나머지, 4로 나눈 나머지에 대해서 먼저 알아보자.
2로 나눈 나머지
직관적으로 짝수(even number)이면 2로 나눈 나머지가 0이고, 홀수 (odd number)이면 2로 나눈 나머지가 1이다. 이렇게 직관적인 걸 왜 하나 싶겠지만, 8로 나누었을 때의 나머지를 구하는 것과 원리가 같으니 가장 쉬운 것 부터 시작해 보는 것이다.
10 = 2\times 5 라는 사실을 기억해 두자.
모든 자연수를 1의 자리와 그 이외의 자리로 나눌 수 있는데, 예를 들어 4,322는 다음과 같이 나타낼 수 있다.
1의 자리를 제외한 부분이 10의 배수이므로 동시에 2의 배수가 되고, 그래서 2로 나눈 나머지는 0이 된다. 그러므로 1의 자리 이외의 자리는 무시하고, 1의 자리만 생각하면 되는 것이다. 그래서 다른 것 볼 필요없이 끝자리만(1의 자리)만 보고 짝수인지 홀수 인지 판단할 수 있다.
5로 나눈 나머지
2로 나눈 나머지를 구하는 것과 동일한 원리이다. 10=2\times5 이므로 10의 배수는 5의 배수이기도 하다. 따라서 1의 자리를 제외한 숫자는 5의 배수가 되니 다 무시하고 끝자리(1의자리)만 보고 5로 나눈 나머지를 찾아낼 수 있다.
4로 나눈 나머지
100 = 4\times 25 을 이용한다. 숫자의 마지막 두 자리와 그 외의 자릿수로 나누어 표현하면 마지막 두 자리를 제외한 부분은 100의 배수이고, 100의 배수는 4의 배수이기 때문에 나머지를 찾아낼 때는 무시(건너뛰기)하면 된다. 그래서 끝자리 두 자리만 4로 나누어서 4의 배수인지 찾아내면 된다. 예를 들어 4322는 다음과 같이 나타낼 수 있다.
