3
$\begingroup$

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.

  • 0
    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)2012-09-22
  • 0
    Geoff : I am not able to get you. I have added a proof of 2nd argument .Can you tell me where i am wrong?2012-09-22
  • 3
    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.2012-09-22
  • 0
    $4 \pmod{6} = 4$ but $2 \pmod{3} = 2$. Clearly the two are not the same.2012-09-22
  • 0
    But $4^{100}/6 $ is equal to $2^{200}/6$ .2012-09-22
  • 1
    and 4/6 = 2/3, but 4 (mod 6) is not equal to 2 (mod 3).2012-09-22
  • 0
    But in integer division, $2^{200}/6$ is *not* the same as $2^{199}/3$. You can easily see this with lower exponentials: $2^4/6 = 16/6 = 2,\text{ remainder }4$ but $2^3/3 = 8/3 = 3,\text{ remainder }2$.2012-09-22
  • 1
    @GeoffRobinson: You surely meant $\frac{2^{199}-2}{3}$.2012-09-22
  • 0
    @celtschk: Yes, I did indeed. Thanks. Confusing error in this context. Should have read ``$\frac{2^{200} - 4}{6} = \frac{2(2^{198}-1)}{3}$, which is twice an integer. Hence $2^{200} \equiv 4$ (mod 6)."2012-09-22

1 Answers 1

3

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.