Question

Use Fermat's Little Theorem to compute the following remainders for 44824482 (Always use canonical representatives.)

4^482= ? mod 5
4^482 = ? mod 7
4^482= ? mod 11

Use your answers above to find the canonical representative of 4482 mod 3854482 mod 385 by using the Chinese Remainder Theorem. [Note 385=5⋅7⋅11385=5⋅7⋅11 and that Fermat's Little Theorem cannot be used to directly find 4482 mod 3854482 mod 385 as 385 is not a prime and also since it is larger than the exponent.]
4^482 mod 385 is

Answer 1

Fermat's Little Theorem can be stated a few ways;

the relevant way to this question is: Given a prime p and an integer a such that

gcd(a, p) = 1, then a^(p - 1) is congruent to 1 (mod p).

a) 4^482= ------ mod5 , here a=4 , p=5

gcd(4,5)=1 then

4^241=(4^480)*4^2

=(4^4)^120 * 4^2

= 1^120*16

=16 (mod5)

b)4^482=------ (mod7) , here a=4 ,p=7

gcd(4,7)=1

4^482= (4^480)*4^2

=(4^6)^80*16

=1^80*16

=16

=16(mod7)

c)4^482 = ------ (mod11)

here a=4, p=11

gcd(4,11)=1

4^482=(4^472)*4^10

=(4^470)*4^2

=(4^10)^47*16

=1*16

=16 (mod11)