More mathblogging.
A while back, I was interested in what the fibonacci numbers have to say about primes.
The fibonaccis, defined with a seed of 1, 1 for elements 1, 2, have a number of very predictable patterns. For example, every third one is even, every fifth one is a multiple of 5, etc.
They share some interesting properties with the natural numbers which are important for determining anything about prime numbers with them.
Define: F(n)= the nth fibonacci number.
I. For all n and m in Z+, if n divides m, then F(n) divides F(m).
This is a powerful link between the natural numbers, Z+, and the positively indexed Fibonacci numbers, call them F+. It gives us a range within which we MAY find primes in the Fibonacci sequence, because of the definition of prime number: no number divides a prime besides itself and 1.
II. Therefore, we only need to look at F(p), where p is prime, to look for prime numbers.
Is that true? Trivially not. The fourth prime number is 3, and 4 is not prime. Why is that the case in the face of the obviousness of II? Well, F(2) = 1. Therefore F(2) divides F(4), even though F(4) is prime. However, it can be demonstrated that this is a special case: All Fibonaccis above F(2) are greater than 1, and all fibonaccis of the form F(2k) will have F(k) as a factor. If k>2, then statement II. holds.
Does this mean that all F(p) are prime? Absolutely not. Many are composites composed of unique primes. However, we can say something more if we recognize another fact of the fibonaccis.
III. For any sufficiently large h and j, if h and j are relatively prime, F(h) and F(j) are relatively prime.
Relatively prime is a term describing whether two numbers share common factors. For example, 14 and 15 are relatively prime, because the only common factor they share is 1. 39 and 21 are NOT relatively prime, because they share 3 as a common factor. Why is this important? It says that unless (prime) p is a factor of q, F(p) and F(q) are relatively prime. Therefore, any factors of F(p) are not found elsewhere in the fibonacci sequence. Basically, they are "new" primes, when they are encountered in F(p). So, one can generate a set of numbers with unique prime factors easily enough by calculating F(P), where P is the set of primes.
This will not cover all the primes; the fibonacci sequence introduces new primes into it's makeup via other means than just F(p). However, you can make a nifty and large (infinite) list.
The fibonaccis, defined with a seed of 1, 1 for elements 1, 2, have a number of very predictable patterns. For example, every third one is even, every fifth one is a multiple of 5, etc.
They share some interesting properties with the natural numbers which are important for determining anything about prime numbers with them.
Define: F(n)= the nth fibonacci number.
I. For all n and m in Z+, if n divides m, then F(n) divides F(m).
This is a powerful link between the natural numbers, Z+, and the positively indexed Fibonacci numbers, call them F+. It gives us a range within which we MAY find primes in the Fibonacci sequence, because of the definition of prime number: no number divides a prime besides itself and 1.
II. Therefore, we only need to look at F(p), where p is prime, to look for prime numbers.
Is that true? Trivially not. The fourth prime number is 3, and 4 is not prime. Why is that the case in the face of the obviousness of II? Well, F(2) = 1. Therefore F(2) divides F(4), even though F(4) is prime. However, it can be demonstrated that this is a special case: All Fibonaccis above F(2) are greater than 1, and all fibonaccis of the form F(2k) will have F(k) as a factor. If k>2, then statement II. holds.
Does this mean that all F(p) are prime? Absolutely not. Many are composites composed of unique primes. However, we can say something more if we recognize another fact of the fibonaccis.
III. For any sufficiently large h and j, if h and j are relatively prime, F(h) and F(j) are relatively prime.
Relatively prime is a term describing whether two numbers share common factors. For example, 14 and 15 are relatively prime, because the only common factor they share is 1. 39 and 21 are NOT relatively prime, because they share 3 as a common factor. Why is this important? It says that unless (prime) p is a factor of q, F(p) and F(q) are relatively prime. Therefore, any factors of F(p) are not found elsewhere in the fibonacci sequence. Basically, they are "new" primes, when they are encountered in F(p). So, one can generate a set of numbers with unique prime factors easily enough by calculating F(P), where P is the set of primes.
This will not cover all the primes; the fibonacci sequence introduces new primes into it's makeup via other means than just F(p). However, you can make a nifty and large (infinite) list.