Integers and Congruences - Part V

An Application of Congruence

Example - ISBN

An interesting application of modulus is in ISBN. Maybe you have wondered why some books have an ISBN which ends in X? This is because the last digit is a check digit, calculated modulo 11, so an extra 'digit' is required to symbolise 10. How is the check digit calculated? It is a weighed sum, which means that each digit is multiplied by a fixed amount, and then the sum is taken. Suppose the ISBN is a₁a₂a₃a₄a₅a₆a₇a₈a₉a₁₀. Then the weighted sum is

ax b (mod n)

Next we are going to look at solving congruences, but first, let's consider the following situtation. Suppose

3x=34.

Then we cancel and get x=4. Nothing strange about that. Now let's look at the same thing, but this time, modulo 24:

3x34 (mod 24).

Is it true to say that x4? What if x12? Then

312 36 12 34 (mod 24).

This illustrates the fact that we must be very careful when cancelling while working with congruences. What you might wonder is if there is ever a time when we can cancel, and yes there is. We will come to that in a moment, after we have looked at the problem a bit more.

The Problem with Cancellation

Solve the equations

1. 2 x 8 (mod 4)
2. 2 x 3 (mod 4)
3. 3 x 2 (mod 4)

Solution

We use trial and error.

1. Solutions are all integers x such that x 0 (mod 4) or x 2 (mod 4).
2. There are no solutions.
3. Solutions are all integers x such that x 2 (mod 4).

We mentioned earlier than if ax b (mod n), then we can write ax+nq=b for some integer q. From a result on diophantine equations, we know there is a solution to the equation ax+nq=b if and only if gcd(a,n) | b. This means that there is a solution to the congruence ax b (mod n) if and only if gcd(a,n) | b.

In one of the examples above we got one solution from 0,1,2,3, and for another we got two solutions from 0,1,2,3. How do we know how many solutions we will get in this range, and how can we be sure we have found them all? Let's think about the diophantine equations again. We can write 2 x 8 (mod 4) as 2x+4y=8 for some integer y. Now dividing by 2, we find that we get x+2y=4, that is x 4 (mod 2). We might have thought that we could cancel to get x 4 (mod 4), but that would have meant that we missed some possible values of x - all those congruent to 2 modulo 4. What we should do is divide by 2 thoughout: 2x/2 8/2 (mod 4/2). We summarise in the following result.

Result 1

If ax ay (mod an), then x y (mod n).

Example

Find all values of x which satisfy the congruence 5x 10 (mod 15).

As gcd(5,15)=5 is a factor of 10, there are solutions. We divide by 5 to get x 2 (mod 3). This gives the following values for x (mod 15): 2,5,8,11,14.

Example

Find all values of x which satisfy the congruence 5x 10 (mod 18).

As gcd(5,18)=1 is a factor of 10, there are solutions. We write the congruence as a diophantine equation: 5x+18y=10, where x and y are integers. By inspection, we see that a solution is given by x=-16 and y=5, and so the general solution is x=-16+18t, y=5-5t, for integers t. So x=-16+18t -16 2(mod 18).

Suppose we have ax b (mod n) and we can find an integer r so that ar 1 (mod n). Then we have rax rb (mod n) and so x rb (mod n) as ar 1 (mod n). When does such an integer r exist? It exists if there is a solution to ar=1 + kn (integer k). There is a solution exactly when gcd(a,n) | 1, that is, when gcd(a,n)=1. This is summarised in the following result.

Result 2

Suppose ax b (mod n), where gcd(a,n)=1. Then there is an integer r such that ar 1 (mod n) and x rb (mod n).

One question which may arise is why, when we divided by a, did we divide everything by a:

ax ay (mod an) x y (mod n)

but when we multiplied by r, we didn't multiply the modulus by r:

ax b (mod n) rax rb (mod n)?

The answer is as follows. First we write the congruence as a diophantine equation: ax b (mod n) becomes ax+yn=b where y is an integer. Now we multiply by r to get rax+ryn=rb. Now as ryn is divisible by n, it is congruent to 0 modulo n. Hence rax rb (mod n), as required.

Result 3

If a b (mod mn) then a b (mod n) and a b (mod m)

Example

Find all values of x which satisfy the congruence 5x 10 (mod 18).

As gcd(5,18)=1, there is an integer r such that 5r 1 (mod 18). To find r, we either solve the diophantine equation 5r+18y=1, or we use trial and error. Take r=-7, to get 5(-7)=-35 1 (mod 18). Now we apply the result above to 5x 10 (mod 18) to get x -70 2 (mod 18).

Exercises

1. Solve the following congruences where possible
   1. 4x 5 (mod 9)
   2. 4x 5 (mod 8)
   3. 4x 8 (mod 12)
   4. 18x 5 (mod 29)
2. Determine the missing digit '?' in ISBN 91-518-?600-3.
3. Decide which of the following are possible ISBN.
   1. 91-46-16515-0
   2. 91-46-16616-X
   3. 1-55615-104-7

Simultaneous Congruences

Now that we have covered solving individual congruences, we look at solving simultaneous congruences. Again, we rely on the techniques we developed earlier to solve diophantine equations.

Example

Consider x 5 (mod 12) (*) and x 7 (mod 16) (**). From result 3 above, we know that x 5 (mod 12) x 5 (mod 2) and x 5 (mod 3) and x 5 (mod 4) and x 5 (mod 6). Similarly x 7 (mod 16) x 7 (mod 2) and x 7 (mod 4) and x 7 (mod 8). So x 5 1 (mod 4) and x 7 3 (mod 4), which is a contradiction. Hence there are no solutions to this pair of simultaneous equations.

Example

Solve the simultaneous congruences x 5 (mod 12) and x 3 (mod 5).

Solution

• First we write the congruences as diophantine equations to get
  x=5+12t (*) and x=3+5s, integers s, t
  Note that we use different paramenters s and t.
• Now we eliminate x from the equations, by subtracting one from the other, to get a single diophantine equation
  5s-12t=2 integers s, t
• Now we find a general solution to the diophantine equation. By inspection, we see that s=2 and t=1 is one solution. This gives the general solution
  s=2+(-12)/1 u =2-12u and t=1-5/1 u=1-5u for integers u.
• We substitute for t into * to get
  x=5+12(1-5u)=17-60u 17 (mod 60).
• Finally, we check our answer:
  x=17-60u5 (mod 12) and x=17-60u2 (mod 5), which is correct.

Exercises

1. x 5 (mod 9) and x 7 (mod 13)
2. x 11 (mod 12) and x 12 (mod 13)
3. 2x 5 (mod 12) and 5x 7 (mod 13)
4. x 4 (mod 12) and x 7 (mod 26)
5. x 5 (mod 12) and x 7 (mod 26)