원주 위에서 말을 옮기는 규칙, 원시근과 순환소수 (2026학년도 영재학교 공동출제 대구 1번)
이번 글에서는 2026학년도 영재학교 공동출제 대구 1번, 원 위에서 규칙에 따라 말을 옮기는 문제를 살펴보겠습니다. 같은 문항이 대전 2번, 광주 2번, 세종 3번에도 나왔습니다. 풀이 뒤에는 어떤 원에서 모든 점을 방문할 수 있는지와, 이 이동이 순환소수의 나눗셈과 어떻게 이어지는지 생각해 보겠습니다.
문제는 아래와 같습니다.

2026학년도 영재학교 공동출제 대구 1번
Part 1. 풀이
1. 다음 점의 번호 생성 원리
원의 둘레가 nπ 이고 점이 같은 간격으로 n개 있으므로, 이웃한 두 점 사이의 호의 길이는 π 입니다. π 만큼 움직이는 것을 한 칸으로 세면 [1단계]에서는 0 에서 m칸 움직이므로 번호가 m 인 점에 놓입니다.
그다음에는 현재 번호에 m 을 곱한 만큼 움직입니다. 현재 점의 번호를 a 라 하죠. a 에서 am칸 더 가는 것이므로, 다음 점의 번호는 a + am = a(m + 1) 을 n 으로 나눈 나머지입니다. n칸을 움직일 때마다 같은 점으로 돌아오기 때문이죠.
문제에서 주어진 예시에서는 n = 5, m = 2 이므로 첫 번호 2 를 얻은 뒤부터는 (바로 윗 줄의 공식에 따라) 현재 자리의 번호를 3배하고 5 로 나눈 나머지를 구하면 됩니다.

n = 5, m = 2 의 여섯 장면, 빨간 원이 말의 위치
출발점까지 적으면 0 → 2 → 1 → 3 → 4 → 2 이고, 2 에 다시 놓이는 순간 멈춥니다.
2. 사각형의 넓이
(1)에서는 n = 8, m = 1 이므로 [1단계]의 번호는 1 이고, 그다음부터는 2배하고 8 로 나눈 나머지를 구합니다.
4 의 2배가 8 이라서 마지막에는 출발점 0 으로 돌아옵니다. 이 네 점을 순서대로 선분으로 연결하면 아래 사각형입니다.

0, 1, 2, 4 를 순서대로 연결한 사각형
둘레가 8π 이므로 원의 반지름은 4 입니다. 넓이를 구하기 위해 원의 중심을 O, 번호가 0, 1, 2, 4 인 점을 각각 A, B, C, D 라 하겠습니다. B 에서 OC 에 내린 수선의 발을 H 라 하면 다음과 같습니다.

A, B, C, D 는 번호 0, 1, 2, 4 인 점, 중심 O 와 수선의 발 H 로 나눈 세 삼각형
원을 8등분했으므로 이웃한 두 반지름이 이루는 각은 360° ÷ 8 = 45° 입니다. 그래서 ∠BOH = 45° 이고 ∠BHO = 90° 인 △OBH 는 직각이등변삼각형입니다.
OB = 4 이고 OH = BH 이므로, 피타고라스 정리를 적용하면
입니다.
△OAB 와 △OBC 는 두 변의 길이가 4 이고 끼인각이 45° 로 같으므로 SAS합동이고, △OBC 는 밑변 OC = 4 에 대한 높이가 BH = 2√2 입니다. △OCD 는 서로 수직인 두 변 OC, OD 의 길이가 각각 4 이므로, 구하는 사각형의 넓이는 세 삼각형의 넓이를 더해서
입니다.
3. 번호의 합의 최댓값
이제, 소문항 (2)번을 풀어보겠습니다.
n = 10 이므로 가능한 자연수 m 은 1 부터 9 까지입니다. 각 경우 첫 번호는 m 이고, 이후에는 현재 번호를 m + 1 배해서 일의 자리만 남기면 됩니다. 처음 나온 번호를 다시 만나면 그 줄의 계산을 멈추게 되구요.
예를 들어 m = 7 이면, 첫 번호 7 에서부터 8배한 수의 일의 자리를 이어가므로
에서 도착점의 번호는 0 → 7 → 6 → 8 → 4 → 2 → 6 입니다.
같은 방법으로 아홉개 경우를 전부 노가다 뛰어서 계산하면 아래 표와 같습니다. (마지막에 다시 나온 번호는 합에 한 번 더 넣지 않는 것에 주의합니다.)

