# What does Linear Congruential mean?

How does one interpret the terms "Linear" and "Congruential" as in a "Linear congruential RNG"?

I am used to linearity by $f(ax)=af(x)$. This does not seem to me to hold true in this case ($\bmod$). I have no idea how to interpret the congruential part.

-
Note that there is more than one common use of the word "linear" in mathematics. $y=ax+b$ is linear in the sense that its graph is a straight line, even though it isn't linear in the sense of linear algebra. – Gerry Myerson Dec 7 '11 at 11:46
Knuth has entire chapter devoted to random numbers, TAOCP, Vol. 2, Chapter 3. In 3.2 he discusses Lehmer's work and the linear congruential method. – dbasnett Dec 7 '11 at 13:41
@dbasnett Yes, I have read Knuth's work and thats partly the reason why I am asking this question. (Proud owner of the 4 (3 1/2?) volumes) – Captain Giraffe Dec 7 '11 at 17:43
@Gerry Good point. – Captain Giraffe Dec 7 '11 at 17:44

$$x_{k+1}=(ax_k+b)\bmod M$$
where $x_0,a$ and $b$ are some integer parameters, and $M$ is a large integer only slightly below the largest representable integer on the machine.
We can see where the name comes from (which, BTW, is due to D.H. Lehmer): "linear" is due to the fact that the quantity whose remainder we are taking is the result of a linear function ($ax+b$), and "congruential", since we are performing a congruence operation (modulo).