The largest number that will perfectly divide $101^{100}–1$

Question

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$

Can someone please answer this question. Thanks in advance.

Answer 1

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.

Answer 2

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...

Answer 3

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$

and the answer is B.