AMC 10 · 2024 · #18

Grade 8 arithmetic

modular-arithmeticexponentseulers-theoremprime-factorization complementary-countingidentify-subproblemscasework ↑ Prerequisites: modular-arithmeticexponentsprime-factorization

📏 Medium solution 💡 3 insights

Problem

How many different remainders can result when the $100$ th power of an integer is
divided by $125$ ?

$\textbf{(A) } 1 \qquad\textbf{(B) } 2 \qquad\textbf{(C) } 5 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 125$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

125

View mode:

Toolkit + CCSS Solution

Understand

Restated: Let $n$ range over every integer. How many distinct remainders can the expression $n^{100} \bmod 125$ take?

Givens: $n$ is an integer (positive, negative, or zero); The divisor is $125 = 5^3$; The exponent is $100$; $\phi(125) = 5^3 - 5^2 = 100$ (Euler's totient — used as a known fact for the coprime case); Answer choices: (A) $1$, (B) $2$, (C) $5$, (D) $25$, (E) $125$

Unknowns: The number of distinct values of $n^{100} \pmod{125}$ as $n$ ranges over the integers

Understand

Restated: Let $n$ range over every integer. How many distinct remainders can the expression $n^{100} \bmod 125$ take?

Plan

Primary tool: #16 Change Focus / Count the Complement

Secondary: #7 Identify Subproblems, #9 Solve an Easier Related Problem

Every integer either shares the prime $5$ with $125$ or it does not — Tool #16 (Change Focus) reframes the problem by that dichotomy and turns one hard question into two easy ones. Tool #7 (Identify Subproblems) then handles each case: (a) $n$ coprime to $125$ (no factor of $5$) — here Euler's theorem nails $n^{100} \equiv 1 \pmod{125}$ in one line because $\phi(125) = 100$; (b) $n$ is a multiple of $5$ — then $n^{100} = 5^{100} k^{100}$, divisible by $5^{100} \gg 5^3 = 125$, so the remainder is $0$. Tool #9 (Solve an Easier Related Problem) checks the coprime conclusion on a small case ($n = 2$) before trusting the general theorem, so the answer is grounded, not hand-waved.

Execute — Answer: B

#16 Change Focus / Count the Complement 6.NS.B.4 Step 1

Split by the only prime that matters.
The divisor is $125 = 5^3$, so the only prime to worry about is $5$.
Every integer $n$ falls in exactly one of two buckets: $\gcd(n, 125) = 1$ (no factor of $5$) or $5 \mid n$.

$$\text{integers} = \{n : 5 \nmid n\} \sqcup \{n : 5 \mid n\}$$

💡 Choosing the dividing line by the prime factorization of $125$ is the Grade 6 GCF/LCM mindset — only $5$ matters.

#7 Identify Subproblems 8.EE.A.1 Step 2

Case A: $5 \nmid n$, so $n$ is coprime to $125$.
Euler's theorem gives $n^{\phi(125)} \equiv 1 \pmod{125}$, and the totient is $\phi(125) = 5^3 - 5^2 = 125 - 25 = 100$.
The exponent in the problem is exactly $100$, so $n^{100} \equiv 1 \pmod{125}$ for every such $n$.

$$\phi(125) = 5^3 - 5^2 = 100, \quad n^{100} \equiv 1 \pmod{125}$$

💡 When the exponent matches $\phi$ of the modulus, the power lands on $1$ for every coprime base — a clean Grade 8 integer-exponent fact.

#9 Solve an Easier Related Problem 8.EE.A.1 Step 3

Verify Case A on a small concrete value.
Try $n = 2$ (coprime to $125$): $2^{10} = 1024 = 8 \cdot 125 + 24$, so $2^{10} \equiv 24 \pmod{125}$.
Then $2^{100} = (2^{10})^{10} \equiv 24^{10} \pmod{125}$.
Squaring step by step: $24^2 = 576 \equiv 76$, $24^4 \equiv 76^2 = 5776 \equiv 26$, $24^5 \equiv 24 \cdot 26 = 624 \equiv 124 \equiv -1$, so $24^{10} \equiv (-1)^2 = 1 \pmod{125}$.
Confirmed: $2^{100} \equiv 1 \pmod{125}$.

$$2^{10} \equiv 24, \; 24^5 \equiv -1, \; 2^{100} \equiv (-1)^2 = 1 \pmod{125}$$

💡 A small-case check on $n = 2$ confirms the general Euler conclusion without trusting a theorem name in the dark.

#7 Identify Subproblems 8.EE.A.1 Step 4

Case B: $5 \mid n$.
Write $n = 5m$ for some integer $m$.
Then $n^{100} = (5m)^{100} = 5^{100} \cdot m^{100}$.
Since $5^{100}$ is divisible by $5^3 = 125$ (in fact by a much higher power), $n^{100}$ is a multiple of $125$, giving remainder $0$.

$$n^{100} = 5^{100} m^{100} = 125 \cdot 5^{97} m^{100} \equiv 0 \pmod{125}$$

💡 A single factor of $5^3$ inside $5^{100}$ already eats the modulus — the rest just goes along for the ride.

#16 Change Focus / Count the Complement 5.OA.A.2 Step 5

Combine the two cases.
Every integer $n$ lands in exactly one case, and the only remainders that appear are $0$ (Case B) and $1$ (Case A).
So the set of possible remainders is $\{0, 1\}$ — $2$ values.

$$\{n^{100} \bmod 125 : n \in \mathbb{Z}\} = \{0, \; 1\}, \quad |\{0,1\}| = 2 \;\Rightarrow\; \textbf{(B)}$$

💡 The complement-style split lined up so each side contributes exactly one remainder — Grade 5 "write the answer as a small set".

[1] #16 6.NS.B.4 Split by the only prime that matters. The divisor is $125 = 5^3$, so the only pr

[2] #7 8.EE.A.1 Case A: $5 \nmid n$, so $n$ is coprime to $125$. Euler's theorem gives $n^{\phi(

[3] #9 8.EE.A.1 Verify Case A on a small concrete value. Try $n = 2$ (coprime to $125$): $2^{10}

[4] #7 8.EE.A.1 Case B: $5 \mid n$. Write $n = 5m$ for some integer $m$. Then $n^{100} = (5m)^{1

[5] #16 5.OA.A.2 Combine the two cases. Every integer $n$ lands in exactly one case, and the only

Review

Reasonableness: Both remainders are attained: $n = 5$ gives $5^{100}$, divisible by $125$, remainder $0$; $n = 1$ gives $1^{100} = 1$, remainder $1$. Both values are in $\{0, 1, \dots, 124\}$ and lie in the legal remainder range. The five answer choices include $1$, $2$, $5$, $25$, $125$ — exactly the small divisor-like numbers one would expect from a guess; $\{0, 1\}$ has size $2$, matching (B). Quick sanity for Case A on another base: $n = 3$: $3^5 = 243 \equiv 243 - 125 = 118 \equiv -7 \pmod{125}$, then $3^{10} \equiv 49$, $3^{20} \equiv 49^2 = 2401 = 19 \cdot 125 + 26 \equiv 26$, $3^{50} \equiv 26^2 \cdot 49 \equiv 676 \cdot 49 \equiv 51 \cdot 49 = 2499 \equiv -1$, so $3^{100} \equiv 1 \pmod{125}$. Same answer, confirming Case A.

Alternative: Tool #5 (Look for a Pattern) on the table of $n^{100} \bmod 125$ for $n = 0, 1, 2, \dots, 10$: the values are $0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0$. The pattern "$0$ whenever $5 \mid n$, otherwise $1$" jumps right out, even without invoking Euler by name. Same conclusion: $2$ distinct remainders.

CCSS standards used (min grade 8)

6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Identifying $5$ as the only prime in $125 = 5^3$ to split every integer $n$ into the coprime case and the multiple-of-$5$ case.)
8.EE.A.1 Know and apply the properties of integer exponents (Applying Euler's theorem $n^{\phi(125)} \equiv 1 \pmod{125}$ for the coprime case and using $(5m)^{100} = 5^{100} m^{100}$ for the multiple-of-$5$ case.)
5.OA.A.2 Write simple expressions that record calculations with numbers (Recording the answer as the set $\{0, 1\}$ and reading off its size $2$.)

⭐ This AMC 10 problem only needs the Grade 8 integer-exponent rule and a clean "is $n$ a multiple of $5$ or not?" split — and the answer set turns out to be just $\{0, 1\}$!

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: B

Review

CCSS standards used (min grade 8)

More like this