Question

Find the last two digits of 49^19 by using chinese remainder theorem.

Answer 1

Given:

49^19

To find:

The last two digits.

Solution:

By using Chinese remainder theorem,

x ≡ 49^19 mod 100

100 = 25 * 4

x ≡ 49^19 mod 25

x ≡ 49^19 mod 4

( 49 )^19 = ( -1 )^19 mod 25

-1 mod 25

( 49 )^19 = ( 1 )^19 mod 4

1 mod 4

x ≡ ( ( -1 ) ( 4 ) ( 19 ) ) + ( ( 1 ) ( 25 ) ( 1 ) )

x ≡ -51 mod 100

x ≡ 49 mod 100

Hence, the last two digits of 49^19 is 49.