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!).
Cut a deck of \(4\) cards. Are any of the cards in the same place as they were before?
We have a deck of \(13\) cards from Ace to King. Let Ace be the first card, \(2\) the second card and so on with King being the thirteenth card. How can you swap \(4\) and \(7\) (and leave all other cards where they are) by only switching adjacent pairs of cards?
How many permutations of 13 cards leaves the third card where it started?
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.
Let \(m\) and \(n\) be positive integers. What positive integers can be written as \(m+n+\gcd(m,n)+\text{lcm}(m,n)\), for some \(m\) and \(n\)?
Suppose that \(n\) is a natural number and \(p\) is a prime number. How many numbers are there less than \(p^n\) that are relatively prime to \(p^n\)?
Let \(n\) be a positive integer. We denote by \(s(n)\) the sum of the divisors of \(n\). For example, the divisors of \(n=6\) are \(1\), \(2\), \(3\) and \(6\), so \(s(6)=1+2+3+6=12\). Prove that, for all \(n\ge1\), \[\sum_{k=1}^ns(k)=s(1)+s(2)+...+s(n)\le\frac{\pi^2}{12}n^2+\frac{n\log n}{2}+\frac{n}{2}.\]
Consider a line segment of length \(3m\). Jack chose \(4\) random points on the segment and measured all the distances between those \(4\) points. Prove that at least one of the distances is less than or equal to \(1m\).