# What is remainder when $5^6 - 3^6$ is divided by $2^3$ (method)

I want to know the method through which I can determine the answers of questions like above mentioned one.

PS : The numbers are just for example. There may be the same question for BIG numbers.

Thnx.

• This is not a question about logic. Seems more like number theory. Commented Jul 22, 2014 at 5:56
• Tags have been edited. @Nagase Commented Jul 22, 2014 at 6:00
• There is no general method for finding the remainder of a very large number, because it depends what information you have about that number. The method will be very different depending on whether the number is described as "$9^{342}$", "the number of possible tic tac toe boards", or "435435435345330909". Commented Aug 10, 2014 at 9:33

One may notice that if $c |(a' - a)$ and $c | (b' - b)$ then $a \cdot b \mod c = a' \cdot b' \mod c$, same with + and - where $x \mod c$ is reminder (from 0 to $c-1$) (Why?)

So, $3^6 \mod 8 = (-5)^6 \mod 8 = 5^6 \mod 8$

We know that

$x^2-y^2 = (x-y)(x+y)$ and $x^3 + y^3 = (x + y)(x^2 - xy + y^2)$

So,

$5^6 - 3^6 = (5^3)^2 - (3^3)^2 = (5^3 + 3^3) (5^3 - 3^3)$

so, $5^6 - 3^6 = (5 + 3) (5^2 - 3\centerdot 5 - 3^2) (5^3 - 3^3)$

Now, as reminder of $(x\centerdot y$ mod $y )$ is $0$, dividing above term (with $(5+3)$ as one of the factors) with $2^3(=8)$ will give $0$ reminder.

HINT:

$$(2n+1)^2=4n^2+4n+1=8\frac{n(n+1)}2+1\equiv1\pmod{2^3}$$

Set $\displaystyle2n+1=5^3,3^3$ one by one

The following is the method: $$5^6-3^6=(2^3-3)^6-3^6 = 2^3 L+0$$ where $L$ is given by the binomial expansion.

Another method is to simply reduce mod $8$. We know that $5^2 = 25 \equiv 1 \bmod 8$ and $3^2 = 9 \equiv 1 \bmod 8$.

Thus:

$5^6 - 3^6 = (5^2)^3 - (3^2)^3 \equiv 1^3 - 1^3 \equiv 0 \bmod 8$.

So $8$ divides $5^6 - 3^6$ with no remainder.