5
$\begingroup$

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?

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

4 Answers 4

7
$\begingroup$

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}$

$\endgroup$
6
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ The OP does not know anything about modular arithmetic. $\endgroup$
    – Crostul
    Aug 30, 2016 at 12:44
  • 2
    $\begingroup$ and the use of "Obviously" is rather off-putting in any answer. $\endgroup$
    – Jason S
    Aug 30, 2016 at 17:12
  • $\begingroup$ The first step comes out of nowhere. Why is the first expression divisible by 32 ? $\endgroup$ Aug 30, 2016 at 17:52
  • $\begingroup$ @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 $\endgroup$ Aug 31, 2016 at 12:09
5
$\begingroup$

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$)

$\endgroup$
4
  • 2
    $\begingroup$ The OP does not know anything about modular arithmetic. $\endgroup$
    – Crostul
    Aug 30, 2016 at 12:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – 5xum
    Aug 30, 2016 at 12:47
  • $\begingroup$ 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! $\endgroup$ Aug 30, 2016 at 13:22
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 30, 2016 at 14:04
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.