m = 1 부터 9 까지의 도착점과 서로 다른 번호의 합
가능한 m 을 빠짐없이 비교했을 때, 합이 가장 큰 경우는 m = 7 입니다. 이때 실제로 말이 놓인 점은 출발점을 포함하여 0, 2, 4, 6, 7, 8 입니다.

n = 10, m = 7 에서 방문한 여섯 점은 청록색, 멈춘 점은 번호 6
따라서 (2)의 답과 그때의 번호의 합은
입니다.
4. 짝수 n 에서 빠지는 점
(3)에서는 n 이 4 이상의 짝수입니다. 짝수를 짝수 n 으로 나누면 나머지도 짝수입니다. 짝수에서 n 의 배수인 짝수를 빼서 나머지를 만들기 때문이죠.
[1단계]에서 놓인 번호는 m 이고, [2단계]의 번호는 m(m + 1) 을 n 으로 나눈 나머지입니다. 연속한 두 정수 m, m + 1 중 하나는 짝수이므로 그 곱은 짝수이고, [2단계]의 번호도 짝수입니다.
그 이후에도 현재 번호가 짝수이면 m + 1 을 곱한 수가 짝수이고, 짝수 n 으로 나눈 나머지도 짝수입니다. 그러므로 [2단계]부터 멈출 때까지는 모두 짝수 번호에 놓입니다.

짝수 n 에서 m 의 홀짝성에 따른 도착점 번호
m 이 짝수이면 [1단계]의 번호도 짝수라서 홀수 번호에는 한 번도 놓이지 않습니다.
m 이 홀수이면 홀수 번호 중에서는 [1단계]의 m 에만 놓입니다. 그런데 n ≥ 4 이므로 번호 1 과 3 이 모두 있고, 둘 중 적어도 하나는 m 과 다릅니다. 그래서 그 점에는 말이 놓일 수 없게되죠.
출발점 0 을 포함해도 방문하지 못하는 홀수 번호가 남으므로, 조건을 만족하는 자연수 m 은 없습니다.
Part 2. 더 생각해보기
5. 합성수 n 의 경우 "모두 방문" 가능성

문제의 n = 5, m = 2 예시, 다섯 점을 모두 방문한 뒤 번호 2 에서 멈춘다
문제에 주어진 n = 5, m = 2 의 예시는 다섯 점을 모두 방문합니다. 짝수에서는 "모두 방문" 이 안 되는데 홀수에서는 되는 경우가 있네요. 그렇다고 홀수이기만 하면 되는 것은 아닙니다. 예를 들어 n = 9 에서는 어떤 m 을 골라도 모든 점을 방문할 수 없습니다.

n = 9 에서 m = 1, 2, 3 의 방문점, 청록색으로 표시한 점 이외에는 말이 놓이지 않는다
n = 9, m = 1 이면 첫 번호 1 을 계속 2배해서 나머지를 구하므로, 번호 3 과 6 에는 놓이지 않습니다. m = 2 이면 0 → 2 → 6 → 0 이고, m = 3 이면 0 → 3 → 3 입니다. 위 그림에서는 3 의 배수인지 아닌지가 서로 다른 방식으로 방문점을 제한하고 있습니다.
이것을 일반적인 합성수 n 에도 적용할 수 있습니다. n 의 소인수 하나를 q 라 하죠. n 이 합성수이므로 q < n 이고, 번호 q 인 점은 출발점과 다른 점으로 실제로 있습니다. n 의 배수를 더하거나 빼도 q 의 배수 여부는 변하지 않습니다.
① m 이 q 의 배수이면 첫 번호부터 q 의 배수이고, 이후에도 곱셈과 나머지 계산을 거칠 때마다 q 의 배수입니다. 그래서 번호 1 에 놓일 수 없습니다.
② m + 1 이 q 의 배수이면 [2단계] 이후의 번호는 모두 q 의 배수입니다. 번호 1 과 n − 1 은 둘 다 q 의 배수가 아닌데, 그런 번호에 놓일 기회는 [1단계] 한 번뿐입니다. 둘 중 적어도 하나는 방문하지 못합니다.
③ m 과 m + 1 이 모두 q 의 배수가 아니면, 첫 번호 m 에서 시작하여 m + 1 을 반복해서 곱해도 q 의 배수가 되지 않습니다. q 가 소수라서 q 의 배수가 아닌 두 수의 곱은 q 의 배수가 아니기 때문입니다. 나머지를 구할 때도 이 성질이 유지되므로 번호 q 에 놓일 수 없습니다.
세 경우에 빠지는 점이 각각 있으므로, 짝수뿐 아니라 모든 합성수 n 에서도 모두 방문은 불가능합니다. 그런 관점에서 보면 (3)의 홀짝성은 소인수 2 때문에 발생한 상황이었던겁니다.
6. 소수와 원시근 관점
n 이 소수이면 0 이 아닌 번호는 모두 n 과 서로소입니다. 앞 절에서 사용한, 0 과 다른 소인수 번호 q 가 이제는 없으므로 합성수 때와는 상황이 달라집니다.
그렇지만 소수라고 아무 m 이나 골라도 다 되는 것은 아닙니다. n = 7 에서 m = 1 이면
로 멈추고, m = 2 이면
가 되어 모든 점을 방문합니다.

