# 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$.