AMC 10 · 2010 · #24

Grade 8 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

legendre-formulachinese-remainder-theoremeulers-theoremmodular-arithmeticfactorial identify-subproblems ↑ Prerequisites: modular-arithmetic

📏 Long solution 💡 4 insights

Problem

The number obtained from the last two nonzero digits of $90!$ is equal to $n$ . What is $n$ ?

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

Try it yourself first — the explanation is most useful after you’ve attempted it.

View mode:

Toolkit + CCSS Solution

Understand

Restated: Write out $90!$ (the product $1\cdot 2\cdot 3\cdots 90$). It ends in a run of zeros. Ignore those trailing zeros and read the two digits just before them. Those two digits form a number $n$; find $n$.

Givens: $90! = 1\cdot 2\cdot 3\cdots 90$; We take the last two digits that are not part of the ending run of zeros; Answer choices: (A) $12$, (B) $32$, (C) $48$, (D) $52$, (E) $68$

Unknowns: The two-digit number $n$ formed by the last two nonzero digits of $90!$

Understand

Givens: $90! = 1\cdot 2\cdot 3\cdots 90$; We take the last two digits that are not part of the ending run of zeros; Answer choices: (A) $12$, (B) $32$, (C) $48$, (D) $52$, (E) $68$

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #7 Identify Subproblems, #5 Look for a Pattern

Tool #9 (Solve an Easier Related Problem): the full number $90!$ is impossible to compute, so replace it with a much smaller question about remainders. The last two nonzero digits are $N \bmod 100$, where $N$ is $90!$ with its trailing zeros removed. Tool #7 (Identify Subproblems): $100 = 4\times 25$ with $4$ and $25$ sharing no factors, so split the one hard remainder into an easy $N \bmod 4$ and a harder $N \bmod 25$, then reassemble. Tool #5 (Look for a Pattern): mod $25$, each clean block of $25$ consecutive numbers leaves the same footprint, and the powers of $2$ repeat in a short cycle — patterns that collapse the huge product to a few small steps.

Execute — Answer: A

#9 Solve an Easier Related Problem 5.NBT.A.2 Step 1

Count and strip the trailing zeros

A zero appears at the end of a number for every factor of $10 = 2\times 5$ inside it.
In $90!$ there are far more factors of $2$ than of $5$, so the number of ending zeros equals the number of factors of $5$.
Count multiples of $5$ up to $90$ (there are $18$), then add one extra $5$ for each multiple of $25$, namely $25,50,75$ (that is $3$ more).
So $90!$ ends in exactly $21$ zeros.
Strip them off: let $N = 90!/10^{21}$.
The last two nonzero digits of $90!$ are the last two digits of $N$, that is $N \bmod 100$.

$$\left\lfloor \tfrac{90}{5} \right\rfloor + \left\lfloor \tfrac{90}{25} \right\rfloor = 18 + 3 = 21,\qquad N = \dfrac{90!}{10^{21}}$$

💡 Every trailing zero is one $2$ paired with one $5$, and the $5$s are the scarce partner, so counting $5$s counts the zeros.

#7 Identify Subproblems 6.NS.B.4 Step 2

Split the target into a 4-clock and a 25-clock

Since $100 = 4\times 25$ and $4$ and $25$ share no common factor, knowing $N \bmod 4$ and $N \bmod 25$ pins down $N \bmod 100$ exactly.
The mod $4$ part is easy: $90!$ contains $45+22+11+5+2+1 = 86$ factors of $2$, and stripping the zeros removed only $21$ of them, leaving $65$.
Since $65 \ge 2$, $N$ is divisible by $4$, so $N \equiv 0 \pmod 4$.
All the real work is the mod $25$ part.

$$100 = 4\cdot 25,\ \gcd(4,25)=1;\quad \#\text{twos} = 86,\ 86-21 = 65 \ge 2 \Rightarrow N \equiv 0 \pmod 4$$

