AMC 10 · 2021 · #10

학년 8 number-theory
유형 Modular Cycle Frequency Count └ 세부 유형 Power-Cycle Residue
base-conversionmodular-arithmeticplace-valueexponents easier-related-problempattern-recognition ↑ 선수 지식: base-conversionmodular-arithmetic
📏 중간 풀이 💡 3 개 인사이트
문제
어떤 수가 9진법으로 열한 자리로 적혀 있습니다. 10진법으로 바꾸면 아주 큰 수입니다. 10진법 값을 전혀 구하지 않고 이 수를 5로 나눈 나머지를 구하세요.

답을 골라 클릭하세요.

(A)
0
(B)
1
(C)
2
(D)
3
(E)
4
풀이 과정
전략 더 쉬운 문제로 줄이기

9진법 표기를 통째로 10진법으로 바꾸려면 10자리 수인 9¹0을 계산하고 큰 곱을 네 개 더 더해야 한다. 그러나 묻는 것은 나머지뿐이므로 그 계산은 필요 없다. 나머지는 곱셈과 덧셈에서 그대로 살아남는다. 두 수가 5로 나눈 나머지가 같으면 그 합과 곱의 나머지도 같기 때문이다. 그래서 전개식에 있는 9를 각각 그 9가 남기는 작은 수로 바꾸면, 거대한 계산이 한 자리 조각들로 이루어진 더 쉬운 문제로 바뀐다. 이 교체를 하고 나면 9의 거듭제곱이 짧게 반복되는 패턴에 빠지고, 문제 전체가 열한 개의 숫자에 부호를 붙여 더하는 일로 줄어든다.

1STEP 1

9진법 표기를 펼치기

표기를 거듭제곱의 합으로 펼칩니다.

N = 2 · 9¹⁰ + 7 · 9⁹ + 6 · 9⁶ + 5 · 9¹ + 2 · 9⁰
2STEP 2

9를 그것이 남기는 값으로 바꾸기

9는 5로 나누면 마이너스 1과 같습니다.

9 = 5 + 4 ≡ 4 (mod 5), 9 = 10 - 1 ≡ -1 (mod 5)
3STEP 3

9의 거듭제곱은 번갈아 나타난다

거듭제곱이 번갈아 나타납니다.

9^k ≡ (-1)^k (mod 5), 9^k ≡ 1 if k is even, 9^k ≡ -1 if k is odd
4STEP 4

숫자에 부호를 번갈아 붙여 더하기

부호를 번갈아 붙여 더합니다.

N ≡ 2(1) + 7(-1) + 6(1) + 5(-1) + 2(1) = 2 - 7 + 6 - 5 + 2 = -2 (mod 5)
5STEP 5

마이너스 2를 진짜 나머지로 바꾸기

음수를 진짜 나머지로 바꾸면 3입니다.

-2 ≡ -2 + 5 = 3 (mod 5), 0 ≤ 3 ＜ 5
정답
3
마이너스 1 대신 4를 써서 다시 계산해도 답은 같아야 한다. 9의 나머지가 4이고 4의 제곱은 16이라 나머지가 1이므로, 9의 거듭제곱은 지수 0, 1, 2, 3에 대해 나머지가 1, 4, 1, 4로 반복된다. 따라서 짝수 자리는 9¹0 자리의 2 곱하기 1, 9⁶ 자리의 6 곱하기 1, 1의 자리의 2 곱하기 1을 주고, 홀수 자리는 7 곱하기 4와 5 곱하기 4를 준다. 합은 2 + 28 + 6 + 20 + 2 = 58이고 58 = 11 곱하기 5 더하기 3이므로 나머지는 다시 3이다. 두 경로가 일치하고 3은 0부터 4까지의 허용 범위 안에 있으므로 값이 일관된다.
💡핵심 정리

나머지를 구할 때는 거대한 수를 만들지 말고, 밑을 그것이 남기는 작은 수로 바꿔라. 그러면 거듭제곱이 짧게 반복되는 패턴으로 무너진다.

  • 9진법 표기를 펼치기
  • 9를 그것이 남기는 값으로 바꾸기
  • 9의 거듭제곱은 번갈아 나타난다
  • 숫자에 부호를 번갈아 붙여 더하기
  • 마이너스 2를 진짜 나머지로 바꾸기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.