Number Theory Chinese Remainder Theorem and Modular Inverse

Number Theory: Chinese Remainder Theorem and Modular Inverse

*******Make sure hand writing is done in black ink. Do not take picture that is far away or leaves out segments of the paper. Make sure the solution is done in a step by step process. Don\'t leave out small details. Explain the solution thorougly and in concise manner.

1) Determine the modular inverse of 149 modulo 666 with the help of the Chinese Remainder Theorem.

Solution

To find modular inverse of 149 mod 666 we can use Euclid’s Algorithm. So first we divide 666 by 149 to get

666=149*4+70 … (1)

149=70*2+9 … (2)

70=9*7+7 … (3)

9=7*1+2… (4)

7=2*3+1 … (5)

Calculating back

1=7-2*3 use … (5)

=7-(9-7*1)*3 use … (4)

=7-9*3+7*1*3

=7*4-9*3

=(70-9*7)*4-9*3 use … (3)

=70*4-9*31

=70*4-(149-70*2)*31 use … (2)

=70*(4+62)-(149)*31

=70*66-(149)*31

=(666-149*4)*66-(149)*31 use … (1)

=666*66-149*(4*66+31)

=666*66-149*295

Thus 1=666*66-149*295

That is modular inverse of 149 mod 666 is 295.