A well-known result about Fibonacci numbers says
gcd(Fm, Fn) = Fgcd(m, n)
In words, the greatest common divisor of the mth and nth Fibonacci numbers is the gth Fibonacci number where g is the greatest common divisor of m and n.
M. Wunderlich used this identity to create a short, clever proof that there are infinitely many primes.
Suppose on the contrary that there are only k prime numbers, and consider the set of Fibonacci numbers with prime indices: Fp1, Fp2, … Fpk. The Fibonacci theorem above tells us that these Fibonacci numbers are pairwise relatively prime: each pair has greatest common divisor F1 = 1.
Each of the Fibonacci numbers in our list must have only one prime factor. Why? Because we have assumed there are only k prime numbers, and no two of our Fibonacci numbers share a prime factor. But F19 = 4181 = 37*113. We’ve reached a contradiction, and so there must be infinitely many primes.
Source: M. Wunderlich, Another proof of the infinite primes theorem. American Mathematical Monthly, Vol. 72, No. 3 (March 1965), p. 305.
Here are a couple more unusual proofs that there are infinitely many primes. The first uses a product of sines. The second is from Paul Erdős. It also gives a lower bound on π(N), the number of primes less than N.
The proof is wrong because F_2 = 1
Good catch! I didn’t see that, and neither did Wunderlich or his editors. So leaving out F_2, we have k primes and k-1 Fibonacci numbers bigger than 1. Finding a Fibonacci number with two prime factors doesn’t establish a contradiction. But F_37 = 24157817 = 73*149*2221 has three factors, and that does establish a contradiction.
I’m wondering: what (set of weakest) properties does a sequence need to have for the GCD-identity to be true. F = Fib works but that’s relatively arbitrary.
Where can i find the proof for gcd(Fa,Fb)?
>A well-known result about Fibonacci numbers says
>gcd(Fm, Fn) = Fgcd(m, n)
>In words, the greatest common divisor of the mth and nth Fibonacci >numbers is the gth Fibonacci number where g is the greatest common >divisor of m and n. You can find a proof here.
Here is where?
thx
Regarding the catch.
i thought F0=F1=1 and F2=2