5.2 : Linear Congruences Revisted
( \newcommand{\kernel}{\mathrm{null}\,}\)
The following theorem we stated in Chapter 4:
Let m∈Z+ and a,b∈Z, with a be non-zero. Then
ax≡b(modm) has a solution if and only if gcd(a,m)|b. Moreover, if x=x0 is a particular solution to this congruence, then the set of all solutions is {x∈Z|x≡x0(modm)}={x0,x0+md,x0+2md,…,x0+(d−1)md}, where d=gcd(a,m).
Let us learn how to use the theorem to solve linear congruence. Let m∈Z+ and a,b∈Z, with a be non-zero. Consider the linear congruence ax≡b(modm). Which is equivalent to m∣ax−b⟹ax−b=my, for somey∈Z. Thus solving linear congruence is equivalent to solving the linear Diophantine equation ax+my=b, for x,y∈Z.
If possible, solve 2x≡2(mod4).
Solution
Since gcd(2,4)=2 and 2∣2, 2x≡2(mod4) has a solution. Moreover, the set of all solutions is given by {x∈Z|x≡x0(mod4)} . To find a particular solution we consider the corresponding Diophantine equation 2x+4y=2. Since 2(−1)+4(1)=2, one particular solution is given by x0=−1. Then all the solutions to the Diophantine equation 2x+4y=2 are of the form x=−1+2k,y=1−4k,k∈Z.
Thus x(mod4)=−1,1.
Since (−1)(mod4)≡3 and 1(mod4)≡1, the set of all solutions are all integers x such that x≡3(mod4) or x≡1(mod4).