# The largest number that will perfectly divide $101^{100}–1$ [closed]

The largest number amongst the following that will perfectly divide $101^{100}–1$ is:

A. $100$

B. $10,000$

C. $100^{100}$

D. $100,000$

• Hint: $$101^{100}-1 = (1+100)^{100} - 1 = \underbrace{\binom{100}{1}100}_{\verb/divisible by / 10^4} + \binom{100}{2}100^2 + \cdots + 100^{100}$$ Mar 15, 2015 at 16:14

HINT Use binomial expansion: $$(1+100)^{100}-1={100\choose1}100+{100\choose2 }{100}^2+\cdots+{100\choose100}100^{100}$$ So the largest among A, B, C and D that divides it is...

Hint: $x^n-1=(x-1)\underbrace{(x^{n-1}+x^{n-2}+\dots+1)}_{100\text{ terms}}$

Note that $101^k\equiv100k+1\pmod{1000}$.

Details from a Deleted Comment

I should have moved the content from the comment to the question since comments are ephemeral.

We can show by induction that $101^k\equiv100k+1\pmod{1000}$. The initial case ($k=0$) and inductive step are simple: \begin{align} 101^{k+1} &=101^k\cdot101\\ &\equiv(100k+1)\cdot(100+1)\pmod{1000}\\ &\equiv100(k+1)+1\pmod{1000} \end{align} Then, set $x=101$ and $n=100$. $x-1=100$ adds one factor of $100$, while \begin{align} 101^{99}+101^{98}+\dots+1 &\equiv(99\cdot100+1)+(98\cdot100+1)+\dots+(0\cdot100+1)\\ &\equiv4950\cdot100+100\\ &\equiv100\pmod{1000} \end{align} adds exactly one more.

• Readers may wonder how the above is related to the proof in zed111's answer, which computes a couple leading terms of the Binomial Theorem (BT) expansion of $(x\!+\!1)^{100}-1,\ x=100$. The above essentially computes the same leading terms, but in a different way. First it factors it to $x((x\!+\!1)^{99}+(x\!+\!1)^{98}\!+\cdots+1)$ then it computes the first two terms of the binomial expansion of all $100$ summands $(x\!+\!1)^k,$ then it computes their sum. Mar 17, 2015 at 4:53

Using a little "brute force" and calculating $\bmod 100000$, \begin{align} 101^{1} &\equiv 101\\ 101^{2} &\equiv 10201\\ 101^{4} &\equiv 60401\\ 101^{8} &\equiv 80801\\ 101^{16} &\equiv 1601\\ 101^{32} &\equiv 63201\\ 101^{64} &\equiv 66401\\ 101^{96} &\equiv 9601\\ 101^{100} &\equiv 10001\\ \end{align}

therefore

• $100 \mid 101^{100}-1$
• $10000 \mid 101^{100}-1$
• $100000 \nmid 101^{100}-1$
• $100^{100} \nmid 101^{100}-1$