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

axb(modn).Specifically, if

a,b, andnare integers (withnpositive), then we want to completely answer the following three questions for this congruence equation:

- Are there any solutions?
- If there are solutions,
whatare they?- If there are solutions,
how manyare 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, andnare given, then the solutions can be determined by simply trying all possible congruence classes forx. The applet below does just that. For example, here are all of the solutions to 2x5 (mod 11):Here are all of the solutions to 6

x9 (mod 15):And here are all of the solutions to 10

x35 (mod 42):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

axb(modn), determine conditions ona,b, andnfor there to be at least one solution.

## Research Question 3

Suppose that

a,b, andnsatisfy the conditions you gave in response to Research Question 2. Describe a method for finding a solution toaxb(modn).

Hint:One possibility is trial and error; just plug each ofx= 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, andnsatisfy the conditions you gave in response to Research Question 2, and thatx_{0}is a solution toaxb(modn). Find the form, in terms ofx_{0}, of all solutionsxmodulon.

## Research Question 5

Suppose that

a,b, andnsatisfy the conditions you gave in response to Research Question 2. How many distinct solutionsxmodulonare there toaxb(modn)?Below are a collection of hints designed to help you as you work through the research questions from this section.

## 5.3.1 Hints

## 5.3.1.1 General Advice

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

axb(modn). One was in connection with multiplicative inverses. Specifically, finding the multiplicative inverse ofamodulonis equivalent to solving the congruence equationax1 (modn).In an earlier chapter you found a formula for the additive order of

amodulon. This required you to find all solutions to the congruenceax0 (modn).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

bIn our general problem, there are three parameters:

a,b, andn. Our hint here is to test specific values ofaandn, and in each case compute all possiblebso that the congruenceaxb(modn) has a solution. This is somewhat natural since it amounts to holdingaandnfixed, and plugging in all values forxand then watching what values come out forb. The applet below automates this process by taking each value ofjsatisfying 0jM, computingaj%n, and printing out a list of the resulting values. Here is an example:Try experimenting with different values of

aandn.

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

Copyright © 2001 by W. H. Freeman and Company