Linear Congruencies

The mot general linear equation is of the form ax + c = 0. This can also be written in the form ax = b.

The most general linear congruency is usually written in the form ax º b ( mod m ). When we attempt to solve an equation, we look for numbers that satisfy a given equation. When we attempt to solve a congruency we look for congruence classes ( or residue classes ) that satisfy the given congruency. If the last sentence is a bit confusing, it will clear up in a while. In order to do that, let's first forget about finding congruence classes that satisfy a given congruency, and just look for plain old numbers that satisfy a given congruency.

Example 1: Find by inspection, four numbers x that satisfy the congruency 2x º 1 ( mod 3 ).

Trying 0, 1 and 2 we find x = 2 works because 2x = 4 º 1 ( mod 3 ).

We also notice that 3 and 4 does not work but 5 works because 2x = 10 º 1 ( mod 3 ).

We notice x = 8 and 11 works as well so we have x = 2, 5, 8, 11 as the solutions.

We also notice there are infinitely many such solutions and they don't have to be

necessarily positive either. For example x = -1, -4 are solutions, and there is an infinite sequence of numbers like this that satisfy this congruency.

Exercise 1: Find by inspection, three negative numbers x such that 7x º 1 ( mod 5 ).

In Example 1, the four solutions were 2, 5, 8 and 11. Is there a relation among these numbers?

Of course there is. These numbers are congruent to each other modulo 3. That is,

11 º 8 º 5 º 2 ( mod 3 ).

Therefore, we can write the solution as a congruency, that is,

x º 2 ( mod 3 ).

This is what we meant when we said we look for congruence classes ( or residue classes ) that satisfy a given congruency. That is, x º 2 ( mod 3 ) is a congruence class that satisfies the congruency 2x º 1 ( mod 3 ). Every integer in this class ( or the residue class ) satisfies the given congruency. This also suggests that we can greatly simplify the task of looking for integers that satisfy a given congruency. All we have to do is check the integers in the least positive residue system of the given modulus to see if any of them satisfies the congruency. We don't need to check any more integers since every one of them will belong to one of the congruent classes we already checked into.

Thus when we look for solutions of a congruency, in modulus 7 for example, we check the numbers 0, 1, 2, 3, 4, 5, 6 to see if they work. Any that work will then lead to an entire congruence or residue class ( consisting of an infinite number of integers ) that satisfy the given congruency. For example if 2 and 5 do work, then we write x º 2 ( mod 7) and x º 5 ( mod 7 ) as solutions.

The last sentence in the last paragraph may have surprised you. Are there Linear Congruencies with more than one residue classes as solutions? Moreover, are there linear congruencies with no solutions?

The next couple of examples will answer this question.

Example 2: Solve, by inspection 2x º 1 ( mod 4 ).

You will see none of the integers in the residue system modulo 4 satisfies the above condition.

Therefore the above congruence has no solution!

Example 3: Solve, by inspection 21x º 6 ( mod 9 ).

You are probably tempted to divide both sides by 3. Why is this not allowed?

You will eventually see, of the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8 only 2, 5, 8 satisfy this congruency. Thus we have three solutions

x º 2 ( mod 9 ), x º 5 ( mod 9 ), and x º 8 ( mod 9 ).

Note that when a congruence has one residue class as its solution its customary to say it has one solution (even though there are infinite many integers that satisfy this congruence). When a congruency has 3 residue classes as its solution ( such as the one in Example 3) we say it has three solutions. In Example 3, also note that the three residues that are solutions are incongruent to each other ( naturally! ). That is, 2 not º 5 ( mod 9 ) and so on. For this reason, the three solutions are sometimes referred to as the three incongruent solutions to the given congruency.

Now let's change one of the numbers in the congruency slightly in Example 3 and try to solve it.

Example 4: Solve, by inspection 21x º 5 ( mod 9 ).

You will see no number from the residue system modulo 9 satisfies this congruency.

Hence this congruence has no solution.

Exercise 2: Solve each of the following.

2x º 1 ( mod 19 ) 3x º 1 ( mod 17 ) 3x º 6 ( mod 18 ) 40x º 777 ( mod 1777 )

By now, you are probably becoming very curious about when does a linear congruency has solutions and how many. The following theorem answers that question.

Theorem 1: ax º b ( mod m ) has solutions iff (a, m) | b. If it has solutions, then there are exactly (a, m) of them.

In Example 1, we had the congruency 2x º 1 ( mod 3 ), and it had one solution. Now, (2, 3) = 1, and 1 divides b =1.

In Example 2, we had 2x º 1 ( mod 4 ), and we had no solutions. Here (2, 4) = 2, and 2 does not divide 1.

In Example 3, we had 21x º 6 ( mod 9 ), and we had three solutions. This is because (21, 9) = 3, and 3 divides 6.

