Cutting time

Number Theory Level 4

What is the highest power of 10 that divides $101^{100} - 1$ ?

The answer is 4.

2 solutions

Manuel Kahayon
Apr 4, 2016

Let $V_{n}(x)$ denote the largest power of $n$ which divides $x$ . By Lifting the Exponent Lemma,

$V_{10}(101^{100}-1^{100}) = V_{10}(101-1)+V_{10}(100) = 2+2 = 4$

So, our answer is $4$ .

Vishnu Bhagyanath
Mar 23, 2016

$(1+x)^n = \binom{n}{0} + \binom{n}{1} x + ... + \binom{n}{n} x^n$

Substituting $x =100,n=100$ , we get $101^{100} -1 = 1 + 100 \times 100 + \frac{100\times 99}{2}\times 100^2 +... + 100^{100} -1$

Note that the lowest power we can take common from the remaining terms is from the first term of $100^2$ . Hence, the highest power of $10$ that can divide $101^{100}-1$ is $100^2 \Rightarrow 10^4$ .

Verification that after factoring out $10^4$ , the remaining terms cannot sum up to another power of $10$ :

We get the remaining terms as $1 + \frac{100 \times 99}{2} + \frac{100 \times 99 \times 98}{6} \times 100 + ... + 100^{98}$ .

Note that $\binom{n}{r} \geq 1$ and the remaining terms are powers of $100$ times an arbitrary $\binom{n}{r}$ corresponding to the $r^{\text{th}}$ term. Thus if the resulting term were to be a power of $10$ , then $\frac{100 \times 99}{2} + \frac{100 \times 99 \times 98}{6} \times 100 + ... + 100^{98} \equiv 9 \pmod{10}$ , which is not true (since powers of each power of hundred ends in zero and the first term is $99 \times 50$ which also ends in zero)

Vishnu Bhagyanath - 5 years, 2 months ago

Cutting time

The answer is 4.

2 solutions

0 pending reports