AMC 10 · 2017 · #14

Grade 7 probability

Archetype Modular Cycle Frequency Count └ Sub-archetype Power-Cycle Residue

modular-arithmeticunits-digit-trackingprobability-basic pattern-recognitioneulers-theorem ↑ Prerequisites: modular-arithmetic

📏 Medium solution 💡 2 insights

Problem

An integer N is chosen at random from 1 ≤ N ≤ 2020, every value equally likely. Find the probability that N¹⁶ leaves a remainder of 1 when divided by 5.

Pick an answer.

(A)

$\frac{1}{5}$

(B)

$\frac{2}{5}$

(C)

$\frac{3}{5}$

(D)

$\frac{4}{5}$

(E)

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

How to solve

Strategy Look for a Pattern

N¹⁶ for N up to 2020 is astronomically large, so Tool #9 (Solve an Easier Related Problem) shrinks it: the remainder of a product divided by 5 depends only on the remainders of its parts, so the answer depends only on the remainder of N divided by 5 — just five cases 0,1,2,3,4. Tool #5 (Look for a Pattern): inside each case the remainders of the powers march in a short repeating cycle, so we never compute the giant power, we only see where the 16th step lands. Tool #2 (Make a Systematic List) lays the five cases side by side, and Tool #7 (Identify Subproblems) turns "count the winners from 1 to 2020" into the easy sub-task of counting multiples of 5.

1STEP 1

Only the remainder of N matters

The remainder of N¹⁶ divided by 5 depends only on N's remainder, so check just the five cases N ≡ 0, 1, 2, 3, 4 instead of all 2020 numbers.

N¹⁶ mod 5 depends only on N mod 5∈{0,1,2,3,4}

2STEP 2

Track the cycle in each case

Powers mod 5 loop in a short cycle and 16 ends each cycle, so 2¹⁶, 3¹⁶, 4¹⁶ all leave remainder 1, while 1 stays 1 and 0 stays 0.

2¹⁶,3¹⁶,4¹⁶≡ 1, 1¹⁶≡ 1, 0¹⁶≡ 0 (mod 5)

3STEP 3

Find which N win

The four nonzero cases all give remainder 1 and only N ≡ 0 fails, so N¹⁶ leaves remainder 1 exactly when N is not a multiple of 5.

N¹⁶≡ 1 (mod 5) ⇔ 5 ∤ N

4STEP 4

Count and divide

From 1 to 2020 there are 2020 ÷ 5 = 404 multiples of 5, leaving 2020 − 404 = 1616 winners, so the probability is 1616/2020 = 4/5 → (D).

(2020-404)/2020=1616/2020=4/5 → (D)

Answer

4/5

Of the five equally likely remainder groups 0,1,2,3,4, exactly four succeed and one (multiples of 5) fails, pointing straight to 4/5. Because 2020=5× 404 the five groups split the range evenly, so the count 1616/2020 reduces cleanly to 4/5 with no remainder fudge. The value 4/5=0.8 sits between 0 and 1 and is large, which fits: only the multiples of 5 are knocked out.

💡Key takeaway

Only N's remainder mod 5 matters, and N¹⁶ leaves remainder 1 for every N except the multiples of 5 — that is 4/5 of them, choice (D).

Only the remainder of N matters
Track the cycle in each case
Find which N win
Count and divide

Only the remainder of N matters

Track the cycle in each case

Find which N win

Count and divide

More like this