[seqfan] Re: x(i-1) = ( x(i+1) - x(i)) mod M, period-N solutions?
Andrew N W Hone
A.N.W.Hone at kent.ac.uk
Mon Sep 6 12:28:30 CEST 2010
Hi -
I see that you are looking at the periods of the Fibonacci sequence mod M.
I'm afraid I haven't been following this discussion closely, but it relates to a project I gave to some clever secondary school students this summer,
to teach them about modular arithmetic.
There is rather a lot of work on this problem (i.e. linear recurrence sequences mod M) in the literature, and apparently it has applications to codes/cryptography as well.
A good reference is the book "Recurrence Sequences" by Everest, van der Poorten, Shparlinski & Ward - see
http://www.ams.org/bookstore-getitem/item=surv-104
The book is a survey volume and maybe rather tough to dive into for non-professionals. I am away in Germany for a fortnight
and don't have my copy with me, so I cannot provide the page reference, but there is a chapter that discusses
the reduction of linear (and also some nonlinear) recurrences mod M; I recall that there is a reference to a survey
article by Richard Pinch, but I have not sought out the reference myself.
However, I can give a brief explanation of the periods in the case that M=p, a prime. (The case of composite M is
rather more complicated.) In the case M=p, one is
considering the Fibonacci recurrence
x(i+1)=x(i) + x(i-1)
with initial data (x(0),x(1)) \in F_p^2 = F_p \times F_p (the affine plane defined over the finite field F_p=Z/pZ). So there are p^2 different initial
values, but we can ignore the trivial (0,0) which just gives the sequence 0,0,0,... So the problem is to determine the period of the
orbit starting from a given pair of initial values
The general solution of Fibonacci for arbitrary initial values is
x(i) = A c_+^i + B c_-^i
where c_\pm = (1 \pm \sqrt{5})/2 are the roots of the quadratic x^2 = x+1 (the golden mean and - its reciprocal).
So for given initial values, one can fix the constants A,B, and then the length of the orbit, which is the period you are looking forward, is determined by the
multiplicative period N of the numbers c_+ and c_- (which are the same), that is the smallest N such that
c_+^N = 1 = c_-^N.
However, now this depends on whether \sqrt{5} belongs to F_p or not (i.e. whether 5 is a quadratic residue mod p; this can only happen
when p = +1 or -1 mod 10).
For example, for p=11, we have 4^2 = 16 =5, and (-4)^2=7^2=5, so the two square roots of 5 in F_{11} are 4 and 7.
These are elements of the cyclic multiplicative group F_{11}^*=F_{11} \ {0} of order 10 = p-1, so their multiplicative periods
must be factors of 10; indeed 4^5 = 1 = 7^5 mod 11. So the only possible periods mod 11 are 1 and 5.
On the other hand, for p=7, 5 is not a quadratic residue, so the formula for x(i) doesn't make sense in F_7, but in
the field extension F_7[\sqrt{5}], which is isomorphic to the finite field F_{7^2}=F_49, which can
be realized as numbers of the form
a + b \sqrt{5},
where a and b belong to F_7. Now c_+ and c_- belong to the cyclic group F_{49}^* of order 48 = p^2-1.
Then I believe F_p^2 splits up into p-1 orbits of length p+1, as well as the trivial orbit (0,0) of length 1.
So in this case (p=7) the period is 8=p+1.
Andy
________________________________________
From: seqfan-bounces at list.seqfan.eu [seqfan-bounces at list.seqfan.eu] On Behalf Of Ron Hardin [rhhardin at att.net]
Sent: 04 September 2010 13:41
To: seqfan at list.seqfan.eu
Subject: [seqfan] x(i-1) = ( x(i+1) - x(i)) mod M, period-N solutions?
T(N,M) is the number of nonzero solutions of x(i-1) = (x(i+1) - x(i)) mod M,
with period N
for N=12 M=10 there are 19 (including shifted multiplicities)
1 0 5 5 0 5 5 0 5 5 0 5 5
2 5 0 5 5 0 5 5 0 5 5 0 5
3 5 5 0 5 5 0 5 5 0 5 5 0
4 1 3 4 7 1 8 9 7 6 3 9 2
5 1 8 9 7 6 3 9 2 1 3 4 7
6 6 3 9 2 1 3 4 7 1 8 9 7
7 6 8 4 2 6 8 4 2 6 8 4 2
8 2 1 3 4 7 1 8 9 7 6 3 9
9 2 6 8 4 2 6 8 4 2 6 8 4
10 7 1 8 9 7 6 3 9 2 1 3 4
11 7 6 3 9 2 1 3 4 7 1 8 9
12 4 2 6 8 4 2 6 8 4 2 6 8
13 4 7 1 8 9 7 6 3 9 2 1 3
14 9 2 1 3 4 7 1 8 9 7 6 3
15 9 7 6 3 9 2 1 3 4 7 1 8
16 3 4 7 1 8 9 7 6 3 9 2 1
17 3 9 2 1 3 4 7 1 8 9 7 6
18 8 4 2 6 8 4 2 6 8 4 2 6
19 8 9 7 6 3 9 2 1 3 4 7 1
T(N,M) starts (rows N=1.. cols M=1..)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0
0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0
0 3 0 15 0 3 0 15 0 3 0 15 0 3 0 15 0 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 8 0 4 8 0 0 8 4 0 8 0 0 44 0 0 8 0
0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 3 18
0 0 0 0 0 0 0 0 0 0 120 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 0 15 4 3 0 63 0 19 0 15 0 3 4 63 0 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 0 3 0 3 0 3 0 3 10 3 0 3 0 3 0 3 0
0 0 8 0 4 8 48 0 8 4 0 8 0 48 44 0 0 8 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 0 15 0 3 0 15 0 3 0 15 0 3 0 15 0 3 360
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 24 0 0 0 0 24 120 0 0 0 24 0 0 0 0
full current table occasionally updated at
http://rhhardin.home.mindspring.com/current5.txt
Ideas, formulas, is it already in OEIS in some form...?
rhhardin at mindspring.com
rhhardin at att.net (either)
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list