💡 Two coprime clocks — a 4-clock and a 25-clock — together give every value $0$ to $99$ a unique reading, so their two answers rebuild the last two digits.

#5 Look for a Pattern 4.OA.C.5 Step 3

Strip the fives block by block, mod 25

Work with $A = 90!/5^{21}$, that is $90!$ with every factor of $5$ divided out (later we also divide out the $2$s).
First handle the numbers in $1$ through $90$ that are not multiples of $5$.
Here is the pattern: in any full run of $25$ consecutive integers, the ones coprime to $5$ multiply to $-1 \pmod{25}$ (a Wilson-type fact).
The runs $1$–$25$, $26$–$50$, $51$–$75$ each contribute $-1$, and the leftover $76$–$90$ also contributes $-1$.
So all the non-multiples of $5$ together give $(-1)^4 \equiv 1 \pmod{25}$.

$$(1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)(11\cdot 12\cdot 13\cdot 14) \equiv (-1)(-1)(-1) \equiv -1;\quad (-1)^4 \equiv 1 \pmod{25}$$

💡 Each clean block of $25$ leaves the identical footprint $-1$ mod $25$, so you only have to count how many blocks there are.

#7 Identify Subproblems 4.OA.B.4 Step 4

Peel the fives off the multiples of 5

The multiples of $5$ from $5$ to $90$ are $5\cdot 1, 5\cdot 2, \ldots, 5\cdot 18$.
Pull one $5$ from each: that uses $18$ fives and leaves $1\cdot 2\cdots 18 = 18!$.
But $18!$ still hides multiples of $5$ (namely $5,10,15$), so pull one more $5$ from each of those three ($3$ more fives, $21$ total), leaving $1\cdot 2\cdot 3$ from the original $25,50,75$.
Now reduce the survivors mod $25$: the numbers $1$–$18$ coprime to $5$ multiply to $4$, and $1\cdot 2\cdot 3 = 6$.
Combine with the $1$ from Step 3: $A \equiv 1\cdot 4\cdot 6 = 24 \equiv -1 \pmod{25}$.

$$\underbrace{1\cdot 2\cdots 18 \text{ (drop mult. of 5)}}_{\equiv\, 4} \;\cdot\; \underbrace{1\cdot 2\cdot 3}_{=\,6} \;\cdot\; \underbrace{1}_{\text{Step 3}} = 24 \equiv -1 \pmod{25}$$

💡 Peeling one $5$ off every multiple of $5$ turns the scary product into a small factorial you can finish by hand.

#5 Look for a Pattern 8.EE.A.1 Step 5

Divide out the 2s using cycling powers

We removed the $2$s along with the zeros, so $N = A/2^{21}$; mod $25$ that means multiplying $A$ by the inverse of $2^{21}$.
Use the exponent rules on powers of $2$ mod $25$: $2^{10} = 1024 \equiv -1$, so $2^{20} \equiv 1$ and $2^{21} \equiv 2 \pmod{25}$.
The inverse of $2$ mod $25$ is $13$, because $2\cdot 13 = 26 \equiv 1$.
Therefore $N \equiv A\cdot 13 \equiv (-1)\cdot 13 \equiv -13 \equiv 12 \pmod{25}$.

$$2^{10} \equiv -1,\ 2^{21} \equiv 2,\ 2^{-1} \equiv 13 \pmod{25};\quad N \equiv (-1)\cdot 13 \equiv 12 \pmod{25}$$

💡 Powers of $2$ loop every $20$ steps mod $25$, so a giant exponent collapses to a tiny one you can read off.

#7 Identify Subproblems 6.NS.B.4 Step 6

Glue the two clocks together

