The Power of All Digits

Number Theory Level 3

$2^{123456789} - 1$

What is the remainder when the above number is divided by 19?

The answer is 17.

1 solution

Worranat Pakornrat
Feb 9, 2017

Since $19|513 = 2^9 + 1$ , and $9|123456789$ , then $2^{123456789} + 1 = 2^{9n} + 1 = (2^9 + 1)m$ for some integers $n$ and $m$ .

Thus, $19| 2^{123456789} + 1$ , and the remainder when dividing $2^{123456789}-1$ by $19$ equals $19-2 = \boxed{17}$ .

That's a great observation!

(Though it seems somewhat amazing.)

Calvin Lin Staff - 4 years, 4 months ago

Thanks. It is amazing. :)

Worranat Pakornrat - 4 years, 4 months ago

Actually, it's not too surprising.

Do you know how to explain this observation?

Hint: euler's theorem .

Calvin Lin Staff - 4 years, 4 months ago

@Calvin Lin – $\phi(19) = 18$ , so $2^{18} \equiv 1 \pmod {19}$ . $123456789 = 9(2n+1)$ for some integer $n$ , so $2^{123456789} \equiv 2^9 \equiv -1 \pmod {19}$ .

Thus, $2^{123456789} - 1 \equiv -2 \equiv 17 \pmod {19}$ .

I think. ;)

Worranat Pakornrat - 4 years, 4 months ago

@Worranat Pakornrat – Great! Because we know that $2^{18} - 1 \equiv 0 \pmod{19}$ , we could work directly with that to get the answer.

To explain what you did here, notice that $( 2 ^ { 9 } -1 ) ( 2^9 + 1 ) = 2 ^ { 18 } -1 \equiv 0 \pmod{19}$ , hence one of these terms must be $\equiv 0 \pmod{19}$ . IE We didn't need to magically pull that divisibility observation out of thin air, but have the motivation for why it's true (and in particular, why we didn't look at say $2^8 -1$ ).

Calvin Lin Staff - 4 years, 4 months ago

The Power of All Digits

The answer is 17.

1 solution

0 pending reports