In a previous chapter, you completely determined all solutions to the linear diophantine equation
Our goal in this section will be to do the same for the linear congruence equation
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:
- Are there any solutions?
- If there are solutions, what are they?
- 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):
Here are all of the solutions to
6x 9 (mod 15):
And here are all of the solutions to
10x 35 (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 1Compute 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 |
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 |
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 |
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 |
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 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
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
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:
Try experimenting with different values of a and n.