We now need the value $N$ below $100$ with $N \equiv 0 \pmod 4$ (Step 2) and $N \equiv 12 \pmod{25}$ (Step 5).
Test $12$ itself: $12 = 3\cdot 4$ so $12 \equiv 0 \pmod 4$, and clearly $12 \equiv 12 \pmod{25}$.
Both conditions hold, and because $4$ and $25$ are coprime the answer mod $100$ is unique, so $N \equiv 12 \pmod{100}$.
The last two nonzero digits of $90!$ are $12$, giving $n = 12$, which is choice (A).

$$N \equiv 0 \pmod 4,\ N \equiv 12 \pmod{25} \ \Rightarrow\ N \equiv 12 \pmod{100};\quad n = 12 \ \textbf{(A)}$$

💡 Among $0$–$99$, only $12$ reads $0$ on the 4-clock and $12$ on the 25-clock at the same time.

[1] #9 5.NBT.A.2 A zero appears at the end of a number for every factor of $10 = 2\times 5$ insid

[2] #7 6.NS.B.4 Since $100 = 4\times 25$ and $4$ and $25$ share no common factor, knowing $N \bm

[3] #5 4.OA.C.5 Work with $A = 90!/5^{21}$, that is $90!$ with every factor of $5$ divided out (

[4] #7 4.OA.B.4 The multiples of $5$ from $5$ to $90$ are $5\cdot 1, 5\cdot 2, \ldots, 5\cdot 18

[5] #5 8.EE.A.1 We removed the $2$s along with the zeros, so $N = A/2^{21}$; mod $25$ that means

[6] #7 6.NS.B.4 We now need the value $N$ below $100$ with $N \equiv 0 \pmod 4$ (Step 2) and $N

Review

Reasonableness: The two checks are independent, so passing both is strong evidence. Mod $4$: $12$ is a multiple of $4$, matching $N \equiv 0$. Mod $25$: retracing, $A \equiv -1$ and dividing by $2^{21}\equiv 2$ gives $-1\cdot 13 = -13 \equiv 12$. Every answer choice ($12,32,48,52,68$) is a multiple of $4$, which fits our mod $4$ result — so the mod $25$ step is what actually selects the answer, and only $12$ satisfies $\equiv 12 \pmod{25}$ among them ($32\equiv 7$, $48\equiv 23$, $52\equiv 2$, $68\equiv 18$). That single match confirms (A).

Alternative: Instead of the block-Wilson shortcut, one can grind $A \bmod 25$ directly with Euler's theorem. Strip the $5$s to get $A = 90!/5^{21}$; the factors coprime to $25$ satisfy $x^{20} \equiv 1 \pmod{25}$, so grouping the product into full residue systems and leftover terms yields the same $A \equiv -1$. Dividing by $2^{21} \equiv 2$ and combining with $N \equiv 0 \pmod 4$ through the Chinese Remainder Theorem again gives $12$.

CCSS standards used (min grade 8)

5.NBT.A.2 Explain patterns in number of zeros and placement of decimal point (Recognizing each trailing zero comes from a $2\times 5$ pair, so counting factors of $5$ counts the zeros to strip off.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Splitting mod $100$ into coprime mod $4$ and mod $25$ pieces and recombining them uniquely.)
4.OA.C.5 Generate a number or shape pattern following a given rule (Spotting that each full block of $25$ numbers coprime to $5$ multiplies to $-1$ mod $25$.)
4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Factoring one $5$ out of every multiple of $5$ to reduce the big product to a small factorial.)
8.EE.A.1 Know and apply the properties of integer exponents (Reducing $2^{21}$ mod $25$ using the short cycle of powers of $2$ and dividing it out.)

⭐ To find the last nonzero digits of a huge factorial, strip the zeros, then track the number on a 4-clock and a 25-clock and glue the two readings back together.

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: A

Count and strip the trailing zeros

Split the target into a 4-clock and a 25-clock

Strip the fives block by block, mod 25

Peel the fives off the multiples of 5

Divide out the 2s using cycling powers

Glue the two clocks together

Review

CCSS standards used (min grade 8)

More like this