Problem
NT-B1-M04-P013 Criterion for a Linear Congruence
#13
★★★☆☆ Level 3 of 5
Prove that \(ax\equiv b\pmod m\) has a solution if and only if \(\gcd(a,m)\mid b\).
Rewrite the congruence as \(ax-b=my\).
The congruence is equivalent to the integer equation \(ax-my=b\). All numbers of the form \(ax-my\) are divisible by \(d=\gcd(a,m)\), so \(d\mid b\) is necessary. Conversely, if \(d\mid b\), Bezout's identity gives \(u,v\) with \(au+mv=d\). Multiplying by \(\frac bd\), we represent \(b\) as \(aX+mY\), giving a solution to the congruence.
This is the theoretical centre of the module.