Page 310 - Discrete Mathematics and Its Applications

4.5 Applications of Congruences 289

Many computer experiments require the generation of pseudorandom numbers between 0
and 1. To generate such numbers, we divide numbers generated with a linear congruential
generator by the modulus: that is, we use the numbers x n /m.

EXAMPLE 3 Find the sequence of pseudorandom numbers generated by the linear congruential method with
modulus m = 9, multiplier a = 7, increment c = 4, and seed x 0 = 3.

Solution: We compute the terms of this sequence by successively using the recursively defined
function x n+1 = (7x n + 4) mod 9, beginning by inserting the seed x 0 = 3tofind x 1 . We find
that

x 1 = 7x 0 + 4 mod 9 = 7 · 3 + 4 mod 9 = 25 mod 9 = 7,
x 2 = 7x 1 + 4 mod 9 = 7 · 7 + 4 mod 9 = 53 mod 9 = 8,
x 3 = 7x 2 + 4 mod 9 = 7 · 8 + 4 mod 9 = 60 mod 9 = 6,
x 4 = 7x 3 + 4 mod 9 = 7 · 6 + 4 mod 9 = 46 mod 9 = 1,
x 5 = 7x 4 + 4 mod 9 = 7 · 1 + 4 mod 9 = 11 mod 9 = 2,
x 6 = 7x 5 + 4 mod 9 = 7 · 2 + 4 mod 9 = 18 mod 9 = 0,
x 7 = 7x 6 + 4 mod 9 = 7 · 0 + 4 mod 9 = 4 mod 9 = 4,
x 8 = 7x 7 + 4 mod 9 = 7 · 4 + 4 mod 9 = 32 mod 9 = 5,
x 9 = 7x 8 + 4 mod 9 = 7 · 5 + 4 mod 9 = 39 mod 9 = 3.

Because x 9 = x 0 and because each term depends only on the previous term, we see that the
sequence

3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3,...

is generated. This sequence contains nine different numbers before repeating. ▲

Most computers do use linear congruential generators to generate pseudorandom numbers.
Often, a linear congruential generator with increment c = 0 is used. Such a generator is called
a pure multiplicative generator. For example, the pure multiplicative generator with modulus
5
2 31 − 1 and multiplier 7 = 16,807 is widely used. With these values, it can be shown that
2 31 − 2 numbers are generated before repetition begins.
Pseudorandom numbers generated by linear congruential generators have long been used
for many tasks. Unfortunately, it has been shown that sequences of pseudorandom numbers gen-
erated in this way do not share some important statistical properties that true random numbers
have. Because of this, it is not advisable to use them for some tasks, such as large simulations.
For such sensitive tasks, other methods are used to produce sequences of pseudorandom num-
bers, either using some sort of algorithm or sampling numbers arising from a random physical
phenomenon. For more details on pseudorandom number, see [Kn97] and [Re10].

Check Digits

Congruences are used to check for errors in digit strings. A common technique for detecting
errors in such strings is to add an extra digit at the end of the string. This final digit, or check digit,
is calculated using a particular function. Then, to determine whether a digit string is correct, a
check is made to see whether this final digit has the correct value. We begin with an application
of this idea for checking the correctness of bit strings.