Solutions of Linear Congruences

Theorem
Consider the linear congruence  
\[ax \equiv b \; (mod \; n)\]

a) The congruence has solutions if and only if  
\[gcd(a, n) | b\]

b) If  
\[gcd(a,n)-1\]
  the congruence has a unique solution.
c) If  
\[gcd(a,n)-d\]
  and  
\[d | b\]
  the congruence has  
\[d\]
  solutions which can be found from the unique solution  
\[mod \frac{n}{d}\]
  of the congruence  
\[ax \equiv b \; (mod \; \frac{n}{d})\]
.
Proof
a) The linear Diophantime  
\[ax-ny=b\]
  has solutions if and only if  
\[gcd(a,n) | b\]
. Hence the linear congruence has solutions if and only if  
\[gcd(a, n) | b\]

b) Suppose  
\[gcd(a,n)=1\]
  then if  
\[x_0, \; y_0\]
  are solutions of  
\[ax-ny=b\]
  then the general solution is  
\[x_0+nk, \; y_0+ak, \; k \in \mathbb{Z}\]
.
For all integers  
\[k \in \mathbb{Z}\]
   
\[x_0+nk \equiv x_0 \; (mod \; n)\]
  so  
\[x_0\]
  is the only solution of  
\[ax \equiv b \; (mod \; n)\]
.
c) If  
\[gcd(a,n)=d, \; d | b\]
  then  
\[ax \equiv b \; (mod \; n) \leftrightarrow \frac{a}{d} \equiv \frac{b}{d} \; (mod \; \frac{n}{d})\]
.
But  
\[gcd( \frac{a}{d}, \frac{n}{d})=1\]
  so the right hand congruence has a unique solution  
\[mod \; n\]
, say  
\[x_1\]
.
Hence the integers which satisfy  
\[ax \equiv b \; (mod \; n)\]
  are precisely those of the form  
\[x=x_1+ k \frac{n}{d}\]
  for some integer  
\[k\]
.
Consider the set  
\[\{ x_1, \; x_1 + \frac{n}{d}, \; x_1+2 \frac{n}{d},...,x_1+(d-1) \frac{n}{d} \}\]
. No two members of the set are congruent  
\[mod \; n\]
. Any integer  
\[x_1 + k \frac{n}{d}\]
  is congruent  
\[mod \; n\]
  to some member of  
\[S\]
  because if we write  
\[n=dq+r\]
  then  
\[x_1+k \frac{n}{d} = x_1 +k (dq+r) \frac{n}{d}=x_1+nq+r \frac{n}{d} \equiv x_1+ \frac{r}{d} \; (mod \; n)\]
.
Elements of  
\[S\]
  are then the solutions of  
\[ax \equiv b \; (mod \; n)\]
.
Example: Solve the linear congruence  
\[30x \equiv 15 \; (mod \; 33)\]
.
\[gcd(15, 33)=3\]
  and  
\[3 | 33\]
  so there are 3 distinct solutions  
\[mod \; 33\]
  b y the above theorem. Cancel 3 to give  
\[10x \equiv 5 \; (mod \; 11)\]
. Since  
\[gcd)10,11)=1\]
  so there is a unique solution  
\[mod \; 11\]
, The Cancellation Rule allows us to cancel 5 to obtain  
\[2x \equiv 1 \; (mod \; 11)\]
  which is equivalent to  
\[2x \equiv 11 \; (mod \; 11)\]
  and we get  
\[x \equiv 6 \; (mod \; 11)\]
. Other solutions are obtained by adding or subtracting multiples of  
\[\frac{33}{3}=11\]
. We obtain  
\[x \equiv 6, \; 17, \; 28 \; (mod \; 11)\]
.

Add comment

Security code
Refresh