AMC 10 · 2022 · #17

학년 8 number-theory

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

divisibility-rulesmodular-arithmeticexponentsprime-numberspolynomial-factoring pattern-recognitioneasier-related-problemcasework ↑ 선수 지식: modular-arithmeticprime-numbers

📏 긴 풀이 💡 3 개 인사이트

문제

One of the following numbers is not divisible by any prime number less than $10.$ Which is it?

답을 골라 클릭하세요.

(A)

$2^{606}-1$

(B)

$2^{606}+1$

(C)

$2^{607}-1$

(D)

$2^{607}+1$

(E)

$2^{607}+3^{607}$

AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 다섯 개의 식 중 네 개는 소수 $\{2, 3, 5, 7\}$ 중 하나로 나누어 떨어지고, 단 하나는 그렇지 않습니다. 작은 소인수를 가지지 않는 식을 찾으세요.

주어진 것: 다섯 후보: $2^{606}-1,\ 2^{606}+1,\ 2^{607}-1,\ 2^{607}+1,\ 2^{607}+3^{607}$; $10$ 미만 소수는 $2, 3, 5, 7$; 모든 후보가 홀수 ($2$의 거듭제곱은 짝수, 짝수 $\pm 1$ 은 홀수, 짝수 $+$ 홀수도 홀수) 이므로 $2$ 로 나누어 떨어질 가능성은 자동 제거

구하는 것: (A)–(E) 중 $2, 3, 5, 7$ 어느 것으로도 나누어 떨어지지 않는 식

이해

계획

주요 도구: #3 가능성 지우기

보조 도구: #5 패턴 찾기, #9 더 쉬운 문제로 줄이기

도구 #3 (지우기): 다섯 후보가 우주, $2, 3, 5, 7$ 중 하나로 잘 나누어 떨어지는 것부터 지웁니다. 도구 #9 (더 쉬운 문제): 지수를 $607$ 대신 $7$ 로 바꿔 $2^n \pm 1$ 의 행동을 미리 관찰 — 같은 패턴이 큰 지수에서도 그대로 적용됩니다. 도구 #5 (패턴): $2 \bmod p$ 가 주기를 가지므로 "$2^{607} \bmod p$" 는 "$607 \bmod (\text{주기 길이})$" 만 알면 표에서 바로 읽힙니다. 네 후보는 한 줄로 떨어지고, 남은 하나는 직접 검증.

실행 — 정답: C

#3 가능성 지우기 6.NS.B.4 단계 1

(A) $2^{606}-1$ 을 $3$ 으로 지우기.
$2 \equiv -1 \pmod 3$ 이고 $606$ 이 짝수이므로 $2^{606} \equiv (-1)^{606} = 1$, 따라서 $2^{606} - 1 \equiv 0 \pmod 3$.

$$2^{606} - 1 \equiv 1 - 1 \equiv 0 \pmod 3$$

💡 $2 \equiv -1 \pmod 3$ 이면 "지수가 짝수인가?" 만 보면 되고, $606$ 은 짝수.

#3 가능성 지우기 8.EE.A.1 단계 2

(D) $2^{607}+1$ 을 $3$ 으로 지우기.
같은 방법: $2^{607} \equiv (-1)^{607} = -1$, 따라서 $2^{607} + 1 \equiv 0 \pmod 3$.
(같은 말: 홀수 $n$ 에 대해 $a^n + b^n$ 은 $a + b$ 로 나누어 떨어지고, $2 + 1 = 3$.)

$$2^{607} + 1 \equiv -1 + 1 \equiv 0 \pmod 3$$

💡 홀수 지수는 $-1$ 을 그대로 남기고, 거기에 $1$ 을 더하면 $3$ 의 배수.

#3 가능성 지우기 8.EE.A.1 단계 3

(E) $2^{607}+3^{607}$ 을 $5$ 로 지우기.
홀수 $n$ 에 대해 $a^n + b^n$ 이 $a + b$ 로 나누어 떨어진다는 항등식.
$a = 2$, $b = 3$, $n = 607$ 홀수, $a + b = 5$.

