Re: [math-fun] Fibonacci mod n question
Marc LeBrun writes: <<
=Dan Asimov ...QUESTION: What is a formula for fp(n) in general?
Interesting question, but isn't this basically asking for a formula for the multiplicative order of the matrix [1 1] [0 1] mod n? I understand that's hard for just integers; should we expect it to be easier in matrix land? (but fp(n) sounds like a great candidate for the OEIS!)
Maybe so about the matrices, but it appears there *is* a formula for fp(n) -- which turns out (no surprise!) to already be in OEIS. The OEIS entry mentions that for a prime p, (*) fp(p) = (p-1). Can someone please explain this notation to me? Thanks. Another comment at that entry is that if n = p1^e1*...* pk^ek, for distinct primes p1,..., pk, then (**) fp(n) = LCM(fp(p1^e1),...,fp(pk^ek)). And I've just noticed strong numerical evidence that for a prime power n = p^r, we have (***) fp(p^r) = p^(r-1) * fp(p). If (***) can be proved, then putting these three equations together gives essentially a formula for all fp(n). (But what the heck does (p-1) mean?!?!?) --Dan
1) If p is not 2 or 5, then the order of the matrix (0,1;1,1) is the multiplicative order of any eigenvalue (i.e. (1+/-sqrt(5))/2), since, for those p's the matrix is diagonalizable. 2) Again, for those p, by Hensel's lemma, fp(p^n) = p^(n-1) fp(p) 3) Since we're asking for the multipicative order of an element of a finite field, this is much like the question of Artin's conjecture which asks how often 2 is a primitive root (or more generally, how often a is a primitive root). The really interesting quantity is how far it deviates from the maximum value. So one would want to define fq(p) = (p-1)/fp(p) if 5 is a quadratic residue of p, and fq(p) = (p^2-1)/fp(p) if 5 is a quadratic non-residue of p. fq wouldn't be bounded, but would tend to be small. Victor
"Victor" == Victor S Miller <victor@idaccr.org> writes:
Victor> 3) Since we're asking for the Victor> multipicative order of an element of a finite field, this is Victor> much like the question of Artin's conjecture which asks how Victor> often 2 is a primitive root (or more generally, how often a is Victor> a primitive root). The really interesting quantity is how far Victor> it deviates from the maximum value. So one would want to Victor> define fq(p) = (p-1)/fp(p) if 5 is a quadratic residue of p, Victor> and fq(p) = (p^2-1)/fp(p) if 5 is a quadratic non-residue of Victor> p. fq wouldn't be bounded, but would tend to be small. Slight correction: if 5 is a non-residue, since Norm((1+sqrt(5))/2) = -1, (1+sqrt(5))/2 is contained in a cyclic subgroup of order 2*(p+1) (the elements of norm +/- 1), so that in this case we should define fq(p) = (2*(p+1))/fp(p). As I mentioned before, 5 is special. So that Chris's data would give (for the values of fq, instead of fp): mod 3 period 8 1 mod 7 period 16 1 mod 11 period 10 1 mod 13 period 28 1 mod 17 period 36 1 mod 19 period 18 1 mod 23 period 48 1 mod 29 period 14 2 mod 31 period 30 1 mod 37 period 76 1 mod 41 period 40 1 mod 43 period 88 1 mod 47 period 32 3 mod 53 period 108 1 mod 59 period 58 1 mod 61 period 60 1 mod 67 period 136 1 mod 71 period 70 1 mod 73 period 148 1 mod 79 period 78 1 mod 83 period 168 1 mod 89 period 44 2 Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor@idaccr.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin
participants (2)
-
dasimov＠earthlink.net -
victor＠idaccr.org