0
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Welcome to math.SE! Please consider taking the time to read the faq to familiarise yourself with some of our common practices. In addition, this page should give you a start at learning how to typeset mathematics here so that your posts say what you want them to, and also look good. As this question appears to be homework, please consider reading this page for information about asking effective homework-related questions. Cheers! $\endgroup$
    – Alice Ryhl
    Mar 15, 2015 at 16:05
  • 2
    $\begingroup$ 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} $$ $\endgroup$ Mar 15, 2015 at 16:14

3 Answers 3

6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 17, 2015 at 4:53
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .