Math Is Fun Forum

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Why does an Linear Congruential Generator work?

suppose you have a pair of number a and b, whose largest common factor is 1.
And you multiply a by natural numbers then divide the result by b and get remainders. It must be b times until you get the same remainder when each the non negative numbers smaller than b appears once.

e.g

7 5
7*1=7 7|5=1...2
7*2=14 14|5=3...4
7*3=21 21|5=4...1
7*4=28 28|5=5...3
7*5=35          ...0

Apparently this theorem shall be proven by contradiction

But does anyone remember what this theorem is called?

---

X'(y-Xβ)=0

Bob

Administrator

Registered: 2010-06-20

Posts: 10,167

Re: Why does an Linear Congruential Generator work?

Hi George Y,

It must be 40 years since I did this so what follows is 'covered in mathematical rust'. 

Cannot recall that it is a named theorem at all.  I had a quick trawl on Wiki but found nothing.  But it may be there somewhere.  Best guess is Gauss discovered/proved it first.

To prove:

(i)  You won't get a zero remainder.

Assume you do.  => axn (for some integer n) = b x m (for some other integer m)

=> a and b have a prime factor other than 1 =><=

(ii)  Assume two integers give the same remainder

=> axn = axm for different integers n and m

=> a(n-m) = 0

=><= (i)

(i) and (ii) together => every remainder will occur once and once only.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Why does an Linear Congruential Generator work?

Indeed bob it should be proved this way.
I already asked JaneFairFox for help, for she mentioned this theorem before.

---

X'(y-Xβ)=0