7의 배수 판정과 그래프

Divisibility by 7 is a Walk on a Graph, by David Wilson

Tanya Khovanova의 수학 블로그에 올라온 글로 David Wilson이 알려주었다고 한다.

현재 이 사이트가 접속이 안 돼서 그림을 다시 그렸다.

먼저 0에서 출발하여 각 자리의 수만큼 검은 화살표 방향으로 움직이고, 자리 수가 바뀔 때마다 빨간 화살표 방향으로 움직이면 마지막 결과가 7로 나눈 나머지가 된다.

예를 들어 133을 생각해 보면, 처음 0에서 검정 화살표를 따라 한 번 움직이면 도착점은 1, 다음 자리 수인 3을 생각하기 전에 먼저 빨간 화살표를 따라 한 번 움직이면 도착점은 3. 여기서 다시 검정 화살표를 따라 세 번 움직이면 6에 도착한다. 마지막으로 빨간 화살표를 따라 4로 간 다음, 끝자리 수가 3이므로, 검정 화살표를 따라 세 번 움직이면 0에 도착한다. 즉, 133을 7로 나눈 나머지는 0이 된다.

재미있게도 이 그래프는 평면 그래프(planar graph)가 되는데, 7이 아닌 다른 수에 대해서도 이런 그래프는 항상 평면 그래프가 될까?