Exercise 4.4.2 ($\mathrm{gcd}(F_n, F_{n+1}) = 1$)

Question

Prove that two consecutive terms of the Fibonacci sequence are relatively prime.

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

\begin{proof} 
To avoid an induction, consider the function $f : \N 	o \N$ defined by  
$$f(n) = F_n \wedge F_{n+1}.$$
Then $f(0) = F_0 \wedge F_1 = 0 \wedge 1 = 1$.

Moreover, since $F_{n+2} = F_n + F_{n+1}$, for every integer $k$,
$$(k \mid F_n 	ext{ and } k \mid F_{n+1}) \iff (k \mid F_{n+1} 	ext{ and } k \mid F_{n+2}).$$
Thus
$$F_n \wedge F_{n+1} = F_{n+1} \wedge F_{n+2},$$
thus $f$ is a constant function, so $f(n) = f(0) = 1$ for all $n \in \N$.

$$\forall n \in \N, \ F_n \wedge F_{n+1} = 1.$$

\end{proof}

Exercise 4.4.2 ($\mathrm{gcd}(F_n, F_{n+1}) = 1$)

Answers

Comments

Exercise 4.4.2 ($\mathrm{gcd}(F_n, F_{n+1}) = 1$)

Answers

Comments

Add answer