I am trying to find the remainder when $4^{96}$ is divided by 6.
SO using the cyclicity method,
Dividing $4^1$ by 6 gives remainder 4.
Dividing $4^2$ by 6 gives remainder 4.
Dividing $4^3$ by 6 gives remainder 4.
Dividing $4^4$ by 6 gives remainder 4.
Dividing $4^5$ by 6 gives remainder 4.
..
..
So by this method we get the answer as 4.
But when we reduces this to
$$ 4^{100} /6 $$ to
$$ 2^{200} /6 $$
which is equal to
$$ 2^{199} /3 $$
Then by using the cyclicity method:
Dividing $2^1$ by 3 gives remainder 2.
Dividing $2^2$ by 3 gives remainder 1.
Dividing $2^3$ by 3 gives remainder 2.
Dividing $2^4$ by 3 gives remainder 1.
Dividing $2^5$ by 3 gives remainder 2.
..
..
So accrding to this ,We get the answer as 2.
So which one is correct?
And how we are getting two different answers for the same numbers?
Thanks in advance.
Best Answer
The first method is correct. Since $4\times 4 \equiv 4 \mod 6$, you can conclude $4^n \equiv 4 \mod 6$ for $n \ge 1$.
The second method is wrong. A simple example is that it suggests the remainder when $8$ is divided by $6$ is the same as the remainder when $4$ is divided by $3$.
If you know that $$2^{2n-1} \equiv 2 \mod 3$$ and $$2^{2n} \equiv 1 \mod 3,$$ then modulo $6$ you can conclude $$2^{2n-1} \equiv 2 \text{ or } 5 \mod 6$$ and $$2^{2n} \equiv 1 \text{ or } 4 \mod 6.$$ You want the latter expression. You can similarly say that since $2^m \equiv 0 \mod 2$ you can conclude $$2^m \equiv 0 \text{ or } 2 \text{ or } 4 \mod 6.$$ Put those two together and you get $$2^{2n} \equiv 4 \mod 6$$ which is the first result.