## 5.3  Linear Congruence Equations

In a previous chapter, you completely determined all solutions to the linear diophantine equation

ax + by = c.

Our goal in this section will be to do the same for the linear congruence equation

ax b (mod n).

Specifically, if a, b, and n are integers (with n positive), then we want to completely answer the following three questions for this congruence equation:

1. Are there any solutions?
2. If there are solutions, what are they?
3. If there are solutions, how many are there?

There are many approaches one might take to try to answer these questions, but it may be helpful to have a function for computing examples. Recall from your Prelab work that if a, b, and n are given, then the solutions can be determined by simply trying all possible congruence classes for x. The applet below does just that. For example, here are all of the solutions to 2x 5 (mod 11):

Your browser does not support java.

Here are all of the solutions to 6x 9 (mod 15):

Your browser does not support java.

And here are all of the solutions to 10x 35 (mod 42):

Your browser does not support java.

Try some other examples on your own. The following exercise gives you a chance to check the function congsolve against your solutions found on the Prelab assignment.

#### Exercise 1

Compute the answers to questions 2, 3, 4, and 5 from the Prelab exercises using the above applet, and then compare to your Prelab solutions.

#### Research Question 2

For the congruence equation ax b (mod n), determine conditions on a, b, and n for there to be at least one solution.

#### Research Question 3

Suppose that a, b, and n satisfy the conditions you gave in response to Research Question 2. Describe a method for finding a solution to ax b (mod n).

Hint: One possibility is trial and error; just plug each of x = 1, 2, 3, . . . , n – 1 into the congruence. This will work, but there is a better, more efficient answer.

#### Research Question 4

Suppose that a, b, and n satisfy the conditions you gave in response to Research Question 2, and that x0 is a solution to ax b (mod n). Find the form, in terms of x0, of all solutions x modulo n.

#### Research Question 5

Suppose that a, b, and n satisfy the conditions you gave in response to Research Question 2. How many distinct solutions x modulo n are there to ax b (mod n)?

Below are a collection of hints designed to help you as you work through the research questions from this section.

### 5.3.1  Hints

The full solution to Research Questions 2 to 5 may not be obvious at first, but in the end there is an elegant answer. One of our standard course strategies is particularly important here: If the general case stumps you, then study special cases first.

Another suggestion: If you have trouble working with the congruence, then use the definition of congruence to convert it to an equation of integers. This will allow you to apply everything that you have learned in earlier chapters to solve the problem.

#### 5.3.1.2   Multiplicative Inverses and Additive Orders

You have already worked extensively with two special cases of the congruence equation ax b (mod n). One was in connection with multiplicative inverses. Specifically, finding the multiplicative inverse of a modulo n is equivalent to solving the congruence equation

ax 1 (mod n).

In an earlier chapter you found a formula for the additive order of a modulo n. This required you to find all solutions to the congruence

ax 0 (mod n).

These are two special cases of our general congruence equation. You may be able to make use of what you know about these special cases to learn more about the general equation.

#### 5.3.1.3  Vary the value of b

In our general problem, there are three parameters: a, b, and n. Our hint here is to test specific values of a and n, and in each case compute all possible b so that the congruence ax b (mod n) has a solution. This is somewhat natural since it amounts to holding a and n fixed, and plugging in all values for x and then watching what values come out for b. The applet below automates this process by taking each value of j satisfying 0 j M, computing aj % n, and printing out a list of the resulting values. Here is an example:

Your browser does not support java.

Try experimenting with different values of a and n.

Section 5.1 | Section 5.2 | Section 5.3 | Section 5.4 | Section 5.5 | Section 5.6