Question

Why 100 is used as modulo in finding last two digits of 49^19 using chinese remainder theorem?

Answer 1

Answer:

There is only one number that satisfies the congruences by the Chinese Remainder Theorem.The number is modulo 100

Step-by-step explanation:

The Chinese remainder theorem provides with a unique solution to simultaneous linear congruences with the coprime modulo. The modulo generally being 100.

49^19 (Given)

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.