Example:
4x + 1 º x – 1 (mod 7).
4x – x + 1 º x – x – 1 (mod 7)
3x + 1 – 1 º – 1 – 1 (mod 7)
3x º -2 (mod 7)
3x º 5 (mod 7)
3^-1 ´ 3x º 3^-1 ´ 5 (mod 7)
5 ´ 3x º 5 ´ 5 (mod 7)     (since 3^-1 º 5 (mod 7))
x º 4 (mod 7)

We put all the variables on one side of the equation and the constants on the other, just as in secondary school algebra. Then we want to "divide" out by 3, the coefficient of the variable x. Division in this case is multiplication by the inverse, and checking the multiplication table for Z₇, we find the inverse of 3 (mod 7) is 5. So we multiply both sides by 5 to finally get our solution x º 4. We can check that 4 ´ 4 + 1 = 17 º 3 = 4 –1. Manipulations like these will let us find the unique solution to any linear equation in a field.

If we are in a ring like Z₁₀ rather than a field, then the situation is more complicated. Everything works fine until we want to "divide" out by the coefficient of the variable. That "division" is the problem shouldn’t be surprising. A commutative ring with identity like Z10 satisfies all the field rules except for the existence of multiplicative inverses (law 8), so if there were going to be a problem it would have to be with the inverse of multiplication. If the coefficient has an inverse, all is well and good. If the coefficient doesn’t have an inverse, then we don’t have a general way to divide and we may not be able to solve the problem. If we can solve the problem, we may have more than 1 solution.

Example:
4x + 1 º x – 1 (mod 10).
4x – x + 1 º x – x – 1 (mod 10)
3x + 1 – 1 º – 1 – 1 (mod 10)
3x º -2 (mod 10)
3x º 8 (mod 10)
3^-1 ´ 3x º 3^-1 ´ 8 (mod 10)
7 ´ 3x º 7 ´ 8 (mod 10)     (since 3^-1 º 7 (mod 10))
x º 6 (mod 10)

In the last example, everything worked out fine because 3 is invertible (mod 10). In the next two examples, we get a coefficient that isn’t invertible (mod 10) and things are a little trickier.

Example:
5x + 1 º x – 2 (mod 10)
5x – x +1 º x – x – 2 (mod 10)
4x + 1 –1 º –2 – 1 (mod 10)
4x º – 3 (mod 10)
4x º 7 (mod 10)
No solutions.

A check of the multiplication table for Z₁₀ shows that nothing times 4 gives 7, so there are no solutions to our problem. On the other hand, the next example shows we may have too many solutions.

Example:
5x + 1 º x – 1 (mod 10)
5x – x + 1 º x – x – 1 (mod 10)
4x + 1 – 1 º –1 – 1 (mod 10)
4x º –2 (mod 10)
4x º 8 (mod 10)
x º 2, 7 (mod 10)

It is tempting to jump immediately from 4x º 8 to x º 2, but that is not a complete answer. Recall that in the multiplication table for Z₁₀, the rows of numbers without inverses repeat so each product appears more than once. Since gcd(4,10) = 2, each product appears twice so we get two answers by looking at the table.

Of course, if we are working (mod 201), then writing out the multiplication table for Z₂₀₁ isn’t an efficient way of doing anything. From the previous lesson we know how to find the inverse of a number (mod 201), if it has an inverse, using the Euclidean algorithm. If it doesn’t have an inverse, then the Euclidean algorithm can still give us some useful information.

Example:
Does 18x º 116 (mod 201) have a solution?

No. We compute gcd(18,201)=3. 3 doesn’t divide 116 so there is no solution. To see why this is so, observe that we are looking for a value of x so 18x = 116 + 201y for some value of y. Then
18x – 201y = 116
3´6x - 3´67y = 116
3 ´ (6x - 67y) = 116
But since 116 isn’t divisible by 3, this is impossible.

Example:
Does 18x º 117 (mod 201) have a solution?

Yes. As before, gcd(18,201)=3, but this time 3 does divide 117, so we have a solution. In fact, we have 3 solutions since gcd(18,201)=3. As before, it is helpful to rewrite the problem as trying to find an x so 18x = 117 + 201y for some y. Then
18x – 201y = 117
3´6x - 3´67y = 117
3 ´ (6x – 67y) = 117
6x – 67y = 39

This looks like the sort of formula we learned to build in the section on inverses, and indeed we can finish our problem and find our values of x using the same techniques as in the last section on the Euclidean algorithm. On the homework you are asked to do exactly that. I’m not going to go into any more detail right now, so you can have the fun of working it out for yourself on the homework. One of the nice things about these problems is that you can check your work when you are done, so you will know if you have things worked out correctly or not. Good luck.