Trio of theorems in number theory for olympiads

This is part of a series of articles based on my high school research paper from 2021 covering nonstandard approaches to solving olympiad problems. The problems from the Latvian Open Mathematics Olympiad mentioned in the article can be found in the LU NMS archive.

As the final entry in this series of articles, we’ll examine a collection of number theory ideas. These three ideas are not particularly interconnected with each other, but each of them is quite short, so we’ll examine all of them at once. After that, we’ll use each theorem in an olympiad problem, thereby learning when each theorem could be useful.

Theorems

Sum of two squares theorem

The first theorem determines when a number can be expressed as the sum of two squared numbers.

A positive integer $n$ can be written as a sum of two squares if and only if each prime factor of $n$, where the remainder of the prime when dividing by $3$ is $4,$ has an even exponent.

For simplicity, in this article we’ll call these prime factors (with bases $3, 7, 11, 15$ and so on) special prime factors. This is an invented term that would need to be explained if used in a contest.

For example, the number $22=2^1\cdot11^1$ cannot be expressed as the sum of two squares, because $11^1$ is a special prime factor with an odd exponent. Meanwhile, $242=2^1\cdot11^2$ can be expressed as the sum of two squares, because the only special prime factor is $11^2,$ and its exponent is even. Moreover, in this case we can immediately see the sum: $242=11^2+11^2.$

“If and only if” means that this also works in the other direction. For example, the special prime factors in the number $3^2+6^2$ must all have even exponents. And indeed, $3^2+6^2=45=3^2\cdot5.$

Euler’s theorem

The second theorem is also related to prime numbers and exponents. It is Euler’s theorem.

If the greatest common divisor of $a$ and $n$ is 1, then $a^{\phi(n)}-1$ is divisible by $n,$ where \[\phi(n)=n(1-\frac1{p_1})(1-\frac1{p_2})\ldots(1-\frac1{p_k})\] and $p_1,p_2,\ldots,p_k$ are all the prime numbers that divide $n.$

For example, consider $a=2$ and $n=45=3^2\cdot5.$ We can see that $\gcd(2,45)=1,$ so we can use the theorem. First, we obtain \[\phi(45)=45(1-\frac13)(1-\frac15)=45\cdot\frac23\cdot\frac45=30\cdot\frac45=24.\] It follows that $2^{24}-1$ is divisible by $45.$ We have very concisely proven this difficult statement.

Legendre’s formula

Finally, Legendre’s formula will tell us something about the factorial of $n$, which is $n!=1\cdot2\cdot3\cdot\ldots\cdot n.$

The highest power of a prime $p$ that divides $n!$ is \[\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots.\]

The unusual brackets $\lfloor\,\rfloor$ denote rounding down. This means that this infinite sum is actually finite, because once the powers of $p$ exceed $n,$ all remaining terms are equal to $0.$

For example, if $p=2$ and $n=30,$ then \begin{aligned} \left\lfloor\frac{30}{2}\right\rfloor&=\lfloor15\rfloor=15&\, \\ \left\lfloor\frac{30}{2^2}\right\rfloor&=\lfloor7.5\rfloor=7&\, \\ \left\lfloor\frac{30}{2^3}\right\rfloor&=\lfloor3.75\rfloor=3&\, \\ \left\lfloor\frac{30}{2^4}\right\rfloor&=\lfloor1.875\rfloor=1&\, \\ \left\lfloor\frac{30}{2^5}\right\rfloor&=\lfloor0.9375\rfloor=0&\, \end{aligned} and all the subsequent terms will also be $0.$ The sum is $26,$ so $30!$ is divisible by $2^{26},$ but not $2^{27}.$

Olympiad examples

Sum of two squares theorem

Latvian Open Mathematics Olympiad 2015/2016, Form 10, Problem 3.
Four consecutive terms of an arithmetic progression are integers $A$, $B$, $C$, and $D$. Prove that $A^{2} +2B^{2} +3C^{2} +4D^{2}$ can be expressed as the sum of the squares of two integers!

Since we have an arithmetic progression, we may introduce $B=A+d,C=A+2d,D=A+3d.$ Then, \begin{aligned} &\,A^2+2B^2+3C^2+4D^2 \\ =&\,A^2+2(A+d)^2+3(A+2d)^2+4(A+3d)^2 \\ =&\,10A^2+40Ad+50d^2 \\ =&\,10(A^2+4Ad+5d^2) \\ =&\,10((A+2d)^2+d^2). \end{aligned} By the sum of two squares theorem, the special prime factors of the number $(A+2d)^2+d^2$ have even exponents. When we multiply this number by $10=2\cdot5,$ the special prime factors don’t change, because neither $2$ nor $5$ has a remainder of $3$ when divided by $4$.

