Prove $ax \equiv b \mod m \iff b \equiv 0 \mod gcd(m, a)$.

I have been stuck for quite some time, but here is my proof so far:

Let $gcd(m, a) = d$. Then $b = dk$.

$ax \equiv b \mod m \implies ax - qm = b$.

A solution exists if and only if $x \in \mathbb{Z}$. So solving for $x$, we find that $x = \frac{b+qm}{a}$. Because $d | m \land d | a$, it can be said that $x = d(\frac{k + qj}{i})$ where $m = dj$ and $a = di$.

I have a feeling that I can show that $x$ is an integer by doing something like this, but I'm not quite sure how.


I'm assuming you mean that there exists a solution to $ax \equiv b \mod m$ if and only if $b \equiv 0 \mod \gcd(m,a)$.

Let $d = \gcd(m,a)$.

Suppose $ax \equiv b \mod m$ for some integer $x$. Then there is an integer $k$ such that $ax-b=km \, \Longrightarrow \, b = ax -km$. Because $d$ divides both $a$ and $m$ it also divides $ax - km=b$ which is to say that $b \equiv 0 \mod d$.

Conversely, suppose $b \equiv 0 \mod d$. Then $b = rd$ for some integer $r$. Express $d = pm+qa$ as a integer combination of $m$ and $a$, which is possible by virtue of the euclidean algorithm. It follows that $b = rd = rpm + rqa \equiv (rq)a \mod m$. letting $x = rq$ we rewrite this as $ax \equiv b \mod m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.