Re: How do I do this problem without a calculator?

On 15 Mar 2006 23:29:46 -0800, "Foster Bell" <bell3774@xxxxxxxxx>
wrote:


One approach, not discussed by other notes in this thread so
far, would be to consider the computation modulo 2 and again
modulo 11. You can then piece together the answer modulo
22 from the separate answers for 2 and 11.

This approach is very enticing, but I don't know how to "piece
together" the results.

6^19 mod 2 is 0
6^19 mod 11 is 2

Now I know that the answer is 6^19 mod 22 is 2, but I know that from
doing the problem, not from the facts above. Is there a generic rule to
use?

Yes, you can use the Chinese Remainder Theorem.

However the numbers here are so small, I would just do it by
inspection.

Let 6^19 = x mod 22 where 0 <= x <= 21

6^19 = x mod 22 ==> 6^19 = x mod 2 => x = 0 mod 2

6^19 = x mod 22 ==> 6^19 = x mod 11 => x = 2 mod 11

In the range 0 to 21 inclusive, only two numbers satisfy x = 2 mod 11,
namely x = 2 and x = 13, but only x = 2 also satisfies x = 0 mod 2.

Therefore x = 2.

quasi
.

Relevant Pages