Question

(a) Solve 14x == 271 (mod 11111) (b) Solve x2 == 91 (mod 77) Note: "==" mean congruence.

Answer 1

congruence means lets take eaxmple to understand

has solution iff gcd(a,n) divide by b

so we will solve this according to this statement above

and here we will denote gcd(a,n) = d;

so 1st question

   // first we fill find gcd

gcd(14,11111) = 1     // so it has only 1 solution.

now we have to try for x value which is less than 11111

so we get 813 if we put 813 at x then

813 * 14 = 11382 // 11382 is divisble by 271

11382 / 271 = 42 .

hence x = 813 and this is the only one solution for this equation.

2nd question.

gcd(2,77) = 1         // so this equation has 1 solution

so answer will be 7.

x=7.