# find remainder

• December 2nd 2007, 05:23 PM
frankdent1
find remainder
Find r when 319^566 is divided by 37.

I can get it down to (11^2)^283*(29^2)^283.
• December 2nd 2007, 07:02 PM
Soroban
Hello, frankdent1!

Are you allowed to use Modulo Arithmetic?

Quote:

Find the remainder when $319^{566}$ is divided by $37.$

We find that: . $319^6 \:\equiv \:-1 \pmod{37}$

Then: . $319^{566} \:=\:319^{6\cdot94 + 2} \:=\:
(319^6)^{94}\cdot319^2$

Hence: . $(319^6)^{94}\cdot319^2 \:\equiv \:(-1)^{94}\cdot319^2 \pmod{37}$

. . . . . . . . . . . . . . . $\equiv\:319^2 \pmod{37}$

. . . . . . . . . . . . . . . $\equiv\:101,761 \pmod{37}$

. . . . . . . . . . . . . . . $\equiv \:11 \pmod{37}$