Solve the congruence equation 22x 13 mod 3045Solution22x 13

Solve the congruence equation 22x = 13 mod 3045.

Solution

22x= 13 mod 3045

=> 22x-3045t=13

Step1 :

3045= 22 * 138 + 9
22= 9* 2 +4
9=4*2 +1
4= 1* 4 + 0

gcd(22,3045)=1

Step 2: We check to see if 1 | 13
13 = 13/ 1
Based on this, there will be 1 solutions mod 3045.
Our Greatest Common factor sets up a Diophantine equation below 22x - 3045y = 13.

Running the Extended Euclidean Algorithm for 22 and 3045, we get x = 5 and y = -692.