# What is the remainder when $16^{15}-8^{15}-4^{15}-2^{15}-1$ is divided by $96$?

I found this question from an old math questionnaire.

What is the remainder when $$16^{15}-8^{15}-4^{15}-2^{15}-1$$ is divided by 96?

I already know the answer. It is 31, says the answer at the back of the questionnaire. I just do not know why 31 is the answer. I do not know how the process of getting the remainder is done.

I tried a lot of crazy things and got answers like -135 and -63/32 which are obviously wrong, so I would not tell anymore what I did. Can anyone help me?

• Have you tried with modular arithmetics $\mod{96}$? Are you familiar with Chinese Remainder Theorem? Aug 30, 2016 at 12:15
• No, I did not. I am also not familiar with Chinese Remainder Theorem. Aug 30, 2016 at 12:37
• Very good. This means that all the answers below are more or less unuseful to you. Aug 30, 2016 at 12:43

Since you don't know modular arithmetic we can instead give a direct divisibility proof.

$$2^{60}\!-2^{45}\!-2^{30}\!-2^{15}\!-1\, =\, \underbrace{2^{30}(2^{30}\!-1)-2^{5}(2^{40}\!-1)-2^{5}(2^{10}\!-1)}_{\Large\color{#c00}{ 96}\, n}\!-2^5\!-2^5\!-1$$

$\color{#c00}{96} = 2^5\cdot 3\,$ divides all RHS summands of form $\,2^J (2^{2K}\!-1)$ since $\,J\ge 5\,$ so $\,2^5$ divides $2^J,\,$ and $\,3\,$ divides $\,2^{2K}\!-1\$ (put $\ a=2\$ in $\,a+1\,$ divides $\,a^2-1\,$ divides $\,(a^2)^K-1).$

So it has form $\,\color{#c00}{96}\,n - 2^5\!-2^5\!-1 = 96n-65 = 96(n\!-\!1)+96-65 = 96(n\!-\!1)+\color{#0a0}{31}$

Obviously,

$$A+1 = 16^{15}-8^{15}-4^{15}-2^{15} \vdots 32.$$ Therefore, reminder when $A$ is divided by $32$ is equal to $31$. Also, $$A\equiv 1^{15}-(-1)^{15}-1^{15}-(-1)^{15}-1 \equiv 1\pmod{3}.$$ Combining the above one gets $A\equiv 31\pmod{96}$.

• The OP does not know anything about modular arithmetic. Aug 30, 2016 at 12:44
• and the use of "Obviously" is rather off-putting in any answer. Aug 30, 2016 at 17:12
• The first step comes out of nowhere. Why is the first expression divisible by 32 ? Aug 30, 2016 at 17:52
• @HopefullyHelpful just because any power of $2$, bigger or equal to $5$-th, is divisible by $2^5=32$. Sorry if it was not clear Aug 31, 2016 at 12:09

The most useful thing here is to notice that $$2\cdot 64\equiv 32\mod 96$$

Using that, you can prove that $$32\cdot 2^{2k}\equiv 32\mod 96$$ and $$32\cdot 2^{2k+1}\equiv 64\mod 96$$

You can then use this to get:

$$2^{15}\equiv2^5\cdot 2^{10} \equiv 32\cdot 2^{2\cdot 5}\equiv 32\mod 96$$

Similarly:

$$4^{15} =2^{30} = 32\cdot 2^{25} \equiv 64\mod 96\\ 8^{15} =2^{45} = 32\cdot 2^{40} \equiv 32\mod 96\\ 16^{15} =2^{60} = 32\cdot 2^{55} \equiv 64\mod 96\\$$

so the answer is $31$ ($64-32-64-32-1=-65\equiv31\mod 96$)

• The OP does not know anything about modular arithmetic. Aug 30, 2016 at 12:44
• @Crostul Well, he says he doesn't know the chinese remainder theorem, not that he doesn't know modular arithmetic. I'll leave this answer up for now.
– 5xum
Aug 30, 2016 at 12:47
• Honestly, Crostul was right. I did not know anything about modular arithmetic about an hour ago. I just learned it by observing 5xum's solution. Thank you very much, 5xum! Aug 30, 2016 at 13:22
• @Carl You can do it reasonably simply even without such knowledge - see my answer. But it is better to learn congruences since it will greatly simplify more complex problems. Aug 30, 2016 at 14:04

If we can work out what remainder $2^{15}$ gives, then we can just successively square it to get $4^{15}, 8^{15}$ and so on.

Notice that $32 \times 3 = 96$, so $2^{15} = 2^5 \times 2^{10} = 2^5 \times (1023 + 1) = 2^5 \times 1023 + 2^5$; but $2^5 \times 1023$ yields no remainder.

Hence $2^{15}$ gives remainder $32$.

You can square it (continuing to use the $32 \times 3 = 96$ fact) to work out that $4^{15}$ yields remainder $64$, that $8^{15}$ yields remainder $32$, and so on.

• But how do you arrive at the answer 31? Aug 30, 2016 at 12:59
• @CarlTerenceValdellon My answer is probably better if you know about modular arithmetic; I didn't know at the time that you didn't. Aug 30, 2016 at 16:02