$$2^{607} + 3^{607} \equiv 0 \pmod 5$$

💡 두 거듭제곱 합 (홀수 차수) 은 두 밑의 합으로 나누어 떨어짐.

#3 가능성 지우기 8.EE.A.1 단계 4

(B) $2^{606}+1$ 을 $5$ 로 지우기.
$2^{606} = (2^2)^{303} = 4^{303}$ 로 다시 쓰면 $2^{606} + 1 = 4^{303} + 1$.
$a = 4$, $b = 1$, $n = 303$ 홀수, $a + b = 5$ 이므로 $4^{303} + 1$ 은 $5$ 의 배수.

$$2^{606} + 1 = 4^{303} + 1^{303} \equiv 0 \pmod 5$$

💡 지수를 둘씩 묶어 밑을 $4$ 로 만든 뒤 $4 + 1 = 5$ 가 일을 합니다.

#3 가능성 지우기 4.OA.B.4 단계 5

소거 후 남은 답은 (C) $2^{607} - 1$.
네 소수 각각에 대해 직접 검증.
$2$ 로 나누어 떨어짐?
$2^{607}$ 이 짝수이므로 $2^{607} - 1$ 은 홀수 — 안 나누어 떨어짐.

$2^{607} - 1$ 은 홀수

💡 짝수에서 $1$ 을 빼면 홀수.

#5 패턴 찾기 6.NS.B.4 단계 6

$\bmod 3$ 으로 (C) 검증.
$2 \equiv -1$, $607$ 홀수 이므로 $2^{607} \equiv -1$, 따라서 $2^{607} - 1 \equiv -2 \equiv 1 \pmod 3$ — 안 나누어 떨어짐.

$$2^{607} - 1 \equiv -1 - 1 \equiv 1 \pmod 3$$

💡 같은 $-1$ 트릭이지만 이번엔 홀수 지수가 $-1$ 을 남기고, $-1 - 1 = -2$ 는 $3$ 의 배수가 아님.

#5 패턴 찾기 6.NS.B.4 단계 7

$\bmod 5$ 검증.
거듭제곱 $2, 4, 8, 16 \equiv 2, 4, 3, 1 \pmod 5$ — 주기 $4$.
$607 = 4 \cdot 151 + 3$ 이므로 $2^{607} \equiv 2^3 = 8 \equiv 3 \pmod 5$, 따라서 $2^{607} - 1 \equiv 2 \pmod 5$ — 안 나누어 떨어짐.

$$607 \bmod 4 = 3 \Rightarrow 2^{607} \equiv 3 \Rightarrow 2^{607} - 1 \equiv 2 \pmod 5$$

💡 $2 \bmod 5$ 는 $4$ 걸음마다 한 바퀴, $607$ 이 주기에서 어디에 떨어지는지만 확인.

#5 패턴 찾기 6.NS.B.4 단계 8

$\bmod 7$ 검증.
거듭제곱 $2, 4, 8 \equiv 2, 4, 1 \pmod 7$ — 주기 $3$.
$607 = 3 \cdot 202 + 1$ 이므로 $2^{607} \equiv 2 \pmod 7$, 따라서 $2^{607} - 1 \equiv 1 \pmod 7$ — 안 나누어 떨어짐.
(C) 가 모든 검사를 통과.
답: $\textbf{(C)}\ 2^{607} - 1$.

$$607 \bmod 3 = 1 \Rightarrow 2^{607} \equiv 2 \Rightarrow 2^{607} - 1 \equiv 1 \pmod 7$$

💡 같은 주기 사용, 이번엔 길이가 $3$.

[1] #3 6.NS.B.4 (A) $2^{606}-1$ 을 $3$ 으로 지우기. $2 \equiv -1 \pmod 3$ 이고 $606$ 이 짝수이므로 $2^{606} \e