Therefore, the special prime factors of the number $10((A+2d)^2+d^2)$ also all have even exponents, and the sum of two squares theorem tells us that this number can be expressed as the sum of two squares, which is what we needed to prove.

This problem doesn’t ask us to write down how to express $A^2+2B^2+3C^2+4D^2$ as the sum of two squares, but only to prove that it is possible to do so. Hence, this solution is completely sufficient!

Euler’s theorem

Latvian Open Mathematics Olympiad 2017/2018, Form 10, Problem 4.
Prove that if $x$ is a natural number, then $x^8-x^2$ is divisible by $252.$

I’ve tried to avoid congruences in this article, but writing this solution without them is much more difficult. For those not familiar with congruences, I recommend studying the theory online; Latvian speakers can do so on uzdevumi.lv. Congruences are quite intuitive, and they are very important in number theory problems, so it’s worth becoming familiar with them either way.

First, we make two observations:

• Since $252=2^2\cdot3^2\cdot7,$ it suffices to prove that $x^8-x^2$ is divisible by 4, by 7, and by 9.
• Since $x^8-x^2=x^2(x^6-1),$ to prove divisibility by $m,$ it suffices to show that either $x^2$ is divisible by $m$ or $x^6-1$ is divisible by $m,$ that is, $x^2\equiv 0\pmod m$ or $x^6\equiv 1\pmod m.$

Then, divisibility by 4 can be justified using a table:

If…	Then…
$x\equiv0\pmod4$	$x^2\equiv0^2\equiv0\pmod 4$
$x\equiv1\pmod4$	$x^6\equiv1^2\equiv1\pmod 4$
$x\equiv2\pmod4$	$x^2\equiv2^2\equiv4\equiv0\pmod 4$
$x\equiv3\pmod4$	$x^6\equiv3^6\equiv(-1)^6\equiv1\pmod 4$

For divisibility by $7$, we consider two cases:

• If $\gcd(x,7)=1,$ then $\phi(7)=7(1-\frac1{7})=7\cdot\frac67=6$ and $x^6-1$ is divisible by $7$ by Euler’s theorem.
• If $\gcd(x,7)\neq1,$ then $x$ is divisible by $7.$ From $x \equiv 0\pmod 7$ it follows that $x^2\equiv 0\pmod 7.$

Finally, for divisibility by $9$, we also consider two cases:

• If $\gcd(x,9)=1,$ then $\phi(9)=9(1-\frac1{3})=9\cdot\frac23=6$ and $x^6-1$ is divisible by $9$ by Euler’s theorem.
• If $\gcd(x,9)\neq1,$ then $x$ is certainly divisible by $3.$ Setting $x=3k,$ we obtain $x^2=(3k)^2=9k^2,$ so $x^2\equiv0\pmod9.$

Legendre’s formula

Latvian Open Mathematics Olympiad 2018/2019, Form 12, Problem 4.
There are 100 students at a sports camp. Let $N$ denote the number of ways these 100 students can be divided into 50 pairs (the order of the pairs does not matter, nor does the order of the students within each pair). By what highest power of $3$ is the number $N$ divisible?

There are $100!$ ways to arrange students in a row. Then, we can call the first two students pair #1, the next two students pair #2, and so on up to pair #50.

However, since the order of pairs and the order of students within each pair don’t matter, we need to correct this result by dividing by $50!$ and $2^{50}$ respectively. We obtain $N=\dfrac{100!}{50!\cdot2^{50}}.$

By Legendre’s formula, the highest power of 3 that divides $100!$ is \[\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor=33+11+3+1=48\] and the highest power of 3 that divides $50!$ is \[\left\lfloor\frac{50}{3}\right\rfloor+\left\lfloor\frac{50}{9}\right\rfloor+\left\lfloor\frac{50}{27}\right\rfloor=16+5+1=22.\]

Therefore, we can express $100!$ and $50!$ as $3^{48}\cdot r$ and $3^{22}\cdot s$ respectively, where it is guaranteed that $r$ and $s$ are not divisible by $3.$ Then, \[N=\dfrac{3^{48}\cdot r}{3^{22}\cdot s\cdot2^{50}}=3^{26}\cdot\frac{r}{s\cdot2^{50}}.\] The fraction $\dfrac{r}{s\cdot2^{50}}$ is not divisible by $3,$ so the highest power of 3 that divides $N$ is $26.$

Final thoughts

Of these three theorems, Euler’s theorem is the most widely encountered, because it is possible to create difficult problems where its usefulness is not immediately obvious. With the sum of two squares theorem or Legendre’s formula, it’s more difficult to achieve that - as we saw in the problems, they explicitly mentioned either the sum of two squares or the highest power of a divisor, which immediately gives away that the respective theorems could be useful.

Therefore, I definitely recommend exploring more problems specifically about congruences and Euler’s theorem. I wish you the best of luck solving number theory problems!