거꾸로 뒤집어 처음의 배수가 되는 수

별로 흥미롭지 않은듯 하지만, 흥미로운 결과로 끝나는 이야기를 해볼까 한다. ㅎㅎㅎ

이 포스트는 [1], [2], [3]의 내용을 근거로 작성한 것이다. 불충분한 부분이 있다면 원본을 참조하시길 바란다.

 


십진법으로 표기된 주어진 수가 있다면 일의 자리 숫자부터 읽어서 거꾸로 뒤집는 작업을 할 수 있다. 이 과정에 의해 1234(천이백삼십사)는 4321(사천삼백이십일)이 된다. 그런데 이렇게 뒤집은 수가 원래 수의 배수(혹은 약수)가 되는 경우는 어떤 것이 있을까?

당연히 12321과 같은 좌우대칭인 수는 뒤집어도 똑같으므로 이러한 숫자를 제외하자. 또한 뒤집어서 자리수가 달라지는 경우도 재미 없으므로-_- 빼고 생각하자. 이러한 숫자로 이루어진 수열이 온라인 정수열 사전 A031877에 등록되어 있다. 정수열을 가만히 보면 8712와 9801로 시작해서 가운데 9자를 계속 끼워넣어 만든 수열임을 알 수 있다. ㅋ

하디의 유명한 저서 ‘어느 수학자의 변명(A Mathematician’s Apology)‘에는 숫자를 거꾸로 뒤집어 처음의 배수(혹은 약수)가 되는 nontrivial 네 자리수는 8712와 9801 오직 이 둘뿐인데, 별로 심각하게 일반화 시킬 내용도 없다고 언급하는 내용이 있다고 한다.[1] 뭐 본인은 그 책을 사실 안 읽어봐서 모르겠다-_- 하디의 이런 발언에도 불구하고 [1]에서 열심히 일반화 시키고 있다. ㅎ

그런데 어떻게 이걸 일반화 시키는가? n 진법에서 뒤집어서 원래 수의 배수가 되는 수들을 분류하는 것이 계산의 목표이다. 이러한 성질을 가진 수를 solution이라 부르자. 이러한 계산을 Alan Sutcliffe이라는 친구가 시도[2]한 모양이다. 이 친구가 두 자리수를 모두 분류했는데, n+1이 합성수임과 두 자리 solution이 항상 존재함이 동치라는 정리의 증명이 나온다.

또 그는 이 두 자리수 분류를 바탕으로 세 자리수를 분류했는데, 두 자리수의 분류를 가지고 시작했으므로 두 자리 solution이 존재하지 않으면서 세 자리 solution이 존재하는 진법이 존재하는 경우를 처리할 수 없다. 즉, n+1이 소수일 때, n 진법으로 두 자리 solution은 없지만 세 자리 solution이 있는 경우를 그는 의문으로 남겨 놓을 수 밖에 없었다.

그런데 Kaczynski[3]라는 친구가 이 문제를 해결한다. 즉, n+1이 소수일 때, 세 자리 solution이 존재하면, 반드시 두 자리 solution도 존재한다는 것을 증명한 것이다. 그런데 이 이름 어디선가 많이 본 이름아닌가? ㅋㅋㅋ 그렇다. 그 유명한 유나바머가 아닌가! 20년 이상 FBI의 추적을 피하고 우편물 폭탄 테러를 하여 현재 연방 일급 수감소(Supermax)에 무기징역으로 복역중인 인물이다. 일전에 ‘수학자의 살인‘ 포스트에서도 소개한 적이 있다. 그가 했던 증명을 본인이 약간 수정하여 소개한다. 물론 매거진에 실린 내용이라서 modular arithmetic만 알면 중고교생도 이해할 수 있을 듯 하다.

 


0. notation >
(a, b, c)_{n} 이라 쓰면 n 진법의 세 자리 수이다. 즉, (a, b, c)_{n} = an^2 + bn + c 이다. 예를 들어 (1, 2, 3, 4)_{10} = 1234 가 된다. ㅋㅋ

1. theorem >
이진법 또는 삼진법에서 3자리 solution은 없다.

1-1. proof of theorem 1 >
만약 k(a, b, c)_{n} = (c, b, a)_{n} 이라 하자. 가정에 의해 1 < k < n 이다. n=2라면 1< k < 2 이므로 불가능하다. n=3이라면 k = 2 이어야 한다. 따라서 2(9a + 3b + c)= 9c + 3b + a 이다. 그런데 삼진법인데다가 뒤집으면 다른 수가 되어야 하므로 a = 1, c = 2 이어야 한다. 따라서 0 = 17a + 3b-7c \ge 17 + 3b-14 > 0 이므로 역시 불가능하다.

