Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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. –  Geoff Robinson Sep 22 '12 at 8:41
1  
and 4/6 = 2/3, but 4 (mod 6) is not equal to 2 (mod 3). –  Deedlit Sep 22 '12 at 8:49
1  
@GeoffRobinson: You surely meant $\frac{2^{199}-2}{3}$. –  celtschk Sep 22 '12 at 9:05

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.