AMC 10 · 2025 · #23

학년 7 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

modular-arithmeticdivisor-sumprime-factorization extreme-principleconvert-to-algebra ↑ 선수 지식: modular-arithmetic

📏 긴 풀이 💡 4 개 인사이트

문제

1보다 큰 정수 z를 고릅니다. 0, 1, 2, 하고 z 빼기 1 각각에 2025를 곱한 뒤 z로 나눈 나머지를 적습니다. 그 나머지들이 언제나 커지는 순서로 나오면, 곧 z보다 작은 모든 x가 y보다 작을 때 2025x의 나머지가 2025y의 나머지보다 작으면 z를 좋은 수라 합니다. 좋은 수를 모두 찾아 더한 값을 구하세요.

답을 골라 클릭하세요.

(A)

3041

(B)

3542

(C)

3750

(D)

4044

(E)

4319

풀이 과정

전략 극단의 원리

조건이 가리키는 비교의 개수가 엄청나게 많아서 한 쌍씩 확인하는 것은 가망이 없다. 그래서 먼저 나머지들을 하나의 목록으로 모으고, 커지는 목록이 도대체 어떤 모습일 수 있는지를 묻는다. 문제가 갈라지는 지점이 바로 여기다. 목록의 항 수와 쓸 수 있는 나머지의 개수가 똑같아서 여유가 전혀 없고, 따라서 목록은 0, 1, 2, …, z-1 순서로 강제된다. 그다음부터는 대수 작업이다. 강제된 등식이 2024에 대한 나눗셈 조건으로 바뀌고, 남는 일은 2024를 소인수분해해 약수를 더하는 익숙한 작은 문제뿐이다.

1STEP 1

나머지를 하나의 목록으로 모으기

나머지를 하나의 목록으로 모읍니다.

R(x) = 2025x mod z, R(0) ＜ R(1) ＜ … ＜ R(z-1)

2STEP 2

목록에는 건너뛸 자리가 없다

자리가 딱 맞아 나머지가 곧 x여야 합니다.

R(0) ＜ R(1) ＜ … ＜ R(z-1) 안에 {0, 1, …, z-1} → R(x) = x

3STEP 3

강제된 목록을 나눗셈 조건으로 바꾸기

이는 z가 2024를 나눔과 같습니다.

2025x ≡ x (mod z) ⇔ z ∣ 2024x, x = 1 → z ∣ 2024

4STEP 4

반대 방향도 확인하기

반대 방향도 성립합니다.

z ∣ 2024 → 2025 ≡ 1 (mod z) → 0 ≤ x ＜ z 에서 R(x) = x

5STEP 5

2024를 소인수로 쪼개기

2024는 2의 세제곱 곱하기 11 곱하기 23입니다.

2024 = 2³ · 11 · 23, 4 · 2 · 2 = 16 개의 약수

6STEP 6

약수를 더한 뒤 1을 빼기

약수의 합에서 1을 빼면 4319입니다.

(1 + 2 + 4 + 8)(1 + 11)(1 + 23) = 15 · 12 · 24 = 4320, 4320 - 1 = 4319

정답

4319

규칙의 양쪽을 짚어 보자. 2024의 약수인 z = 2에서는 목록이 R(0) = 0, R(1) = 1로 커진다. 2024의 약수가 아닌 z = 3에서는 2025가 3의 배수이므로 R(0) = 0, R(1) = 0이 되어 첫 단계에서 바로 무너진다. 살아남는 값을 직접 나열하면 2, 4, 8, 11, 22, 23, 44, 46, 88, 92, 184, 253, 506, 1012, 2024로 15개이며, 이는 약수 16개에서 제외한 1을 뺀 개수와 정확히 맞고 손으로 더해도 4319가 나온다. 이 값이 2024의 전체 약수 합인 4320보다 딱 1 작다는 점도 논증이 예측한 모습 그대로다.

💡핵심 정리

증가하는 목록의 항 수가 쓸 수 있는 값의 개수와 똑같으면 하나도 건너뛸 수 없어 0, 1, 2, ... 순서일 수밖에 없다. 이 빈틈없는 압박이 나머지에 관한 무서운 규칙을 '무엇이 2024를 나누는가'라는 단순한 질문으로 바꿔 준다.

나머지를 하나의 목록으로 모으기
목록에는 건너뛸 자리가 없다
강제된 목록을 나눗셈 조건으로 바꾸기
반대 방향도 확인하기
2024를 소인수로 쪼개기
약수를 더한 뒤 1을 빼기