In Example 4, we had 21x º 5 ( mod 9 ), and we had no solutions. This is because (21, 9) = 3, and 3 does not divide 5.

The proof of theorem obviously has few separate parts. First there is the part about when the congruence has solution. This in itself branches into two parts because there is an iff. Then there is the part dealing with the number of solutions. You should be familiar with at least the first part. However, first let's get some practice applying the theorem. Later we will learn some parts of the proof through some worked examples and exercises.

Exercise 3: First, state how many solutions are there for each of the following congruencies, and then find them.

(a) 2x º 5 ( mod 7 ) (b) 3x º 2 ( mod 6) (c) 4x º 2 ( mod 6 ) (d) 2x º 1 ( mod 6).

If you divide both sides of the congruence in ( c ) , we get the congruence in ( d ). Does that mean the one in ( c ) implies the one in ( d ) ? Explain.

Exercise 4: Write a linear congruence that does not have any solution (a) with modulus 6, (b) with modulus 7.

Exercise 5: If possible, write a linear congruence that has exactly three solutions with (a) modulus 12, (b) modulus 11.

The last part of Exercise 2 should have you thinking about the things that you are allowed to do to a congruence. This will certainly help in the next example.

Example 5: Solve 1000x º 750 ( mod 7 ).

First we notice that (1000, 7) = 1, and 1 divides 750. Hence we have one solution.

Next we observe that since ( 1000, 7) = 1, we can divide by 250 and get 4x º 3 ( mod 7 ).

This congruency is easy to solve by inspection, and we get x º 6 ( mod 7) as the solution.

( Now, put this value in the original congruency and verify that 6000 and 750 leave the same

remainder when divided by 7. )

Example 6: ( Part of the proof of Theorem 1) Prove that if ax º b ( mod m ) has a solution,

then (a, m) | b.

Suppose r is a solution. Then, ar º b ( mod m), and hence m | (ar - b). That is

ar - b = km, for some k. Or, ar - km = b. Now since (a, m) | a, and (a, m) | m, it follows that (a, m) | b.

Example 7: ( Another part ) Prove if (a, m) =1, then ax º b ( mod m ) has exactly one solution.

Since (a, m) = 1, $ r, s Î Z such that ar + sm = 1. Multiplying by b we have

arb + msb = b. That is, a(rb) - b = m(sb). This shows m | (a(rb) - b). Therefore,

a(rb) º b ( mod m ). Comparing this with the given congruence we see the least

residue of rb is a solution of that congruence. Thus we have proved that there is

one solution.

Proving there is only one solution is left as an exercise. Suggestion:- Assume there

are two solutions r and s. Then show r = s.

 

Exercise 6: Prove that if (a, m) | b, then ax º b ( mod m ) has a solution.

Suggestion:- Let (a, m) = c. Then write c as a linear combination of …….

Since (a, m) | b, we have c | b or, b = kc =……….

The rest is just like example 7.

The next one is probably one of the examples that truly illustrate the power of the congruency concept. Problems like these were found in abundance in many of the Indian and Chinese math books written more than a 1000 years ago! ( Some even 2000 years ago! )

Example 8: Find the smallest number that leaves a remainder of 1 when divided by 3, of 2 when divided by 5, and of 3 when divided by 7.

Translated to congruencies we have,

x º 1 ( mod 3 ) x º 2 ( mod 5 ) x º 3 ( mod 7).

The first congruence says that x = 1 + 3k, for some k. Substituting this into the second

Congruecy we get 1 + 3k º 2 ( mod 5 ). This means 3k º 1 ( mod 5 ).

We see, because (3, 5) =1, this congruency has a solution, and by inspection we arrive at

the solution k º 2 ( mod 5 ). This means k = 2 + 5n, for some n.

Thus x = 1 + 3k = 1 + 3( 2 + 5n ) = 7 + 15n. Substituting this the third congruency, we get

7 + 15n º 3 ( mod 7). That is, 15n º - 4 ( mod 7 ) or 15n º 3 ( mod 7 ).

Since (3, 7) = 1, we can divide by 3 to get 5n º 1 ( mod 7 ).

Now since (5, 7) = 1, this has a solution, and by inspection we arrive at n º 3 ( mod 7 ).

This tells us that n = 3 + 7m, for some m.

Thus x = 7 + 15( 3 + 7m ) = 52 + 105m. In other words x º 52 ( mod 105) satisfies all

three congruencies. And of course the smallest integer that satisfies the given conditions is 52.

We will end this discussion by noting that one of the Theorems that often catches our eyes in math books because of its "multi-cultural" nature, The Chinese Remainder Theorem, is basically nothing more than a statement that the above procedure will always work as long as the modulus' involved are pair-wise relatively prime.

Exercise 7: Solve the system:

x º 3 ( mod 5 ) x º 5 ( mod 7 ) x º 7 ( mod 11 ).