AMC 10 · 2022 · #21

학년 9 algebra

유형 Modular Cycle Frequency Count └ 세부 유형 Power-Cycle Residue

polynomial-factoringpolynomial-substitutiondifference-of-cubesroots-of-unitymodular-arithmetic easier-related-problemconvert-to-algebrapattern-recognition ↑ 선수 지식: polynomial-factoring

📏 긴 풀이 💡 3 개 인사이트

문제

아주 높은 차수의 다항식이 주어집니다. 다섯 보기 중에서 이 다항식을 나머지 없이 나누는 것을 고르세요.

답을 골라 클릭하세요.

(A)

$x^2 -x + 1$

(B)

$x^2 + x + 1$

(C)

$x^4 + 1$

(D)

$x^6 - x^3 + 1$

(E)

$x^6 + x^3 + 1$

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #9(더 쉬운 문제로 줄이기) — 2022 같은 지수는 곧이곧대로 다룰 때만 무섭습니다. 나누는 식이 거듭제곱을 짧은 주기로 반복시키면 거대한 지수는 나머지로 줄어들고, 문제는 한 자리 수 계산으로 축소됩니다. 도구 #4(변수 도입하기) — 두 지수 모두 3의 배수이므로 u = x³로 치환하면 P 는 u⁶⁷⁴ + u³³⁷ + 1이 되고 선택지 (E)는 익숙한 u² + u + 1이 됩니다. 도구 #5(패턴 찾기) — u² + u + 1은 u³ - 1의 인수라서 u 의 거듭제곱이 주기 3으로 순환합니다. 도구 #13(대수로 바꾸기) — 순환 관찰을 명시적 항등식으로 바꿔 나누어떨어짐을 추측이 아니라 증명으로 만듭니다. 도구 #3(가능성 지우기) — x = 2 한 번 대입으로 나머지 네 선택지를 한꺼번에 배제합니다.

1STEP 1

치환으로 지수 줄이기

치환으로 지수를 줄입니다.

P(x) = (x³)⁶⁷⁴ + (x³)³³⁷ + 1 = u⁶⁷⁴ + u³³⁷ + 1, x⁶ + x³ + 1 = u² + u + 1

2STEP 2

순환 주기 찾기

순환 주기를 찾습니다.

u³ - 1 = (u - 1)(u² + u + 1)

3STEP 3

674와 337을 3으로 나눈 나머지

지수를 주기로 나눈 나머지를 봅니다.

674 = 3 · 224 + 2, 337 = 3 · 112 + 1

4STEP 4

나누어떨어짐을 정확히 보이기

나누어떨어짐을 정확히 보입니다.

u⁶⁷⁴ + u³³⁷ + 1 = (u² + u + 1) + u²(u⁶⁷² - 1) + u(u³³⁶ - 1)

5STEP 5

x = 2로 한 번에 점검

수 하나로 점검합니다.

P(2) mod 3 = 1, P(2) mod 7 = 3, P(2) mod 17 = 5, P(2) mod 57 = 16, P(2) mod 73 = 0

6STEP 6

답 읽어내기

답은 6차식입니다.

x²⁰²² + x¹⁰¹¹ + 1 = (x⁶ + x³ + 1) · Q(x) → (E)

7STEP 7

차수로 검산

차수로 검산합니다.

(x¹⁰¹¹ - 1)P(x) = x³⁰³³ - 1, deg Q = 2022 - 6 = 2016

정답

x⁶ + x³ + 1

x = 2 수치 검사는 결정적이고 다시 해보기도 쉽습니다: 2⁶ + 2³ + 1 = 73이고 2⁹ = 512 = 7 · 73 + 1 이므로 2⁹ ≡ 1 (mod 73). 2022 = 9 · 224 + 6, 1011 = 9 · 112 + 3 이므로 거대한 수 2²⁰²² + 2¹⁰¹¹ + 1은 2⁶ + 2³ + 1 = 73 ≡ 0과 같은 나머지를 남깁니다. 즉 73이 P(2)를 정확히 나눕니다 — 대수 조작이 만들어낸 착시가 아닙니다. x = 3으로 해도 마찬가지입니다: 3⁶ + 3³ + 1 = 757이고 3⁹ = 19683 = 26 · 757 + 1 이므로 다시 P(3) ≡ 3⁶ + 3³ + 1 ≡ 0. 반면 다른 선택지는 모두 x = 2 에서 0이 아닌 나머지로 탈락했고, 특히 (B)의 탈락 방식이 교훈적입니다: x² + x + 1은 x³을 1 처럼 만드는데 3이 2022와 1011을 모두 나누므로 P 는 1 + 1 + 1 = 3으로 무너지고 결코 0이 되지 않습니다. (B)와 (E) 사이의 아슬아슬한 차이가 이 문제의 핵심입니다.

💡핵심 정리

2022 같은 지수는 순환을 찾는 순간 무섭지 않아요 — u = x³로 치환하고, u² + u + 1이 u³을 1 처럼 만든다는 걸 알아채고, 674와 337을 나머지 2와 1로 줄이면 거대한 다항식이 u² + u + 1 = 0으로 무너져 x⁶ + x³ + 1이 인수임이 드러나요.

치환으로 지수 줄이기
순환 주기 찾기
674와 337을 3으로 나눈 나머지
나누어떨어짐을 정확히 보이기
x = 2로 한 번에 점검
답 읽어내기
차수로 검산