Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A coding club sets two remainders as a warm-up. The first is the remainder when is divided by the prime . The second is the remainder when is divided by the prime . Use Fermat's little theorem to cut each exponent down, then finish by hand. Give both remainders, and say which exponent each is reduced to.
For a prime with , Fermat's little theorem gives , so exponents can be reduced modulo :
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. modulo and modulo ; both moduli are prime and divide neither base.
Step 1. Reduce the first exponent. . So .
Step 2. Reduce the second exponent. . So .
Step 3. Finish. , so , and .
Check. , so , as Fermat says. That also tells us had to be or .
Answer: the remainders are and ; the exponents reduce to and .
Log in to join the discussion.
Loading…