Problems

Let \(\phi(n)\) be Euler’s function. Namely \(\phi(n)\) counts how many integers from \(1\) to \(n\) inclusive are coprime with \(n\). For two natural numbers \(m\), \(n\) such that \(\gcd(m,n)=1\), prove that \(\phi(mn) = \phi(m)\phi(n)\).

A natural number \(N\) is called perfect if it equals the sum of its divisors, except for \(N\) itself. Prove that if \(2^r-1\) is prime, then \((2^r-1)2^{r-1}\) is a perfect number. Are there any odd perfect numbers?

We want to prove Monsky’s theorem as a corollary of Sperner’s lemma: it is not possible to dissect a square into an odd number of triangles of equal area. After scaling we can consider the square with coordinates: \((0,0),(0,1),(1,0),(1,1)\), which we want to cut into \(n\) triangles with area \(\frac{1}{n}\) each for an odd \(n\). Consider the following coloring of all the points with rational coordinates \((\frac{p}{q},\frac{r}{s})\) inside the square:
We look at the powers of \(2\) in the fractions \((\frac{p}{q},\frac{r}{s})\), first of all the numbers \(p,q\) are coprime, and thus only one of them is divisible by \(2\), same with \(r,s\). Then the following possibilities might occur:

1. Neither \(q\) nor \(s\) is divisible by \(2\). In this case we color the point red.

2. \(\frac{r}{s}\) is divisible by a larger or equal power of \(2\) than \(\frac{p}{q}\) and \(p\) is not divisible by \(2\). In this case we color the point blue.

3. \(\frac{p}{q}\) is divisible by a strictly larger power of \(2\) than \(\frac{r}{s}\) and \(r\) is not divisible by \(2\). In this case we color the point green.

Under an assumption (which you do not have to prove) that the area of any rainbow triangle is at least \(\frac{1}{2}\) prove the Monsky’s theorem.