2. theorem >
사진법 이상에서 3자리 solution이 존재하면 2자리 solution도 존재한다.

2-1. proof of theorem 2 > part 1
Alan Sutcliffe의 결과[2]에 의해 n+1이 소수인 경우만을 고려하면 된다. p = n+1 이라고 두자.

k(an^2 + bn + c) = cn^2 + bn + a … 식(1)

가 성립한다면 양변에 mod p를 취하여

k(a -b + c)\equiv c - b + a = a - b + c \pmod{p}

를 얻는다. 따라서 (k-1)(a-b +c) \equiv \pmod{p} 를 얻는다. 그런데 p > n > k 이므로 p가 k-1을 나누지 못한다. 따라서 p는 a – b + c 를 나눈다. 이 값은 -p < n < a - b + c < 2n < 2p 이므로 가능한 값은 a - b + c =0 또는 a - b + c =p 뿐이다.

2-2. proof of theorem 2 > part 2 : a - b + c =p 인 경우
b = a + c -p 이므로 식 (1)에 대입하면,

k[(a(n + 1) -p)n + c(n + 1)] = (c(n + 1) - p)n + a(n + 1)

이고, p = n+1 임을 이용하여 다시 이를 정리하면

k [(a-1)pn +cp ] = (c-1)pn +ap … 식(2)

가 된다. 양변을 p로 나누어 k[(a-1)n+c] = (c-1)n+a 가 되는데, 이 식은 식(1)과 매우 유사하다. 유사한 작업을 한 번 더 반복해보자. 즉, 양변에 mod n-1을 취하여

k(a-n + c) \equiv c-n + a = a-n + c \pmod{n-1}

이므로, (k-1) (a-n+c) \equiv \pmod{n-1} 을 얻는다. 가정에 의해 k > 1 이고, 또한 0 \le b = a + c -p 이므로 a + c -n \ge 1 이다. 결국 (k-1) (a-n+c) \ne 0 이므로 (k-1) (a-n+c) \ge n-1 이 된다. 또한 c-n \le -1 이므로 (k-1)(a-1) \ge (k-1) (a-n+c) \ge n-1 을 얻는다.

한편 이 결과를 이용해 식(2)와 비교해서

\begin{aligned} k(n(a - 1) + c) &= nk(a - 1) + kc \\ & \ge n(k - 1)(a - 1) + kc \\ & \ge n(n - 1) + kc \\ & \ge nc + kc \\ & > n(c - 1) + a\end{aligned}

을 얻는데, 이는 식(2)와 모순이다. 따라서 이러한 관계를 만족하는 세 자리수는 존재하지 않는다.

2-3. proof of theorem 2 > part 3 : a - b + c =0 인 경우
b = a + c 이므로 식 (1)에 대입하면,

k(an^2 + (a+c)n + c) = cn^2 + (a+c)n + a

이다. 정리하면

k(an+ c)(n+1) = (cn+ a)(n+1)

이므로 양변을 n+1로 나누어 두 자리수의 solution을 얻는다.

 


결국 모든 결과를 종합하면 두 자리 solution이 존재하는 것과 n+1이 합성수라는 것은 동치[2]이고, 두 자리 solution으로 세 자리 solution이 항상 유도된다[2]. 또한 n+1이 소수이고 세 자리 solution이 존재하면 두 자리 solution도 반드시 존재해야 하는데[3], 이는 불가능하다. 따라서 n+1이 합성수이면 두 자리 및 세 자리 solution이 존재하고, n+1이 소수이면 두 자리 및 세 자리 solution이 모두 없다. 실제로 십진법의 경우 10+1이 소수이므로 두 자리, 세 자리 solution이 없다. 가장 작은 solution은 하디가 지적한 대로 2178이 된다.

 


[1] Lara Pudwell, “Digit Reversal Without Apology“, Mathematics Magazine, Vol. 80 (2007), pp. 129-132.
[2] Alan Sutcliffe, “Integers That Are Multipled When Their Digits Are Reversed”, Mathematics Magazine, Vol. 39 (1966), pp. 282–287. pdf 566kb
[3] T. J. Kaczynski, “Note on a Problem of Alan Sutcliffe”, Mathematics Magazine, Vol. 41 (1968), pp. 84–86. pdf 331 kb

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중