Recitation 23

In this recitation, I discussed linear congruence equations, i.e., equations of the form ax\equiv b \mod n. Let d=gcd(a,n).

If d\nmid b, then there is no solution.

Otherwise, d\mid b. Hence it is equivalent to solve a'x\equiv b' \mod n', where a'=a/d, b'=b/d, n'=n/d. Notice gcd(a', n')=1.

So it is enough to consider the case for gcd(a,n)=1. We could find the multiplicative inverse of a, say a^*, modulo n. Then x\equiv a^*b \mod n.

Leave a comment

Your email address will not be published. Required fields are marked *