What is the remainder when $4^{96}$ is divided by 6
My approach : When 4 is divided by 6 gives 4 remainder, when $4^2$ is divided by 6 gives remainder 4 ,... is it for the complete series.. that means when $4^{96}$ is divided by 6 gives 4 as remainder or is there any short cut or other answer of this question.
Please suggest if there is any sort of short cut to such problems.
Thanks.
$\endgroup$ 58 Answers
$\begingroup$By induction, we can prove $4^N\equiv4\pmod6$. The base case is $N=1$, which is trivial. Then suppose for $N=k\in\mathbb{N}$, the statement is true. Then for $N=k+1$, we have$$4^N=4^{k+1}=4^k \cdot4\equiv4\cdot4=16\equiv4\pmod6$$So, we have proved the induction case. So sub $N=96$ into above statement then we are finished with $4^{96}\equiv4\pmod6$.
$\endgroup$ $\begingroup$Your answer is in the right direction. Here is the argument I came up with. (I avoided using modular arithmetic.)
Let's prove that $4^n$ has a remainder of $4$ when divided by $6$. The base case for this argument is $4^1=4$ is obvious. Then assume $4^n$ has a remainder of $4$ when divided by $6$, this means $4^n = 4 + 6*m$ for some integer $m$. This means that $4^{n+1}=4*(4+6*m)=16+6*(4*m)$. Because $6*4*m$ is divisible by $6$ the remainder of $16+6*4*m$ when dividing by $6$ is equal to that of $16$, which is $4$. This proves that $4^{n+1}$ has a remainder of $4$ when divided by $6$. This concludes the proof.
The case for $n=96$ is a special case. That follows from the general case.
$\endgroup$ $\begingroup$$$4^{96}=(6-2)^{96} \equiv 2^{96} \pmod{6}$$
Now, if we find the remainder of $2^{95}=(3-1)^{95}$ by $3$,it is simply $(-1)^{95}=-1$ or $2\pmod{3}$ , so we have $$2^{95}=3k+2$$ Now multiply the above equation by $2$ on both sides to get $$2^{96}=6k+4$$
$\endgroup$ 3 $\begingroup$No need for induction. We have$$4^{N}=1^{N}=1\mod 3,$$for all $N\in\mathbb N$, as well as$$4^{N}=0\mod 2.$$From the former it follows that $4^N$ is either $1$ or $4\mod6$, and from the latter it follows that it's $0$, $2$, or $4\mod 6$. So it must be equal to $4\mod 6$.
$\endgroup$ $\begingroup$You could proceed this way: $6 = 2\cdot 3$. When you divide $4^{96}$ by $2$ the remainder is $0$. To divide by $3$, note that $4=3+1$ so that$4^{96} = (3+1)^{96}$ which expands to a multiple of $3$ plus $1$, so the remainder is one.
Now you need a number which is $1$ more than a multiple of $3$ and divisible by $2$ and less than $6$. That would be $4$.
$\endgroup$ $\begingroup$Just to give a different approach, note that ${n\choose k}$ is even for $1\le k\le n-1$ when $n$ is a power of $2$ (i.e., Pascal's triangle mod $2$ looks like Sierpinski's triangle). Consequently
$$4^{32}=(3+1)^{32}\equiv3^{32}+1\equiv3+1=4\mod 6$$
and thus $4^{96}\equiv4^3=64\equiv4$ mod $6$.
$\endgroup$ $\begingroup$As was mentioned, since Euler is not directly applicable, you can use CRT. Putting together that $4^{96}\equiv0\bmod2$ and $4^{96}\equiv 1\bmod3$, the latter by Fermat's little theorem, or the binomial theorem, we have using Bezout that $4^{96}\equiv -2\cdot1+0\cdot3=\equiv-2\equiv4\bmod6$.
As it turns out, CRT is not necessary here, as @BillDubuque points out.
$\endgroup$ $\begingroup$In all cases,
n-odd$\rightarrow 2^n\equiv 2 \mod6$
n-even$\rightarrow 2^n\equiv 4\mod6$
$\implies 2^{96}\equiv 4\mod 6$
$\endgroup$
