Double Problem

Number Theory Level 4

Let $R$ be the remainder when $97!$ is divided by 101.

$M = 2^R + 2^{R-1} + 2^{R-2} + ........ + 2^1 + 2^0$

Find the last three digits of M.

2 solutions

Fahim Shahriar Shakkhor
Dec 25, 2013

From Wilson's Theorem, we get

$100! \equiv -1 \pmod {101}$

$\Rightarrow 100! \equiv 100 \pmod {101}$

$\Rightarrow 99! \equiv 1 \pmod {101}$

$\Rightarrow 99! \equiv 101 \times 49 + 1 \pmod {101}$

$\Rightarrow 98! \equiv 50 \pmod {101}$

$\Rightarrow 98! \equiv 101 \times 16 + 50 \pmod {101}$

$\Rightarrow 97! \equiv 17 \pmod {101}$

So, $R=17$ .

We know, $2^0 + 2^1 + 2^2 + .........+ 2^{n-1} = 2^n -1$

Hence, $M = 2^0 + 2^1 + 2^2 + .........+ 2^{17} = 2^{18}-1 = 262143$

So, the last three digits of $M$ are $\boxed{143}$ .

How do you get 98 ! =50 ( mod 101 ) from the previous step

Sriram Venkatesan - 3 years, 6 months ago

Piyushkumar Palan
Dec 29, 2013

As 101 is prime, by Wilson's theorem, $99! \equiv 1 \pmod{101}$

$97! \cdot 98 \cdot 99 \equiv 1 \pmod{101}$

$97! \cdot (-3) \cdot (-2) \equiv 1 \pmod{101}$

$97! \cdot 6 \equiv 1 \pmod{101}$

$97! \equiv 6^{-1} \pmod{101}$

$97! \equiv 17 \pmod{101}$ ....... because $6 \cdot 17 = 102 \equiv 1 \pmod{101}$

So $R = 17$

So $M = 2^{17} + 2^{16} + ... +2^1 + 2^0 = 2^{18} - 1 = (2^9)^2 - 1 = 512^2 - 1 = 262143$

So answer is $\boxed{143}$