Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.2 : Linear Congruences Revisted

( \newcommand{\kernel}{\mathrm{null}\,}\)

The following theorem we stated in Chapter 4:

Theorem 5.2.1

Let  mZ+ and  a,bZ, with a be non-zero. Then

axb(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 {xZ|xx0(modm)}={x0,x0+md,x0+2md,,x0+(d1)md}, where d=gcd(a,m).

Let us learn how to use the theorem to solve linear congruence. Let mZ+ and  a,bZ, with a be non-zero. Consider the  linear congruence axb(modm). Which is equivalent to maxbaxb=my, for someyZ. Thus solving linear congruence is equivalent to solving the linear Diophantine equation ax+my=b, for x,yZ.

Example 5.2.1

If possible,  solve 2x2(mod4).

Solution

Since gcd(2,4)=2 and 222x2(mod4)  has a solution. Moreover, the set of all solutions is given by {xZ|xx0(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=14k,kZ.

Thus x(mod4)=1,1.

Since (1)(mod4)3 and 1(mod4)1, the set of all solutions are all integers  x such that x3(mod4) or x1(mod4).

 


This page titled 5.2 : Linear Congruences Revisted is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

Support Center

How can we help?