(별 쓰잘데기 없는) 3의 배수, 9의 배수 판별 방법

어떤 정수가 3의 배수라면 10진법으로 표현했을 때 각 자릿수 값을 더한 값은 3의 배수가 된다. 역으로 10진수로 표현된  임의의 정수에 대해 각 자릿수의 값의 합이 3의 배수이면 임의 정수는 3의 배수인 것도 성립한다.

 

가령 4157에 대해,  각 자리수를 더한 값은 17 (=4+1+5+7) 이 되며 17은 3의 배수가 아니므로 4157은 3의 배수가 되지 않는다. 17에 대해서도 각 자릿수 값을 더한 값이 3이 되어야 3의 배수가 된다는 논리를 재귀적으로 적용하면 8 (=1+7)이 되고 당연하게도 이 역시 3의 배수는 아니게 된다.

 

머리를 조금만 굴려보면 자릿수 중에서 3의 배수가 있다면 그건 제끼고 나머지 수를 더해서 3의 배수가 되는지를 판별할 수 있다. 즉 판별에 필요한 덧셈 연산의 개수를 줄일 수 있다.

 

가령15387에 대해 100의 자리수 3은 이미 3의 배수이므로 15387이 3의 배수가 되려면 1+5+8+7의 결과가 3의 배수면 된다. 여기에서도 "1+5=6"은 3의 배수이므로 제끼고 "8+7"이 3의 배수이면 된다. 8+7=15 이고 15에 대해서도 각 자릿수 값을 더한 값이 3이 되어야 3의 배수가 된다는 논리를 다시 적용하면 1+5=6 이 나온다. 6은 3의 배수이므로 15387은 3의 배수가 된다.

 

꽤 예전에 경험적으로 이걸 알아내고는 길거리에 누구 기다리면서 멍하게 있어야 할 때 지나가는 자동차 번호판 4자리 숫자를 보면서 3의 배수가 되는지 계산하면서 시간 죽이기 용도로 종종 쓰고 있다. (사실 이것 말고는 실제 생활에서 유용하게 쓸 일이 없긴 하다. 치매 예방에 효과가 조금 있으려나?)

 

그런데 별 쓰잘데기 없는 명제라서 그런지 임의의 정수에 대해 각 자리수를 더한 값이 3의 배수이면 임의의 정수가 3의 배수가 된다는 것에 대한 증명을 여태까지 본 적이 없어서 여기에 그 증명을 적어 본다. 유치한 수준의 수식으로도 쉽게 증명 가능하다. (증명을 써 놓고 혹시나 해서 검색해 보니 같은 방법으로 증명을 해 놓은 글들이 꽤 있다)

 

------------------------------------------------------------------------------

 

10진수로 자릿수 크기가 n인 임의 정수 I는 다음과 같이 표현된다.

 

I는 다음과 같이 변형하여 표현될 수 있다.

 

우측항을 전개하여 정리하면 아래와 같이 A항과 B항의 합으로 나타낼 수 있다.

 

A항은 언제나 3의 배수(또한 9의 배수)이므로 B항이 3의 배수라면 임의 정수 I는 3의 배수임이 성립한다. 즉 임의 정수를 10진수로 표현했을 때 각 자릿수의 계수를 더한 값이 3의 배수이면 그 때의 임의 정수는 3의 배수이다.

 

A항이 언제나 3과 9의 배수라는 건 그냥 직관이다. A항을 다소 복잡해 보이게 써 놓았지만 아래 예제를 보면 누구라도 직관적으로 받아들일 수 밖에 없을 것이다.

 

암튼 B항이 3의 배수임을 알아보려면 다시 각 자리수의 덧셈이 3의 배수가 되면 된다. 즉 재귀적으로 같은 연산을 계속해서 10 이하의 값이 되도록 자리수를 계속 더하고 더한 후 최종값이 3,6,9 중 하나가 되면 임의 정수 I는 3의 배수로 확정된다.

 

 

------------------------------------------------------------------------------

 

가령 23574을 위 증명식에 대입해 보자

 

23574 = 2*10000 + 3*1000 + 5*100 + 7*10 +4

         = 2(9999+1) + 3(999+1) + 5(99+1) + 7(9+1) +4

         = { 2(9999)+3(999)+5(99)+7(9) } + { 2+3+5+7+4 }

         = 3 { 2(3333)+3(333)+5(33)+7(3) } + { 2+3+5+7+4 }

 

따라서 23574가 3의 배수가 되려면 {2+3+5+7+4} 가 3의 배수이면 된다. 여기에서 1000의 자리수 3은 이미 3의 배수이므로 2+5+7+4가 3의 배수이면 되고 그 합은 18이 된다. 다시 재귀적으로 18이 3의 배수가 되려면 자리수를 더해서 3의 배수가 되면 된다. 최종적으로 1+8은 9이므로 23574는 3의 배수임이 성립한다.

 

------------------------------------------------------------------------------

 

증명수식을 가만 보고 있으면 B항의 값이 9의 배수이면 그 때 임의 정수는 9의 배수가 됨을 알 수 있다. 즉 자릿수의 계수들을 더하고 더하고 더해서 최종적으로 9가 나오면 그 수는 9의 배수가 된다.

 

가령, 23571를 아래와 같이 전개해 보면 23571가 9의 배수임을 알 수 있다.

 

23571 = 2*10000 + 3*1000 + 5*100 + 7*10 +1

         = 2(9999+1) + 3(999+1) + 5(99+1) + 7(9+1) +1

         = { 2(9999)+3(999)+5(99)+7(9) } + { 2+3+5+7+1 }

         = 9 { 2(1111)+3(111)+5(11)+7(1) } + { 2+3+5+7+1 }

 

2+3+5+7+1이 9의 배수이려면 18(=2+3+5+7+1)이 9의 배수이면 된다. 다시 재귀 적용하며 18이 9의 배수가 되려면 1+8이 9의 배수가 되어야 하며 1+8은 9이므로 최종적으로 23571은 9의 배수가 된다.

 

 

구구단에서 9단의 우측값에 대해 자릿수를 더하면 9가 되는 것은 우연이 아니라 필연이다.

 

9*1 = 9

9*2 = 18 --> 1+8=9

9*3 = 27 --> 2+7=9

9*4 = 36 --> 3+6=9

9*5 = 45 --> 4+5=9

9*6 = 54 --> 5+4=9

9*7 = 63 --> 6+3=9

9*8 = 72 --> 7+2=9

9*9 = 81 --> 8+1=9

 

 

PS : 이런 식의 자리수 연산으로 소수를 판별할 생각은 하지 말자. 분명 누군가는 시도해 봤을지 싶은데 여태 나오지 않는 것을 보면 불가능하지 싶다. 그리고 소수 판별이 자리수 연산만으로 가능하다면 소수 분해에 기반하는 암호화 기법이 무용지물이 되므로 지금 현 시대에 누리고 있는 일상 생활이 무너지게 된다.