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: Carl W. on 6 Jul 2010 16:59 On 6 July, 18:37, "Achava Nakhash, the Loving Snake" <ach...(a)hotmail.com> wrote: > 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 I looked at things like this briefly a month or so ago, but hadn't made much progress before heading off in a different direction entirely once I discovered the Perrin sequence: http://en.wikipedia.org/wiki/Perrin_number http://mathworld.wolfram.com/PerrinSequence.html ....which is a cousin to the Fibonacci and Lucas sequences. In case your aforementioned limited internet access prevents you from visiting the above URLs, Here's the first part of the Wikipedia entry: --- begin quoted text --- In mathematics, the Perrin numbers are defined by the recurrence relation P(0) = 3, P(1) = 0, P(2) = 2, and P(n) = P(n - 2) + P(n - 3) for n > 2. The sequence of Perrin numbers starts with 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... --- end quoted text --- The sequence has the interesting property that for all primes p, p divides P(p). There are also some composite c for which c divides P(c), but this is a much rarer occurrence. Whether this is relavent to your research I don't know, but thought I would mention it anyway. Good luck, Carl
From: Achava Nakhash, the Loving Snake on 10 Jul 2010 15:22
On Jul 6, 1:59 pm, "Carl W." <googlen...(a)phodd.net> wrote: > On 6 July, 18:37, "AchavaNakhash, the Loving Snake" > > > > > > <ach...(a)hotmail.com> wrote: > > 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 > > I looked at things like this briefly a month or so ago, but hadn't > made much progress before heading off in a different direction > entirely once I discovered the Perrin sequence: > http://en.wikipedia.org/wiki/Perrin_number > http://mathworld.wolfram.com/PerrinSequence.html > > ...which is a cousin to the Fibonacci and Lucas sequences. > > In case your aforementioned limited internet access prevents you from > visiting the above URLs, > Here's the first part of the Wikipedia entry: > > --- begin quoted text --- > In mathematics, the Perrin numbers are defined by the recurrence > relation > P(0) = 3, P(1) = 0, P(2) = 2, > and > P(n) = P(n - 2) + P(n - 3) for n > 2. > The sequence of Perrin numbers starts with > 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... > --- end quoted text --- > > The sequence has the interesting property that for all primes p, p > divides P(p). There are also some composite c for which c divides > P(c), but this is a much rarer occurrence. > > Whether this is relavent to your research I don't know, but thought I > would mention it anyway. > > Good luck, > Carl- Thanks Carl. I hadn't heard of these before. Regards, Achava |