More on Fibonacci numbers, Lucas numbers, and primes in progressions
in [Math]
|
Prev: Classification of semi-simple Lie groups
Next: using geometry's finite-line & infinite-line and line rays to hopefully well-define finite-number & infinite-number #623 Correcting Math
From: Achava Nakhash, the Loving Snake on 2 Jul 2010 12:39 I made an earlier post asking if it were known that any prime divisor of L(p) was congruent to 1 mod p and observed the implication that this allowed is to give an effective bound to the size of such a prime in a completely trivial way. I was using fairly complicated methods in pursuit of a completely different goal. Having thought about the specific issues above a little more, I realized that the fact I proved was actually a triviality that could be shown via methods that I understood back in high school, and I was not that advanced at that time. It turns out that, if you accept Carmichael's theorem that every Fibonacci number has a prime divisor that does not divide any previous Fibonacci number except for a couple of exceptional cases such as F(6) = 8 and F(12) = 144, then my methods give a high-school level proof if n is odd, L(n) has a prime divisor that is congruent to 1 mod n (and thus an explicit effective bound on this) but the proof does not appear to carry over to even n. However, if n is even, and not 6, or else odd,then L(n) has a prime divisor that is congruent to -1 mod n,and so another special cases of the Dirichlet theorem is proved easily by trivial methods (except for the Carmichael part) with an explicit upper bound. I don't recall having seen any quick proof that yields -1, although quite a few seem to yield +1. Along the way, I happened upon a characterization of which primes have the period length divided by the rank of apparition being 1, 2, or 4. For those who don't recognize these terms, the Fibonacci numbers mod n are periodic and so the period length has an obvious meaning. In particular, some Fibonacci number must be divisible by n. The rank of apparition is then the index of the first Fibonacci number divisible by n, and it is easy to show that it is either equal to, one half of, or one quarter of the period length. Given an odd prime p, look at the smallest index of either a Fibonacci or Lucas number divisible by p. Then if it belongs to a Lucas number of odd index, the quotient is 1, if it belongs to a Lucas number of even index, the quotient is 2, and if it belongs to a Fibonacci number of odd index,l the quotient is 4. It can't belong to a Fibonacci number of even index, so these are all the cases. The proofs of all of this stuff are high-school level. I felt a little stupid for not being able to come up with a quick, elementary proof of Carmichael's theorem, but it turns out that there aren't any. There is a 6-page paper in the Fibonacci quarterly from sometime in this century that purports to give a simple proof that is about 6 pages long. I haven't had a chance to look at it yet. If someone could email me a copy, it would be appreciated, since I don't get out much, My intuition says that there should be an easy way, and if I actually find one, I will let everyone know. Regards, Achava
From: Pubkeybreaker on 2 Jul 2010 13:48 On Jul 2, 12:39 pm, "Achava Nakhash, the Loving Snake" <ach...(a)hotmail.com> wrote: > I made an earlier post asking if it were known that any prime divisor > of L(p) was congruent to 1 mod p and observed the implication that > this allowed is to give an effective bound to the size of such a prime > in a completely trivial way. I was using fairly complicated methods > in pursuit of a completely different goal. > > Having thought about the specific issues above a little more, I > realized that the fact I proved was actually a triviality that could > be shown via methods that I understood back in high school, and I was > not that advanced at that time. > > It turns out that, if you accept Carmichael's theorem that every > Fibonacci number has a prime divisor that does not divide any previous > Fibonacci number except for a couple of exceptional cases such as F(6) > = 8 and F(12) = 144, then my methods give a high-school level proof if > n is odd, L(n) has a prime divisor that is congruent to 1 mod n (and > thus an explicit effective bound on this) but the proof does not > appear to carry over to even n. However, if n is even, and not 6, or > else odd,then L(n) has a prime divisor that is congruent to -1 mod > n,and so another special cases of the Dirichlet theorem is proved > easily by trivial methods (except for the Carmichael part) with an > explicit upper bound. I don't recall having seen any quick proof that > yields -1, although quite a few seem to yield +1. > > Along the way, I happened upon a characterization of which primes have > the period length divided by the rank of apparition being 1, 2, or 4. > For those who don't recognize these terms, the Fibonacci numbers mod n > are periodic and so the period length has an obvious meaning. In > particular, some Fibonacci number must be divisible by n. The rank of > apparition is then the index of the first Fibonacci number divisible > by n, and it is easy to show that it is either equal to, one half of, > or one quarter of the period length. > > Given an odd prime p, look at the smallest index of either a Fibonacci > or Lucas number divisible by p. Then if it belongs to a Lucas number > of odd index, the quotient is 1, if it belongs to a Lucas number of > even index, the quotient is 2, and if it belongs to a Fibonacci number > of odd index,l the quotient is 4. It can't belong to a Fibonacci > number of even index, so these are all the cases. The proofs of all > of this stuff are high-school level. > > I felt a little stupid for not being able to come up with a quick, > elementary proof of Carmichael's theorem, but it turns out that there > aren't any. There is a 6-page paper in the Fibonacci quarterly from > sometime in this century that purports to give a simple proof that is > about 6 pages long. I haven't had a chance to look at it yet. If > someone could email me a copy, it would be appreciated, since I don't > get out much, My intuition says that there should be an easy way, and > if I actually find one, I will let everyone know. See: Brillhart, Montgomery, Silverman Tables of Factorizations of Fibonacci and Lucas Numbers from Mathematics of Computation circa 1989
From: spudnik on 2 Jul 2010 15:00 so, L(n) is the Nth Lucas number?... and, whence the term, apparition? --BP's Rep. Waxman's cap&trade: free beer/miles with your CO2 creds! http://wlym.com
From: Achava Nakhash, the Loving Snake on 2 Jul 2010 15:55 On Jul 2, 12:00 pm, spudnik <Space...(a)hotmail.com> wrote: > so, L(n) is the Nth Lucas number?... Yes and, > whence the term, apparition? Presumably an awkward term that means "where it appears" Regards, Achava
From: Achava Nakhash, the Loving Snake on 6 Jul 2010 13:37
On Jul 2, 10:48 am, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > On Jul 2, 12:39 pm, "AchavaNakhash, the Loving Snake" > > > > > > <ach...(a)hotmail.com> wrote: > > I made an earlier post asking if it were known that any prime divisor > > of L(p) was congruent to 1 mod p and observed the implication that > > this allowed is to give an effective bound to the size of such a prime > > in a completely trivial way. I was using fairly complicated methods > > in pursuit of a completely different goal. > > > Having thought about the specific issues above a little more, I > > realized that the fact I proved was actually a triviality that could > > be shown via methods that I understood back in high school, and I was > > not that advanced at that time. > > > It turns out that, if you accept Carmichael's theorem that every > > Fibonacci number has a prime divisor that does not divide any previous > > Fibonacci number except for a couple of exceptional cases such as F(6) > > = 8 and F(12) = 144, then my methods give a high-school level proof if > > n is odd, L(n) has a prime divisor that is congruent to 1 mod n (and > > thus an explicit effective bound on this) but the proof does not > > appear to carry over to even n. However, if n is even, and not 6, or > > else odd,then L(n) has a prime divisor that is congruent to -1 mod > > n,and so another special cases of the Dirichlet theorem is proved > > easily by trivial methods (except for the Carmichael part) with an > > explicit upper bound. I don't recall having seen any quick proof that > > yields -1, although quite a few seem to yield +1. > > > Along the way, I happened upon a characterization of which primes have > > the period length divided by the rank of apparition being 1, 2, or 4. > > For those who don't recognize these terms, the Fibonacci numbers mod n > > are periodic and so the period length has an obvious meaning. In > > particular, some Fibonacci number must be divisible by n. The rank of > > apparition is then the index of the first Fibonacci number divisible > > by n, and it is easy to show that it is either equal to, one half of, > > or one quarter of the period length. > > > Given an odd prime p, look at the smallest index of either a Fibonacci > > or Lucas number divisible by p. Then if it belongs to a Lucas number > > of odd index, the quotient is 1, if it belongs to a Lucas number of > > even index, the quotient is 2, and if it belongs to a Fibonacci number > > of odd index,l the quotient is 4. It can't belong to a Fibonacci > > number of even index, so these are all the cases. The proofs of all > > of this stuff are high-school level. > > > I felt a little stupid for not being able to come up with a quick, > > elementary proof of Carmichael's theorem, but it turns out that there > > aren't any. There is a 6-page paper in the Fibonacci quarterly from > > sometime in this century that purports to give a simple proof that is > > about 6 pages long. I haven't had a chance to look at it yet. If > > someone could email me a copy, it would be appreciated, since I don't > > get out much, My intuition says that there should be an easy way, and > > if I actually find one, I will let everyone know. > > See: Brillhart, Montgomery, Silverman > Tables of Factorizations of Fibonacci and Lucas Numbers > from Mathematics of Computation circa 1989- Hide quoted text - > > - Show quoted text - Thanks for the tip. I don't have any time these days to do math or much of a chance to look things up, as I now have restricted internet access. I think I have a very elementary proof of Carmichael's theorem that there is a new prime divisor of every Fibonacci number with a few exceptions such as the 6'th and 12'th. Unfortunately, I don't know how long it will be before I will have the time and space to write it all down. Regards, Achava |