Friday, September 7, 2007

a step beyond Euclid and Fermat, 6

Let  f : Z --> Z  be a polynomial function, i.e. f belongs to Z[X]. Then  f  is a residue obeying funtion, or  rof  for short, in the following sense:

  • if  x=y mod n   then   f(x) = f(y) mod n
for every integer x y and natural n.

Now let  f  be an arbitrary residue obeying function. Let's define sequence x(0) x(1) ... satisfy the following iterative equality:
  • x(n+1) = f(x(n))
for every   n=0 1...

Then x(0) x(1)... is a prime residue obeying sequence, or pros for short, in the following sense:

  • if   x(i) = x(j) mod p   then   x(i+1) = x(j+1) mod m
for every i j = 0 1... and prime p=2 3 5 7 11...

Thus every pros mod p is eventually periodic:

indeed, let sequence x(0) x(1)... be a pros, and let  p  be a prime; then there are nonegative integers  i < j ≤ p  such that  x(i) = x(j) mod p.  Then starting with the index  i,  sequence x(n) is periodic mod p:
  • x(n+d) = x(d) mod p
for   d := j-i,   and for every   n=i i+1...

This means that if prime  p  didn't divide any of the terms  x(0) ... x(j-1)  then  p  does not divide any term of the infinite sequence  x(0) x(1)....