Problems
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!).
Prime numbers are like atoms that build every integer number. That is, a prime decomposition of a number is unique and then we can use it to find the number’s factors. Today we will explore this idea a bit more.
We will introduce a couple of new terms. First, a common divisor of two numbers is simply a number that both of these numbers can be divided by. Two numbers which have no common divisors (except from 1) are called relatively prime. We can establish if two numbers are relatively prime by looking at their prime factorizations - if they share no common primes, then they cannot share a common divisor!
Out of all the common divisors two numbers have, one must be the largest. This is an important number and is called the Greatest Common Divisor (GCD). You can find it by looking at the prime factorizations of the two numbers. For every prime number appearing in both factorizations, we take the smaller power. Then we multiply all our choices together. If we divide both numbers by their GCD, the resulting numbers will have no common divisors left and so will be relatively prime.
Similar to the notion of a common divisor is the one of common multiple. It is simply a number that is divisible by both numbers. Among the common multiples, one must be the smallest – this is called the Least Common Multiple (LCM). Again, the LCM can be found by looking at the prime factorizations of the two numbers. For every prime number appearing in any of the two factorizations, we take the larger power. Then we multiply all our choices together.
Cut a packet of 4 cards. Is any of the cards in the same place as it was before?
We have a packet 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 interchange 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?
[Needs editing]
Previously, we have explored how to tile the plane using rectangles, but a much more fascinating topic is plane tilings with more intricate shapes such as quadrilaterals, pentagons, and even more unconventional shapes like chickens.
In this exercise sheet, we define a plane tiling as a covering of the entire plane, without any gaps or overlaps, using identical geometric shapes that can be rotated and symmetrical to each other. Usually, it is sufficient to cover a small portion of the plane with a particular pattern that can be extended to cover the entire plane.
While living on the uninhabited island, Robinson Crusoe missed terribly having a proper floor in his hut. He wanted his floor to not be some simple hard floor, but a proper tile floor he used to have in his house. He missed his house with the tile floor so much, that finally he decided to make one by himself.
He made a huge number of \(1\times2\) tiles, and studied how he could tile a floor in a rectan- gular room if no tile can overlap the other. It was easy for him to tile the floor in a \(6\times8\) room.
He also noticed that if floor in a room of size \(p\times q\) is tiled with his \(1\times2\) tiles then \(pq\) is even (can you explain why?). The reverse is also true, i.e. if \(pq\) is even, then the floor can be tiled with \(1\times2\) tiles in a similar way to the picture above.
This tiling can be cut from one side to another by a grid line without splitting any tiles. Such constructions are impractical, this type of floor can easily become uneven. That’s why in practise irreducible tilings are used.
A tiling of a rectangle by small identical rectangles (tiles) is called irreducible, if any straight cut from one side of the big rectangle to another goes across at least one of the tiles. Robinson decided to use irreducible tilings. Help him to figure out how to tile a rectan- gular floor.
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?