n = 7 에서 m = 1 은 네 점, m = 2 는 일곱 점을 방문한다
두 경우는 첫 번호 뒤에 곱하는 수가 각각 2 와 3 입니다. 7 로 나눈 나머지만 적으면서 1 을 계속 2배하면 1, 2, 4 에서 반복하지만, 계속 3배하면
이 되어 0 이 아닌 나머지 여섯 개가 모두 나옵니다.
이렇게 어떤 수의 거듭제곱을 소수로 나누었을 때, 0 이 아닌 나머지가 전부 나오는 수를 그 소수의 원시근(primitive root)이라고 합니다. 3 은 7 의 원시근이고, 2 는 아닙니다.
이 문제에서 [1단계] 이후의 번호는 다음 수들을 n 으로 나눈 나머지입니다.
그래서 n 이 소수일 때 모든 점을 방문하려면, 곱하는 수 m + 1 이 n 의 원시근이면 됩니다.
(앞에 곱해진 m 때문에 서로 다른 나머지가 합쳐지지는 않습니다. 소수 n 의 배수가 아닌 m 을 곱해서 두 나머지가 같아진다면, 두 수의 차이가 n 의 배수여야 하는데 서로 다른 0 이상 n 미만의 두 수로는 그럴 수 없기 때문입니다. 즉, m 을 곱해도 0 이 아닌 나머지가 전부 나온다는 조건은 같습니다.)
참고로, 모든 소수마다 원시근이 적어도 하나 있다는 정리가 있습니다. 가우스(Carl Friedrich Gauss)가 1801년에 이 사실을 증명했다고 합니다. 이 존재 정리의 증명은 여기서는 다루지 않겠습니다. (소수로 나눈 다항식의 근의 개수 등을 따져야 해서 다음에 따로 글로 작성해 블로그에 올리겠습니다.)
이 정리에 따라 문제의 범위 n ≥ 4 에서는, 모든 점을 방문하는 m 이 존재하는 경우가 정확히 n 이 소수인 경우입니다.
7. 순환소수의 나머지
예를 들어, n = 7, m = 2 일 때 [1단계] 뒤의 이동은 현재 번호에 3 을 곱해서 7 로 나눈 나머지를 구하는 것이었습니다. 그런데 10 은 7 로 나누면 나머지가 3 이므로, 3배 대신 10배해도 나머지가 같습니다.
재미있는 것은 이 계산이 1 을 7 로 나누어 소수로 나타낼 때 나오는 패턴입니다.
처음에는 1 을 10배한 10 을 7 로 나눠서 몫의 숫자 1, 나머지 3 을 얻습니다. 다음에는 그 나머지 3 을 10배한 30 을 7 로 나눠서 몫의 숫자 4, 나머지 2 를 얻습니다.

1 을 7 로 나누는 계산, 나머지에 10 을 곱해 다음 자리의 숫자를 구한다
이 나눗셈의 나머지는 1 → 3 → 2 → 6 → 4 → 5 → 1 입니다. 원 위의 말은 2 에서 출발하여 이 순서를 따랐고, 나눗셈은 1 에서 출발하여 같은 순서를 따르고 있었네요. 나머지가 1 로 돌아오면 그다음 계산도 처음과 같으므로, 소수의 숫자 142857 이 여섯 자리마다 반복됩니다.
또, 2 를 7 로 나누면 나머지 2 에서 시작하므로 같은 계산을 두 칸 뒤에서 시작하게 됩니다. 그래서 소수 부분은 0.285714285714… 이 됩니다. 3 부터 6 까지도 시작하는 나머지만 바뀌므로 반복되는 여섯 숫자의 순서는 유지됩니다.
이 때문에 142857 에 1 부터 6 까지를 곱하면 같은 숫자들이 순서대로 순환하는 현상이 생깁니다.

142857 의 1배부터 6배, 숫자 1 의 위치를 빨간색으로 표시
