$\DeclareMathOperator{\rem}{rem}\newcommand\mycancel[1]{\mypink{\cancel{\myblack{#1}}}}$배수 판정법(divisibility rule)은 주어진 정수 $N$이 또 다른 정수 $m$ 배수인지의 여부를 간단히 확인하는 일련의 절차를 말한다. 일반적으로 배수 판정법은 정수론의 다양한 결과를 이용함으로써 $N$보다 훨씬 작은 수가 $m$의 배수인지를 인지의 여부를 판단하여 $N$이 $m$의 배수인지의 여부를 판정할 수 있게 해준다.
$ $
$7$을 제외한 $2$, $3$, $4$, $5$, $6$, $8$, $9$의 배수 판정법은 다음과 같다.
- $2$의 배수 판정법 : $N$의 일의 자리가 $0$, $2$, $4$, $6$, $8$이면 $N$은 $2$의 배수이다.
- $3$의 배수 판정법 : $N$의 각 자리 수의 합이 3의 배수이면 $N$ 또한 $3$의 배수이다.
- $4$의 배수 판정법 : $N$의 오른쪽 끝 두 자리 수가 $4$의 배수이면 $N$ 또한 $4$의 배수이다.
- $5$의 배수 판정법 : $N$의 일의 자리가 $0$ 또는 $5$이면 $N$은 $5$의 배수이다.
- $6$의 배수 판정법 : $N$이 $2$의 배수이면서 동시에 $3$의 배수이면 $N$은 또한 $6$의 배수이다.
- $8$의 배수 판정법 : $N$의 오른쪽 끝 세 자리 수가 $8$의 배수이면 $N$은 $8$의 배수이다.
- $9$의 배수 판정법 : $N$의 각 자리 수의 합이 $9$의 배수이면 $N$ 또한 $9$의 배수이다.
예를 들어, $N = 3,145,927,680$은 오른쪽 끝 세 자리 수 $680$이 $8$의 배수이므로 $N$ 또한 $8$의 배수이고, 각 자리 수의 합이 $45$이므로 $N$은 $9$의 배수이다. 따라서 $N$은 $2$, $3$, $4$, $6$, $8$, $9$의 배수가 됨을 알 수 있다. 또한 $N$의 일의 자리 수가 $0$이므로 $5$의 배수인 것도 분명하다. 그렇다면 $7$은 어떨까? 이 수가 $7$의 배수인지 아닌지 직접 나누어 보지 않고 알 수 있는 방법은 없을까? 이번 글에서는 다양한 $7$의 배수 판정법과 그 증명을 정리해서 소개해 보고자 한다.
$ $
주어진 정수 $N,\, m \in \Z$에 대하여, $\rem(N,\, m)$을 $N$을 $m$으로 나누었을 때의 나머지, 즉, 적당한 정수 $q$에 대하여 \[ N = mq + \rem(N,\, m), \quad 0 \leq \rem(N,\, m) < m \] 을 만족하는 유일한 양의 정수로 정의하자. 그러면 $N$이 $m$의 배수인 것과 $\rem(N,\, m) = 0$인 것은 서로 동치이다.
$ $
$ $
위에서 소개했던 $2$, $3$, $4$, $5$, $6$, $8$, $9$의 배수 판정법은 모두 강한 배수 판정법이다.
$ $
앞으로 설명할 다양한 $7$의 배수 판정법들의 증명 과정에서, 양의 정수 $N \in \N$을 표현하는 다음 두가지 표기법을 증명의 편의에 따라 자유롭게 혼용해서 사용할 것이다. \[ \begin{align*} N & = \overline{a_n \cdots a_3 a_2 a_1 a_0 \!} \\[5px] & = a_0 + 10 a_1 + 10^2 a_2 + 10^3 a_3 + \cdots + 10^n a_n. \\[5px] \end{align*} \] 여기서 $a_k$는 $N$을 $10^k$로 나누었을 때의 나머지, 즉, $a_k = \rem(N,\, 10^k)$이다. 또한 두 정수 $a,\, b$가 법(modulo) $k$에 대해서 합동일 때, 다시 말해 $\rem(a,\, k) = \rem(b,\, k)$가 성립할 때, $a \equiv_k b$이라는 표현을 사용할 것이다.
$ $
$ $
증명. $N = 10A + b$로 나타내자. (즉, $b$는 $N$의 일의 자리 수, $A$는 일의 자리를 제외한 나머지 수이다.) 그러면 $f(N) = A - 2b$임을 알 수 있다. 먼저 다음 합동식이 성립함을 확인하자. \[ 5N = 5 (10A + b) = 50A + 5b \equiv_7 A + 5b \equiv_7 A - 2b = f(N). \] 이제 $5$와 $7$이 서로소라는 사실로부터, $5N \equiv_7 0$인 것과 $N \equiv_7 0$인 것은 서로 동치이므로 증명이 완료된다.$ $
$ $
예제. $N = 3,145,927,680$이 $7$의 배수인지를 스펜스의 방법을 이용하여 확인해 볼 것이다. 주어진 $N$에 스펜스의 방법 또는 치카의 방법을 충분히 반복 적용하여 $7$의 배수를 간단히 확인할 수 있는 수 $f^{k}(N)$을 구하는 것이 목표이다. \[ \begin{array}{clc} & 314592768\!\mycancel{0} & \\ \hline & 31459276\!\mycancel{8} & \\ - \; \smash{\big)} & \phantom{000000}16 & \\ \hline & 3145926\!\mycancel{0} & \\ \hline & 314592\!\mycancel{6} & \\ - \; \smash{\big)} & \phantom{0000}12 & \\ \hline & 31458\!\mycancel{0} & \\ \hline & 3145\!\mycancel{8} & \\ - \; \smash{\big)} & \phantom{00}16 & \\ \hline & 312\!\mycancel{9} & \\ - \; \smash{\big)} & \phantom{0}18 & \\ \hline & 29\!\mycancel{4} & \\ - \; \smash{\big)} & \phantom{0}8 & \\ \hline & 21 & \\ & & \\ & & \end{array} \qquad \qquad \begin{array}{clc} & 314592768\!\mycancel{0} & \\ \hline & 31459276\!\mycancel{8} & \\ + \; \smash{\big)} & \phantom{000000}40 & \\ \hline & 3145931\!\mycancel{6} & \\ + \; \smash{\big)} & \phantom{00000}30 & \\ \hline & 314596\!\mycancel{1} & \\ + \; \smash{\big)} & \phantom{00000}5 & \\ \hline & 31460\!\mycancel{1} & \\ + \; \smash{\big)} & \phantom{0000}5 & \\ \hline & 3146\!\mycancel{5} & \\ + \; \smash{\big)} & \phantom{00}25 & \\ \hline & 317\!\mycancel{1} & \\ + \; \smash{\big)} & \phantom{00}5 & \\ \hline & 32\!\mycancel{2} & \\ + \; \smash{\big)} & 10 & \\ \hline & 42 & \end{array} \] 위에서 구한 $21$과 $42$ 모두 $7$의 배수이므로, 원래 수인 $N$ 또한 $7$의 배수임을 알 수 있다.
$ $
한 편, 치카의 방법은 아래와 같은 방법으로 더욱 계산을 간소화 할 수 있다.
- $N$의 일의 자리 수를 다섯 배 하여 바로 왼쪽 수 (십의 자리 수)와 더해준 뒤, 계산 결과를 바로 아래에 적어준다.
- 위에서 구한 수의 일의 자리수를 다섯 배 하여 그 수의 십의 자리수와 더한 후, $N$의 그 다음 왼쪽 수 (백의 자리 수)와 더해준 뒤, 계산 결과를 바로 아래에 적어준다.
- $N$의 가장 왼쪽 수의 아래쪽에 계산 결과를 적게될 때까지 위 과정을 반복한다. 이 때, $N$의 아래쪽에 씌여 지는 수가 치카의 방법으로 구하는 $f(N)$의 값이 된다.
위 표기법을 이용하여 $N = 3,145,927,680$에 대하여 치카의 방법을 적용하면 다음 결과를 얻는다. \[ \begin{array}{cccccccccccc} & 3 & 1 & 4 & 5 & 9 & 2 & 7 & 6 & 8 & 0 & \\ \hline & 14 & 12 & 12 & 31 & 15 & 11 & 41 & 46 & 8 & & \\ \end{array} \] (예를 들어 위 식에서 계산된 $41$의 경우, 그 오른쪽 수인 $46$의 일의 자리 수의 다섯배와 십의 자리 수의 합에, $N$의 그 다음 왼쪽 수인 $7$을 더한 값, 즉 \[6 \times 5 + 4 + 7 = 41 \] 와 같이 구해진다.) 위 식의 두번째 줄 가장 오른쪽 수인 $14$는 $7$의 배수이므로, 원래의 수 $N$ 또한 $7$의 배수이다. 또한 이번 예제의 초반에 치카의 방법으로 구한 $f(N) = 42$에 치카의 방법을 한 번 더 적용하면 $f(42) = 14$가 나옴을 확인하자. 이 수는 표기를 간략화한 치카의 방법에서 구한 수와 동일하다.$ $
$ $
위 증명에서 $50 \equiv_7 1$이라는 사실이 중요 아이디어임을 알 수 있다. 위 방법을 응용하여 $400 \equiv_7 1$이라는 사실로부터 다음과 같은 형태의 $7$의 배수 판정법을 만들 수 있다.
$ $
$ $
증명. $N = 100A + b$로 나타내자. (즉, $b$는 $N$의 오른쪽 끝 두 자리의 수, $A$는 두 자리를 제외한 나머지 수이다.) 그러면 $f(N) = A - 3b$임을 알 수 있다. 먼저 다음 합동식이 성립함을 확인하자. \[ 4N = 4 (100A + b) = 400A + 4b \equiv_7 A + 4b \equiv_7 A - 3b = f(N). \] 이제 $4$와 $7$이 서로소라는 사실로부터, $4N \equiv_7 0$인 것과 $N \equiv_7 0$인 것은 서로 동치이므로 증명이 완료된다.$ $
$ $
예제. $N = 3,145,927,680$에 대하여 위 방법을 반복해서 적용하면, \[ \begin{array}{clc} & 31459276\!\mycancel{80} & \\ - \; \smash{\big)} & \phantom{00000}240 & \\ \hline & 314590\!\mycancel{36} & \\ - \; \smash{\big)} & \phantom{000}108 & \\ \hline & 3144\!\mycancel{82} & \\ - \; \smash{\big)} & \phantom{0}246 & \\ \hline & 2898 \end{array} \qquad \qquad \begin{array}{clc} & 31459276\!\mycancel{80} & \\ - \; \smash{\big)} & \phantom{00000}320 & \\ \hline & 314595\!\mycancel{96} & \\ - \; \smash{\big)} & \phantom{000}384 & \\ \hline & 3149\!\mycancel{79} & \\ - \; \smash{\big)} & \phantom{0}316 & \\ \hline & 3465 \end{array} \] 위에서 구한 $2898$과 $3465$ 모두 $7$의 배수이므로, 원래 수인 $N$ 또한 $7$의 배수임을 알 수 있다.$ $
$ $
$ $
증명. $N = 1000A + b$로 나타내자. (즉, $b$는 $N$의 오른쪽 끝 세 자리의 수, $A$는 세 자리를 제외한 나머지 수이다.) 그러면 $f(N) = A - b$임을 알 수 있다. 먼저 다음 합동식이 성립함을 확인하자. \[ 6N = 6 (1000A + b) = 6000A + 6b \equiv_7 A - b = f(N). \] 이제 $6$와 $7$이 서로소라는 사실로부터, $6N \equiv_7 0$인 것과 $N \equiv_7 0$인 것은 서로 동치이므로 증명이 완료된다.$ $
$ $
예제. $N = 3,145,927,680$에 대하여 위 방법을 반복해서 적용하면, \[ \begin{array}{clc} & 3145927\!\mycancel{680} & \\ - \; \smash{\big)} & \phantom{0000}680 & \\ \hline & 3145\!\mycancel{247} & \\ - \; \smash{\big)} & \phantom{0}247 & \\ \hline & 2898 \end{array} \] 위에서 구한 $2898$은 $7$의 배수이므로, 원래 수인 $N$ 또한 $7$의 배수이다.$ $
$ $
$ $
아래에 소개할 방법은 브라질 상파울루 대학의 토자(Gustavo Gerald Toja)에 의해 고안된 방법이다.
$ $
$ $
증명. $N$을 다음과 같이 표현하자. \[ N = b_0 + 100 b_1 + 100^2 b_2 + 100^3 b_3 + \cdots + 100^{m} b_m. \] 여기서 $b_k = \rem(N,\, 100^k)$이다. 또한 각각의 $0 \leq k \leq m$에 대하여 $c_k$를 $b_k$를 $7$로 나눈 나머지로 정의하자. 그러면 $1000 \equiv_7 = -1$이라는 사실로부터, \[ \begin{align*} 10^m N & = 10^m \big( b_0 + 100 b_1 + 100^2 b_2 + 100^3 b_3 + \cdots + 100^{m} b_m \big) \\[5px] & \equiv_7 10^m \big( c_0 + 100 c_1 + 100^2 c_2 + 100^3 c_3 + \cdots + 100^{m} c_m \big) \\[5px] & = 10^m c_0 + 1000 \cdot 10^{m-1} c_1 + 1000^2 \cdot 10^{m-2} c_2 + 1000^3 \cdot 10^{m-3} c_3 + \cdots + 1000^m c_m \\[5px] & = 10^m c_0 - 10^{m-1} c_1 + 10^{m-2} c_2 - 10^{m-3} c_3 + \cdots + (-1)^m c_m \\[5px] & \equiv_7 10^m c_0 + 10^{m-1} (7-c_1) + 10^{m-2} c_2 + 10^{m-3} (7-c_3) + \cdots + \myblue{c_m} \\[5px] & = \overline{c_0 (7-c_1) c_2 (7-c_3) \cdots \myblue{c_m}} \end{align*} \] (단, 위 식에서는 $m$이 짝수라 가정하고 등식을 전개하였다. 만약 $m$이 홀수인 경우는 위의 파랗게 표시한 $\myblue{c_m}$ 부분을 $\myblue{(7-c_m)}$으로만 바꾸어 주면 된다.) 이제 임의의 양의 정수 $m$에 대하여 $10^m$과 $7$이 서로소라는 사실로부터, $10^m N \equiv_7 0$인 것과 $N \equiv_7 0$인 것은 서로 동치이므로 증명이 완료된다.$ $
$ $
예제. $N = 3,145,927,680$에 대하여 토자의 방법을 적용해보자. \[ \begin{array}{ccccccc} & 31 & 45 & 92 & 76 & 80 & \\ & 3 & \mycancel{3}4 & 1 & \mycancel{6}1 & 3 & \\ \hline & & & 3 & 11 & 43 & \\ & & & 3 & \mycancel{4}3 & 1 & \\ \hline & & & & 1 & 33 & \\ & & & & \mycancel{1}6 & 5 & \\ \hline & & & & & 56 & \end{array} \] 위에서 구한 $56$은 $7$의 배수이므로, 토자의 방법에 의하면 $N$ 또한 $7$의 배수여야 한다.$ $
$ $
$ $
증명. $10$의 거듭제곱을 $7$로 나누었을 때의 나머지는 다음과 같다. \[ 10^k \equiv_7 \begin{cases} 1 & \text{if} \quad \rem(k,\, 6) = 0 \\[5px] 3 & \text{if} \quad \rem(k,\, 6) = 1 \\[5px] 2 & \text{if} \quad \rem(k,\, 6) = 2 \\[5px] 6 \equiv_7 -1 & \text{if} \quad \rem(k,\, 6) = 3 \\[5px] 4 \equiv_7 -3 & \text{if} \quad \rem(k,\, 6) = 4 \\[5px] 5 \equiv_7 -1 & \text{if} \quad \rem(k,\, 6) = 5 \end{cases} \] 그러므로, \[ \begin{align*} N & = \overline{a_n \cdots a_3 a_2 a_1 a_0 \!} \\[5px] & = a_0 + 10 a_1 + 10^2 a_2 + 10^3 a_3 + 10^4 a_4 + 10^5 a_5 + 10^6 a_6 + \cdots \\[5px] & \equiv_7 a_0 + 3 a_1 + 2 a_2 + 6 a_3 + 4 a_4 + 5 a_5 + a_6 + \cdots \\[5px] & = f(N). \end{align*} \] 즉, $N \equiv_7 f(N)$이 성립하므로 증명이 완료된다.$ $
$ $
예제. $N = 3,145,927,680$이 $7$의 배수인지를 판정해보자. \[ \begin{align*} f(N) & = \myblue{1} \cdot 0 + \myblue{3} \cdot 8 + \myblue{2} \cdot 6 + \myblue{6} \cdot 7 + \myblue{4} \cdot 2 + \myblue{5} \cdot 9 \\[5px] & \qquad + \myblue{1} \cdot 5 + \myblue{3} \cdot 4 + \myblue{2} \cdot 1 + \myblue{6} \cdot 3 \\[5px] & = 168. \end{align*} \] 이제 $168$는 $7$의 배수이므로, 원래의 수 $N$ 또한 $7$의 배수임을 알 수 있다. 마찬가지로 \[ \begin{align*} f(N) & = \myblue{1} \cdot 0 + \myblue{3} \cdot 8 + \myblue{2} \cdot 6 + \myblue{(-1)} \cdot 7 + \myblue{(-3)} \cdot 2 + \myblue{(-2)} \cdot 9 \\[5px] & \qquad + \myblue{1} \cdot 5 + \myblue{3} \cdot 4 + \myblue{2} \cdot 1 + \myblue{(-1)} \cdot 3 \\[5px] & = 21 \end{align*} \] 이고 $21$은 $7$의 배수이므로, 원래의 수 $N$ 또한 $7$의 배수이다.$ $
$ $
위 방법을 응용하면, 다음과 같은 과정을 통해서 곱셈 계산량을 줄일 수 있다.
$ $
$ $
예제. $N = 3,145,927,680$이 $7$의 배수인지를 판정해보자. \[ \begin{align*} & \begin{array}{cccccccc} & 9 & 2 & 7 & 6 & 8 & 0 & \\ + \; \smash{\big)} & & & 3 & 1 & 4 & 5 & \\ \hline & \mycancel{9}2 & 2 & \mycancel{10}3 & \mycancel{7}0 & \mycancel{12}5 & 5 & \\ \times \; \smash{\big)} & 5 & 4 & 6 & 2 & 3 & 1 & \\ \hline & \mycancel{10}3 & \mycancel{8}1 & \mycancel{18}4 & 0 & \mycancel{15}1 & 5 & \end{array} \\[5px] & \qquad\qquad\qquad \implies \;\; 3 + 1 + 4 + 0 + 1 + 5 = 14. \end{align*} \] 이제 $14$는 $7$의 배수이므로, 원래의 수 $N$ 또한 $7$의 배수임을 알 수 있다.$ $
$ $
$ $
이번에는 $1000 \equiv_7 -1$임을 이용하는 방법이다. 이 방법은 $7 \cdot 11 \cdot 13 = 1001$이라는 사실로부터 $1000 \equiv_{11} -1$, $1000 \equiv_{13} -1$이기 때문에, $11$과 $13$의 배수 판정법에도 같은 방법을 적용할 수 있다는 장점이 있다.
$ $
$ $
증명. $10^3 \equiv_{7} -1$이라는 사실을 이용하면, \[ \begin{align*} N & = a_0 + 10 a_1 + 10^2 a_2 + 10^3 a_3 + 10^4 a_4 + 10^5 a_5 + 10^6 a_6 + \cdots \\[5px] & \equiv_7 a_0 + 10 a_1 + 10^2 a_2 - a_3 - 10 a_4 - 10^2 a_5 + a_6 + \cdots \\[5px] & = \big( a_0 + 10 a_1 + 10^2 a_2 \big) - \big( a_3 + 10 a_4 + 10^2 a_5 \big) + \big( a_6 + \cdots \\[5px] & = \overline{a_2 a_1 a_0 \!} - \overline{a_5 a_4 a_3 \!} + \overline{a_8 a_7 a_6 \!} - \cdots \\[5px] & = f(N). \end{align*} \] 즉, $N \equiv_7 f(N)$이 성립하므로 증명이 완료된다.$ $
$ $
예제. $N = 3,145,927,680$이 $7$의 배수인지를 판정해보자. \[ f(N) = 680 - 927 + 145 - 3 = -105 \] 이제 $-105$는 $7$의 배수이므로, 원래의 수 $N$ 또한 $7$의 배수이다.$ $
$ $
$ $
다음은 뉴욕의 신경정신과 의사인 라이언스(Vosburgh Lyons)가 발견 했다고 알려진 방법으로 특히 $N$이 매우 큰 수일 때 효과적이다. 또한 아래 증명에서 $100 \equiv_7 9$와 $1000 \equiv_7 = -1$이라는 사실이 사용되었는데, 이는 $13$에 대해서도 그대로 $100 \equiv_{13} 9$와 $1000 \equiv_{13} = -1$이 성립한다. 따라서 $13$의 배수 판정법에도 같은 방법을 적용할 수 있다는 장점이 있다.
$ $
$ $
증명. $N$을 다음과 같이 표현하자. \[ N = b_0 + 100 b_1 + 100^2 b_2 + 100^3 b_3 + \cdots + 100^{m} b_m. \] 여기서 $b_k = \rem(N, 100^k)$이다. 또한 각각의 $0 \leq k \leq m$에 대하여 $c_k$를 $b_k$를 $7$로 나눈 나머지로 정의하자. 그러면 $100000 \equiv_7 1$이므로, \[ \begin{align*} N & = b_0 + 100 b_1 + 100^2 b_2 + 100^3 b_3 + 100^4 b_4 + 100^5 b_5 + 100^6 b_6 + \cdots \\[5px] & \equiv_7 c_0 + 100 c_1 + 100^2 c_2 + 100^3 c_3 + 100^4 c_4 + 100^5 c_5 + 100^6 c_6 + \cdots \\[5px] & \equiv_7 c_0 + 100 c_1 + 100^2 c_2 + c_3 + 100^2 c_4 + 100^3 c_5 + c_6 + \cdots \\[5px] & = \big( c_0 + c_3 + \cdots \big) + 100 \big( c_1 + c_4 + \cdots \big) + 100^2 \big( c_2 + c_5 + \cdots \big) \\[5px] \end{align*} \] 이제 $k = 0,\, 1,\, 2$에 대하여, $A_k = \rem(c_k + c_{3+k} + c_{6+k} + \cdots,\, 7)$로 정의하자. 그러면, \[ \begin{align*} N & \equiv_7 A_0 + 100 A_1 + 100^2 A_2 \\[5px] & \equiv_7 A_0 + 9 A_1 - 10 A_2 \\[5px] & = (A_0 + 10 A_1) - (A_1 + 10 A_2) \\[5px] & \equiv_7 B_0 - B_1 \\[5px] & = f(N). \end{align*} \] 단, $B_0 = \rem(A_0 + 10 A_1,\, 7)$, $B_0 = \rem(A_1 + 10 A_2,\, 7)$이다. 결과적으로 $N \equiv_7 f(N)$이 성립하므로 라이언스의 방법이 성립함을 알 수 있다.$ $
$ $
예제. $N = 3,145,927,680$이 $7$의 배수인지 여부를 라이언스의 방법을 이용하여 판정해보자. \[ \begin{align*} & \begin{array}{ccccccc} & 31 & 45 & 92 & 76 & 80 & \\ & 3 & 3 & 1 & 6 & 3 & \\ & & & & 3 & 3 & \\ \hline & & & 1 & \mycancel{9}2 & 6 & \end{array} \\[5px] & \qquad\qquad\qquad \mycancel{12}5 \;\; \mycancel{26}5 \;\; \implies \;\; 5 - 5 = 0. \end{align*} \] 따라서 라이언스의 방법에 의해 $N$ 또한 $7$의 배수임을 확인할 수 있다.$ $
$ $