배수 판정법

'''배수 판정법'''은 배수인지 확인하려는 수의 배수가 맞는지 간단히 확인하는 절차이다. 
일반적으로 정수 에 대해 이 의 배수인지 확인하려면 이 으로 나누어 떨어지는지 확인하면 된다. 이때 이 클 을 하는데 시간도 오래 걸리고, 틀린 답이 나올 수도 있다. '''의 배수 판정법'''은 의 이론적 성질을 이용하여 의 자리수 에 대한 정보를 통해 이 의 배수인지 판정할 수 있는 절차이다. 배수 판정법은 자리수에 대한 나눗셈, 곱셈을 이용하기 때문에 덧셈보다 간단하고, 아무리 큰 수라도 배수 판정을 보다 쉽고 빠르게 할 수 있다.
다음은 43가지 자연수의 배수 판정법이다.
* 1의 배수: 모든 수는 1의 배수이므로 굳이 계산 필요가 없다.
* 2의 배수: 일의 자리 수가 0,2,4,6,8인 수이다.
* 3의 배수: 각 자리 수의 합이 3의 배수인 수이다.
*'''4'''의 배수는 가장 끝에 두 자리수가 00이거나 4의 배수인 수이다. (십의 자리가 짝수인 경우에는 일의 자리수가 0, 4, 8이면 되고, 십의 자리수가 홀수인 경우에는 일의 자리수가 2, 6이면 된다.)
*'''5'''의 배수는 일의 자리수가 5, 0인 수이다.
*'''6'''의 배수는 2와 3의 공배수, 즉, 짝수이면서 각 자리의 합이 3의 배수인 수이다.
*'''7'''의 배수는 일의 자리를 두 배 한 것을 나머지 수에서 빼면 결과가 0 또는 7의 배수가 나오는 수이다.(스펜스의 방법) 다른 방법으로는 일의 자리부터 세 자리씩 끊어서 교대로 빼고 더한 것이 7의 배수일 경우 본래의 수도 7의 배수이다. 이 방법은 7이 1001의 약수임을 이용한 것으로 다른 1001의 약수 11, 13, 77, 91, 143, 1001에도 적용시키는 게 가능하다. 또 다른 방법으로는 본래의 수를 10으로 나눈 뒤에 소수점 아래는 버림한 값에 본래의 수의 일의 자리를 다섯 배한 수를 더한 결과가 7의 배수이면 본래의 수도 7의 배수이다. 
*'''8'''의 배수는 가장 끝에 세 자리수가 000이거나 8의 배수인 수이다. (좀 더 쉽게 설명하자면 백의 자리가 0이거나 짝수인 경우에는 끝에 두 자리수가 00, 08, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96 다시 말해 8의 배수인 수이고, 백의 자리가 홀수인 경우에는 끝의 두 자리수가 4의 배수면서 8의 배수가 아닌 두 자리수 4, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92이어야 한다.)
*'''9'''의 배수는 각 자리 숫자의 합이 9의 배수인 수이다.
*'''10'''의 배수는 일의 자리가 0인 수이다.
*'''11'''의 배수는 홀수 자리의 합과 짝수 자리의 합의 차가 0이거나 11의 배수인 수이다. 다른 방법은 일의 자리 숫자를 제외한 후 남은 숫자에 제외시킨 일의 자리 숫자를 뺀 결과가 0이거나 11의 배수이면 본래의 수도 11의 배수이다.
*'''12'''의 배수는 3과 4의 공배수인 수이다.
*'''13'''의 배수는 일의 자리를 네 배하고 나머지 자리에서 더한 값이 13의 배수인 수이다. 다른 방법으로는 일의 자리부터 세 자리씩 끊어서 교대로 빼고 더한 것이 13의 배수일 경우 본래의 수도 13의 배수이다.
*'''14'''의 배수는 2와 7의 공배수 즉 일의 자리를 두 배하고 나머지 수를 뺐을 때 결과가 0 또는 7의 배수인 수이면서 동시에 짝수인 수이다.
*'''15'''의 배수는 3과 5의 공배수인 수이다. 즉 다시 말해 각자리의 합이 3의 배수이면서 일의 자리가 0 또는 5인 수이다.
*'''16'''의 배수는 끝에 네 자리수가 0000이거나 16의 배수인 수이다. 다른 방법은 끝에 네 자리의 앞의 두 자리 (천의 자리와 백의 자리)를 n으로 놓고 그 수를 4로 나눈 나머지에다 4를 곱해서 나머지 수에 더한다 이 값이 0이거나 16의 배수이면 원래 수도 16의 배수이다.
*'''17'''의 배수는 일의 자리를 다섯 배 하여 나머지 자리에서 뺀 값이 0이거나 17의 배수인 수이다.
*'''18'''의 배수는 2와 9의 공배수 즉 각 자리의 합이 9의 배수이면서 짝수인 수이다.
*'''19'''의 배수는 일의 자리를 두 배하고 나머지 수를 더하는데 그 결과가 19의 배수인 수이다.
*'''20'''의 배수는 십의 자리가 0, 2, 4, 6, 8이고 일의 자리가 0인 수이다. (즉, 끝의 두 자리 수가 00, 20, 40, 60, 80 이면 20의 배수이다.)
*'''21'''의 배수는 3과 7의 공배수인 수이다. 즉 각 자리의 합이 3의 배수이면서 7의 배수로 판정되는 수이다. 다른 방법으로는 일의 자리를 두 배 하고 나머지 수를 빼는데 결과가 0 또는 21의 배수일 경우 본래의 수도 21의 배수이다.
*'''22'''의 배수는 2와 11의 공배수인 수이다. 다시 말해 짝수이면서 홀수 자리의 합과 짝수 자리의 합의 차가 0이거나 11의 배수인 수.
*'''23'''의 배수는 일의 자리 숫자를 7배하여 나머지 자리를 더한 값이 23의 배수인 수이다.
*'''24'''의 배수는 3과 8의 공배수인 수이다.4와 6의 공배수이기도 하지만 4 와 6의 최소공배수가 아니기 때문에 4와 6의 배수 판별법이 섞일수 없다.
*'''25'''의 배수는 끝의 두 자리가 00, 25, 50, 75인 수이다.
*'''26'''의 배수는 2와 13의 공배수인 수이다.
*'''27'''의 배수는 4자리 이상일 경우에는 9의 배수의 확장 개념으로 37의 배수와 비슷하게 일의 자리부터 세 자리씩 나눠 묶은 후 그 숫자들을 모두 더한 값이 27의 배수인 수이다. 1001이 7, 11, 13의 배수인 것과 비슷하게 999가 27, 37의 배수인 것처럼 말이다. 다른 방법으로는 일의 자리 숫자를 8배 하여 나머지 자리에서 뺀 값이 27의 배수면 본래의 수도 27의 배수이다.
*'''28'''의 배수는 4와 7의 공배수인 수이다.
*'''29'''의 배수는 일의 자리 숫자를 3배하여 나머지 자리에서 더한 결과가 29의 배수인 수이다.
*'''30'''의 배수는 3의 배수이면서 일의 자리가 0인 수이다.
*'''31'''의 배수는 일의 자리를 3배하고 나머지 자리에서 뺀 값이 0 또는 31의 배수인 수이다.
*'''32'''의 배수는 마지막 다섯 자리가 00000이거나 32의 배수인 수이다.
*'''33'''의 배수는 3과 11의 공배수인 수이다. 다시 말해 각 자리의 합이 3의 배수면서 짝수자리의 합에서 홀수자리의 합을 뺀 값이 0이거나 11의 배수인 수이다. 다른 방법으로는 두 자리 씩 끊어서 더한 값이 33의 배수일 경우 본래의 수도 33의 배수이다.
*'''34'''의 배수는 17의 배수이면서 짝수인 수이다.
*'''35'''의 배수는 일의 자리가 0이거나 5이면서 7의 배수인 수이다.
*'''36'''의 배수는 4와 9의 공배수인 수이다.
*'''37'''의 배수는 27의 배수와 마찬가지로 일의 자리부터 세 자리씩 나눠 묶은 후 그 숫자들을 모두 더한 값이 37의 배수인 수이다. 이 방법도 역시 37이 999의 약수라는 것을 이용했으며,  111, 333, 999에도 적용할 수 있다. 단, 9와 3은 각 자리숫자의 합이기 때문에 해당이 되지 않는다. 다른 방법으로는 일의 자리를 11배하여 나머지 자리에서 뺀 값이 0 또는 37의 배수인 수이다.
*'''38'''의 배수는 19의 배수이면서 짝수인 수이다.
*'''39'''의 배수는 3의 배수이면서 13의 배수인 수이다.
*'''40'''의 배수는 일의 자리가 0이고, 백의 자리와 십의 자리가 4의 배수인 수이다.
→ 합성수의 배수판별이 필요할때는 해당 합성수의 소인수가 모두 몇 개인지 구한 다음 소인수로 나눠서 모두 만족하는지 확인하면 편하다. 이때 합성수의 소인수가 2개 이상인 경우에는 1과 '''자기 자신이 아닌'''  유니타리 약수의 공배수를 조건으로 하면 되며, 2나 5의 거듭제곱의 배수는 가장 끝에 있는 2 또는 5의 거듭 횟수 자리가 모두 0 또는 2나 5의 거듭제곱의 배수이면 된다. 그후부터는 그 규칙이 반복된다. 또한 일반적으로 1보다 큰 자연수 n에 대하여 n진법에서 n^^m^^-1 및 그 약수의 배수 (m는 2 이상의 자연수)일 필요 충분 조건은 일의 자리부터 m자리씩 끊어서 나뉜 수들을 모두 더한 값이 n^^m^^-1의 배수여야 한다는 것이다. n진법에서 1부터 수를 셀 경우 1, 2, 3, ... , (n-1), 10, 11, ... 이렇게 되는데 여기서 숫자가 하나씩 커질 때마다 일의 자리가 (n-1)에서 0으로 바뀌는 경우가 아니면 각 자리 숫자의 합은 1 증가하게 되며, 또한 숫자의 값이 하나씩 커질 때 일의 자리 숫자가 (n-1)에서 0으로 바뀌는 경우 나머지 자릿값 중 값이 1 증가하는 것이 하나 있기 때문에 각 자리 숫자의 합을 (n-1)로 나눈 나머지는 (n-2)에서 0이 되거나 1 증가한다. 여기서 (n-1)이 (n-1)의 배수이므로 이것이 성립한다. 예를 들어 9의 배수는 10진법에서 각 자리숫자의 합이 9의 배수여야 하므로 그 약수인 3 역시 각자리 숫자의 합이 3의 배수여야 한다. 이를 확장하여 99와 99의 약수인 33의 배수는 일의 자리부터 2자리씩 끊어서 나온 수들을 모두 더한 값이 33, 99의 배수여야 한다는 것이다. 마찬가지로 27, 37, 111, 333은 999의 약수이고, 303과 909는 9999의 약수이고, 41, 123, 271, 369, 813, 2439 역시 99999의 약수이기 때문에 적용시킬 수 있다. 이론상 n진법에서 n과 서로소인 모든 자연수에 적용시킬 수 있지만, 순환마디가 너무 길다면 적용하는게 어려울 수 있다. 이러한 수는 n진법에서 역수를 소수 (decimal number) 로 표기할 경우 순순환 소수가 되며, 역수의 순환마디에 그 수를 곱하면 n^^m^^-1이 된다. n^^m^^+1 및 그 약수의 배수 (m은 2 이상의 자연수) 역시 이와 비슷한 방법으로 일의 자리부터 m자리씩 끊어서 이 수를 오른쪽부터 나열한 뒤, 빼고 더하는 방식을 이용하면 된다. 예를 들어 1001의 약수인 7, 11, 13, 77, 91, 143의 경우 일의 자리부터 3자리씩 끊어서 빼고 더하는 방식을 교대로 반복하면 된다. 73과 137은 10001의 약수이고, 9091 은 100001의 약수이며, 9901은 1000001의 약수이기 때문에 이 방법을 적용시킬 수 있다. 이 방법은 n진법에서 n과 서로소인 자연수여서 역수의 순환마디 길이가 짝수인 수 중 (n-1)과 서로소인 모든 수에 적용할 수 있다. 물론 순환마디가 너무 길 경우에는 적용하기가 힘들어진다.
41: 일의 자리수와 나머지 자릿수를 더한수의 8배에다 일의 자리수를 더한 수가 41의 배수이면 41의 배수이다.
43: 일의 자리를 지운수의 2배에 일의 자리와 나머지 자리를 더한수의 5배를 더한수가 43의 배수이면 43의 배수이다.
50:  맨 끝 두자리가 00 또는 50 이면 50의 배수이다.
모든 자연수의 배수판정법은 다음과 같은 방법으로 이끌어 낼 수 있다.
* 1. 어떤 자연수를 소인수분해한다.
* 2. 다음 과정에 따라 어떤 수의 배수 판정법 과정에 각 줄의 내용을 추가시킨다.
** 1. 만약 자연수의 소인수분해 식에 2n이 포함되어 있으면, 배수판정을 하고 싶은 수의 가장 끝의 n개의 자릿수가 0이거나 2n으로 나누어져야 한다.
** 2. 만약 자연수의 소인수분해 식에 3 또는 9가 있으면 (소인수에 3이 있는데 지수가 3 이상인 경우는 제외), 그 수의 각 자리 숫자의 합이 3 또는 9의 배수인지 확인한다.
** 3. 만약 자연수의 소인수분해 식에 5n이 포함되어 있으면, 2n이 있을 때와 비슷하게 배수판정을 하고 싶은 수의 가장 끝의 n개의 자릿수가 0이거나 5n의 약수여야 한다.
** 4. 위에 나온 소인수들의 경우를 제외하고도 아직 소인수들이 남아 있다면, 각 소인수들에 대해 다음 과정을 적용한다.
**# 소인수에 적절한 1자리 자연수를 곱해 끝 자리 수가 9가 되게 만든다. 즉 끝자리 수가 1인 경우 9를, 3인 경우 3을, 7인 경우 7을, 9인 경우 1을 곱한다.
**# 곱해서 나온 수에 1을 더한 후 10으로 나눈다. 이 수를 c라고 한다.
**# 배수판정을 하고 싶은 수를 n이라고 하고, n = 10a + b (이고 b는 자연수이다) 라 하자. 예를 들어 n = 489인 경우 a = 48, b = 9이다. 이때 a+bc가 원래 소인수의 배수여야만 n이 이 소인수의 배수이다.
=== 예시 1: 84 ===
앞에 나온 과정에 따라 84의 배수판정법을 만들면 다음과 같다.
# 84 = 22 ⋅ 3 ⋅ 7이다.
# 84 안에는 22, 3, 7이 포함되어 있다.
## 84의 소인수분해 식에 22가 포함되어 있으므로 84의 배수이려면 최소한 가장 끝의 2개의 자릿수가 0이거나 22 (=4)로 나누어떨어져야 한다.
## 84의 소인수분해 식에 3이 포함되어 있으므로 84의 배수이려면 최소한 각 자리 숫자의 합이 3의 배수여야 한다.
## 84의 소인수분해 식에는 7이 포함되어 있다.
### 7에 7을 곱하면 끝자리가 9가 된다. 7 ⋅ 7 = 49이다. 
### 49 + 1 = 50이고, 50을 10으로 나누면 5가 되므로 c = 5이다.
### 즉 84의 배수이려면 최소한 a+5b가 7의 배수여야 한다.
위 결과를 모두 종합하면 다음과 같다. 84의 배수이려면 먼저 가장 끝의 2개의 자릿수가 0이거나 4의 배수여야 하고, 각 자리 숫자의 합이 3의 배수여야 하며, 배수판정하고 싶은 수를 n = 10a + b라 하면 a+5b가 7의 배수여야 한다.
=== 예시 2: 455 ===
앞에 나온 과정을 따라하되 중간 과정을 생략하면 다음과 같다.
# 455 = 5 ⋅ 7 ⋅ 13이다. 
# 455 안에는 5, 7, 13이 포함되어 있다.
## 455의 배수이려면 먼저 끝의 1개의 자릿수가 0이거나 5로 나누어떨어져야 한다. 이 경우 한 자리 수 중에 5로 나누어떨어지는 수는 0과 5밖에 없으므로 455의 배수이려면 맨 끝의 자릿수가 0 또는 5가 되어야 한다고 해도 된다.
## 455의 배수이려면 최소한 a+5b가 7의 배수여야 한다.
## 455의 배수이려면 최소한 a+4b가 13의 배수여야 한다.
따라서 455의 배수이려면 먼저 맨 끝의 자릿수가 0 또는 5가 되어야 하고, a+5b가 7의 배수여야 하며, a+4b가 13의 배수여야 한다.
분류:정수
분류:나눗셈
분류:수론