Question

What is the complete solution of 4x= 5 (mod 21)? (the "=" means congruent to) @MIT 18.01 Single …

Answer 1

since the gcd of 4 and 21 is 1, the inverse of 4 (mod 21) exists. so we need to find it.

21*3=63
4*16=64

so the inverse of 4 mod 21 is 16.

Answer 2

so now we multiply both sides of the equation by 16. this gives:\[4x\equiv 5\mod 21\iff 16\cdot4x\equiv 16\cdot 5\mod 21\]\[64x\equiv 80\mod 21\]
but 64 is congruent to 1, and 80 is congruent to 17, so we have:\[x\equiv 17\mod 21\]

Answer 3

So, x=17 (mod 21) is the complete solution?

Answer 4

yes. because the gcd of 4 and 21 is 1, there is a solution, and its unique. When looking at problems of the form:\[ax\equiv b \mod m\]
you always want to check the gcd of a and m before doing anything else.

Answer 5

ok, thanks!