find the remainder of 14^85 mod 49?

i know that this is 14^85 congruent to a mod 49, where we want to find a.

since (14,49) =7, it means that a is divisible by 7. then what happens next?

Printable View

- Apr 17th 2012, 04:11 PMalexandrabel90remainder modulo
find the remainder of 14^85 mod 49?

i know that this is 14^85 congruent to a mod 49, where we want to find a.

since (14,49) =7, it means that a is divisible by 7. then what happens next? - Apr 17th 2012, 06:08 PMDevenoRe: remainder modulo
note that 14 = 2*7 and 14

^{85}= (2^{85})(7^{85}) = (2^{85})(7)(7^{84}) = (2^{85})(7)(7^{2})^{42}

= (2^{85})(7)(49)^{42}.

it stands to reason therefore that 49 divides 14^{85}, which is therefore 0 (mod 49).