# What is the remainder when $4^{100}$ is divided by 6?

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?

-
The first answer is right. The last step of your second argument is incorrect. You could (correctly) argue that $4^{100} \equiv 1$ (mod 3) and $4^{100} \equiv 0$ (mod 2), so that $4^{100} \equiv 4$ (mod 6) – Geoff Robinson Sep 22 '12 at 8:34
Geoff : I am not able to get you. I have added a proof of 2nd argument .Can you tell me where i am wrong? – vikiiii Sep 22 '12 at 8:37
The error comes in assuming that $2^{200}$ (mod 6) is the same as $2^{199}$ (mod 3). It is true that $2^{200}$ divided by $6$ is the same as $2^{199}$ divide by $3,$ but you are talking about remainders in the question. – Geoff Robinson Sep 22 '12 at 8:41
and 4/6 = 2/3, but 4 (mod 6) is not equal to 2 (mod 3). – Deedlit Sep 22 '12 at 8:49
@GeoffRobinson: You surely meant $\frac{2^{199}-2}{3}$. – celtschk Sep 22 '12 at 9:05

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.

-