There is a very, very fast way of computing the greatest common divisor of two positive integers. It was in fact known even to the Greeks two thousand years ago. This procedure is called the Euclidean algorithm, named after Euclid, a famous ancient Greek mathematician.
The algorithm works as follows. Take two positive integers \(a,b\). Let’s say \(a\geq b\).
Calculate the remainder of \(a\) when divided by \(b\). Call it \(r_1\).
Calculate the remainder of \(b\) when divided by \(r_1\). Call it \(r_2\).
Calculate the remainder of \(r_1\) when divided by \(r_2\). Call it \(r_3\).
Continue to divide the remainder from two steps prior by the remainder from the last step, until...
The remainder \(r_n\) is divisible by \(r_{n+1}\). The Euclidean algorithm stops now and \(r_{n+1}\) is \(\gcd(a,b)\).
Show that there is indeed some natural number \(n\) such that \(r_n\) is divisible by \(r_{n+1}\), so that the Euclidean algorithm must stop eventually. Furthermore, show that \(r_{n+1}\) is actually \(\gcd(a,b)\) (otherwise it is all in vain!).
Does there exist an irreducible tiling with \(1\times2\) rectangles of a \(6\times 6\) rectangle?
Irreducibly tile a floor with \(1\times2\) tiles in a room that is a \(6\times8\) rectangle.
Prove that every pair of consecutive Fibonacci numbers are coprime. That is, they share no common factors other than 1.
Calculate the following: \(F_1^2-F_0F_2\), \(F_2^2-F_1F_3\), \(F_3^2-F_2F_4\), \(F_4^2-F_3F_5\) and \(F_5^2-F_4F_6\). What do you notice?
Work out \(F_3^2-F_0F_6\), \(F_4^2-F_1F_7\), \(F_5^2-F_2F_8\) and \(F_6^2-F_3F_9\). What pattern do you spot?
Can every whole number be written as the sum of two Fibonacci numbers? If yes, then prove it. If not, then give an example of a number that can’t be. The two Fibonacci numbers don’t have to be different.
What’s \(\sum_{i=0}^nF_i^2=F_0^2+F_1^2+F_2^2+...+F_{n-1}^2+F_n^2\) in terms of just \(F_n\) and \(F_{n+1}\)?
What are the ratios \(\frac{F_2}{F_1}\), \(\frac{F_3}{F_2}\), and so on until \(\frac{F_7}{F_6}\)? What do you notice about them?
\(\varphi=\frac{1+\sqrt{5}}{2}\) is the golden ratio. Using the fact that \(\varphi^2=\varphi+1\), can you express \(\varphi^3\) in the form \(a\varphi+b\), where \(a\) and \(b\) are positive integers?