-- Apr 10 In-Class Exercise
since g(a, n) = gcd (14, 21) = 7, 1) when b =3 , d|b == false, therefore no solution for 14x = 3 mod 21;
2) when b = 7, d|b == true, therefore there are d= 7 solutions;
3) Extended Euclidian (a, n) = EE ( 14, 21) --> EE( 21, 14) --> EE( 14, 7) --> EE( 7,0) returns (7, 1,0) --> returns ( 7, 0, 1) --> returns (7, 1, -1) --> returns ( 7, -1,1 ) where d = 7 + 14 * (-1) + 21 * 1
x0 = (x' * (b/d)) mod n = ((-1) * (7/7) ) mod 21 = 20;
for i = 0,1,2...6
calculate x_i = ( x0 + i * (n/d)) mod n, that is 20, 23, 26, 29, 32, 35, 38 all mod 21
so final answers are 20, 2, 5, 8, 11, 14, 17.
(
Edited: 2019-05-15)
since g(a, n) = gcd (14, 21) = 7, 1) when b =3 , d|b == false, therefore no solution for 14x = 3 mod 21;
2) when b = 7, d|b == true, therefore there are d= 7 solutions;
3) Extended Euclidian (a, n) = EE ( 14, 21) --> EE( 21, 14) --> EE( 14, 7) --> EE( 7,0) returns (7, 1,0) --> returns ( 7, 0, 1) --> returns (7, 1, -1) --> returns ( 7, -1,1 ) where d = 7 + 14 * (-1) + 21 * 1 <br>
x0 = (x' * (b/d)) mod n = ((-1) * (7/7) ) mod 21 = 20; <br>
for i = 0,1,2...6
calculate x_i = ( x0 + i * (n/d)) mod n, that is 20, 23, 26, 29, 32, 35, 38 all mod 21 <br>
so final answers are 20, 2, 5, 8, 11, 14, 17.