Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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 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$)
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.
