# Thread: Fibonacci relative prime proof

1. ## Fibonacci relative prime proof

Hey Guys, learning discrete math by myself and while I was working with a proof, I got stuck, I checked the solution and I understand the big picture but I can't seem to understand the arithmetic, here's how it goes:

By induction Let P(n) be the proposition that Fn and Fn+1 are relatively prime.

Base case: P (0) is true because F0 = 0 and F1 = 1 are relatively prime.

Inductive step: We show that, for all n 0, P(n) implies P(n + 1). So, fix some n 0and assume that P (n) is true, that is, Fn and Fn+1 are relatively prime. We will show thatFn+1 and Fn+2 are relatively prime as well. We will do this by contradiction.

Suppose
Fn+1 and Fn+2 are not relatively prime. Then they have a common divisor d > 1.But then d also divides the linear combination Fn+2 Fn+1, which actually equals Fn. Hence, d > 1 divides both Fn and Fn+1. Which implies Fn, Fn+1 are not relatively prime, a contradiction to the inductive hypothesis.

Therefore,
Fn+1 and Fn+2 are relatively prime. That is, P (n
+ 1) is true.

How in the hell
Fn+2 Fn+1 equals Fn ??

2. ## Re: Fibonacci relative prime proof

Seriously? The Fibonacci numbers are defined by $\displaystyle F_{n+2}= F_n+ F_{n+1}$. Subtract $\displaystyle F_{n+1}$ from both side.

3. ## Re: Fibonacci relative prime proof

Yeah well I'm dumb sorry ...