[2] #3 8.EE.A.1 (D) $2^{607}+1$ 을 $3$ 으로 지우기. 같은 방법: $2^{607} \equiv (-1)^{607} = -1$, 따라서 $2^{6

[3] #3 8.EE.A.1 (E) $2^{607}+3^{607}$ 을 $5$ 로 지우기. 홀수 $n$ 에 대해 $a^n + b^n$ 이 $a + b$ 로 나누어 떨어진다는

[4] #3 8.EE.A.1 (B) $2^{606}+1$ 을 $5$ 로 지우기. $2^{606} = (2^2)^{303} = 4^{303}$ 로 다시 쓰면 $2^{606}

[5] #3 4.OA.B.4 소거 후 남은 답은 (C) $2^{607} - 1$. 네 소수 각각에 대해 직접 검증. $2$ 로 나누어 떨어짐? $2^{607}$ 이 짝수이므

[6] #5 6.NS.B.4 $\bmod 3$ 으로 (C) 검증. $2 \equiv -1$, $607$ 홀수 이므로 $2^{607} \equiv -1$, 따라서 $2^{60

[7] #5 6.NS.B.4 $\bmod 5$ 검증. 거듭제곱 $2, 4, 8, 16 \equiv 2, 4, 3, 1 \pmod 5$ — 주기 $4$. $607 = 4 \c

[8] #5 6.NS.B.4 $\bmod 7$ 검증. 거듭제곱 $2, 4, 8 \equiv 2, 4, 1 \pmod 7$ — 주기 $3$. $607 = 3 \cdot 202

검토

합리성 확인: 네 후보는 한 줄짜리 깔끔한 논증으로 제거되었고 (mod $3$ 두 번, mod $5$ 두 번), 남은 (C) 는 네 소수 각각에 대해 독립적으로 검증을 통과했습니다. 참고로 $2^{607} - 1$ 은 Mersenne 소수 (자기 자신이 가장 작은 소인수) — 다만 우리는 "작은 소인수가 없다" 만 보였으면 충분.

대안 접근: 도구 #9 (더 쉬운 문제) 단독: 지수 $606, 607$ 를 $6, 7$ 로 바꿔 표를 만든다. $2^6 - 1 = 63 = 9 \cdot 7$ (mod 3, 7 죽음), $2^6 + 1 = 65 = 5 \cdot 13$ (mod 5 죽음), $2^7 - 1 = 127$ (소수 — 작은 인수 없음!), $2^7 + 1 = 129 = 3 \cdot 43$, $2^7 + 3^7 = 128 + 2187 = 2315 = 5 \cdot 463$. 지수 $7$ 표만으로도 (C) 가 답임을 알 수 있고, 지수 $607$ 논증은 같은 패턴의 확대판.

사용된 CCSS 표준 (최저 학년 8)

6.NS.B.4 두 수의 최대공약수·최소공배수 구하기 (소수 $3$, $5$, $7$ 에 대한 모듈러 나눗셈 검사 — $2$ 의 거듭제곱 주기 활용.)
8.EE.A.1 정수 지수의 성질 알고 적용 ($2^{606} = 4^{303}$ 재작성 및 홀수 $n$ 에 대한 $a^n + b^n$ 항등식 적용.)
4.OA.B.4 약수쌍·배수 찾기 및 소수·합성수 판별 ($2^{607}$ 이 짝수이므로 $2^{607} - 1$ 이 홀수 (즉 $2$ 로 안 나누어 떨어짐) 임을 확인.)

⭐ 다섯 후보 중 넷은 한 줄로 제거 — 홀수 $n$ 에서 $a^n + b^n$ 이 $a + b$ 의 배수, 그리고 $2 \equiv -1 \pmod 3$ 이라는 사실 두 가지면 충분. 살아남은 $2^{607} - 1$ 은 $2, 3, 5, 7$ 어느 것으로도 나누어 떨어지지 않으니 답은 $\textbf{(C)}$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

사용된 CCSS 표준 (최저 학년 8)

비슷한 유형 더 풀어보기