Unsolved Problems VS Olympiad NT

(Drew here.)

I've spent a lot of time browsing random math pages on Wikipedia (blue link). Sometimes I find things which are actually useful in olympiads, but a lot of the time there's this void of open problems.

Of these open problems, some were only solved recently, and they can be used to blast olympiad problems. An example of this is Catalan's Conjecture (proven by Mihăilescu in 2002), which states that the only solution to $a^x-b^y=1$ in positive integers where $x,y\geq2$ is $3^2-2^3=1$.

Consider the Diophantine equation $$3^x-2^y=1$$ where $x,y$ are positive integers. The intended olympiad way of solving it would be taking $\bmod\,4$ to show that $x$ is even if $y>1$, then rearranging into a difference of squares, then taking $\bmod\,4$ again. But instead one can quote Catalan's Conjecture and move on.

There are other instances of high power theorems being used in solutions, in 2024 alone there was a number theory problem for which the most straightforward solution path was to quote Bertrand's Postulate, and a functional equation which... gets solved with one pair of substitutions followed by quoting Fermat's Last Theorem. (Do I really need a link for this? I'll let you click it anyway :)

But that's not the topic for today; using high-powered theorems like this is not recommended in contests and also not healthy for practice (in some cases it gets you a zero, especially when said high-powered theorem is strictly stronger than the problem you're solving). In that example above, although we should try to avoid using Catalan's Conjecture in our solution, it does tell us that $(x,y)=(1,1)$ and $(x,y)=(2,3)$ are the only solutions to the problem, and tells us that's what we need to prove. Even though Catalan's Conjecture did not make it into our final proof, the knowledge of its statement could help.

In fact, we can leverage unsolved problems in a similar way.

Time travel back to year 2000 when Catalan's Conjecture was not yet Mihăilescu's Theorem, yet the equation $3^x-2^y=1$ still lies in front of us. We cannot use said conjecture to solve the problem, but we can use it to tell us that these should be the only solutions! Otherwise the proposer of this problem would have mysteriously disproven the conjecture, and is asking us to disprove it too.

Examples

The theme of this blogpost is knowing that problems are unsolved or intractable helps us to limit our approaches. It guides us by showing that some methods simply require way too difficult machinery, something that even our state-of-the-art mathematical tools cannot handle (yet). The constraints on our ability also helps to shape NT intuition: we know what is the first thing to try, or not to try.

Other than the final problem (example set 3) and the very first step of 2013 N3 (which I urge you to try!), none of these examples will showcase any significant part of the solution. We will instead see which approaches get debunked by open problems, and what else it prompts us to attempt.

Each of the example sets is self-contained, so feel free to jump around with these links:

Example Set 1 (2008 IMO, on the expression $n^2+1$)

Example Set 2 (2012 N6, on primes with special properties)

Example Set 3 (ELMOSL 2011 N1, on elliptic curves)

Example Set 1

Let's begin with two similar problems:

(2008 IMO) Prove that there are infinitely many positive integers $n$ such that $n^2+1$ has a prime divisor greater than $2n + \sqrt {2n}$.

(2015 CTST) Prove that there exist infinitely many integers $n$ such that $n^2+1$ is squarefree.

Wouldn't it be great if $n^2+1$ was a prime number? It would instantly solve both problems! Of course, but here's where we encounter our first open problem. It is not known if $n^2+1$ takes on infinitely many prime values, and in fact we know no polynomial $P(n)$ of degree at least $2$ which takes on infinitely many prime values. Bummer.

It turns out it is difficult to analyse the prime factors of $n^2+1$ for any one particular value of $n$, and finding ways to circumvent this hurdle forms the core of the two problems stated above.

The infinitude of primes of the form $x^2+1$ is one of Landau's four problems, the other three being Goldbach's conjecture, the twin prime conjecture, and Legendre's conjecture on primes between consecutive squares. All of these have been extensively studied, so naturally there are well-established results that instantly solve the problem. Just for fun here are the much stronger results that have been proven:

(2008 IMO, hyperbuffed edition) Prove that there are infinitely many positive integers $n$ such that $n^2+1$ has a prime divisor greater than $n^{1.2}$.

(2015 CTST, hyperbuffed edition) Prove that there exist infinitely many integers $n$ such that $n^2+1$ is a product of at most two primes.

Since were both the last problem in their respective contest days, people do not bring up these problems much. However, I'll bring our attention to this problem instead:

(2013 N3) Prove that there exist infinitely many positive integers $n$ such that the largest prime divisor of $n^4 + n^2 + 1$ is equal to the largest prime divisor of $(n+1)^4 + (n+1)^2 +1$.

Taking the $\operatorname{gcd}$ of these two polynomials is a natural first step, which leads us to the factorisations $$n^4+n^2+1=(n^2-n+1)(n^2+n+1),\quad (n+1)^4+(n+1)^2+1=(n^2+n+1)(n^2+3n+3).$$

The most common question I have seen from people doing this problem is "Is $n^2+n+1$ prime for infinitely many $n$? If so, then we will be done!" This also (unfortunately) happens to be the most common fakesolve I have seen for this problem. Knowing that this natural question really is an open problem helps to filter out the approaches that will not work, and does additionally save time in contest.

Example Set 2

The next problem I want to showcase is from the 2012 IMO shortlist, and was what inspired me to write this blogpost. It coincidentally appeared in yesterday's National Team problem set!

(2012 N6) Let $x$ and $y$ be positive integers. If ${x^{2^n}}-1$ is divisible by $2^ny+1$ for every positive integer $n$, prove that $x=1$.

We can factorise $x^{2^n}-1=\left(x^{2^{n-1}}+1\right)\left(x^{2^{n-2}}+1\right)\cdots(x^2+1)(x+1)(x-1)$.

If a prime is not $1\pmod 4$, then it cannot divide any of the factors $x^2+1$, $x^4+1$, etc. And if a prime is not $1\pmod 8$, then it cannot divide any of the factors $x^4+1,x^8+1$, etc.

In general, if a prime is not $1\pmod{2^n}$, then it cannot divide any of the factors $x^{2^{n-1}}+1$ and higher.

When trying this problem, my first thought was to then analyse $3\pmod4$ primes: either show that there are infinitely many $3\pmod4$ primes dividing some value of $2^ny+1$, or one of these primes $p$ can attain arbitrarily large values of $\nu_p(2^ny+1)$. This would finish the problem, as all of these primes must divide into $(x+1)(x-1)$ by the question condition, but that is a finite number. And if both of these approaches fail, I would attempt some other larger residue class such as $5\pmod 8$.

Let's focus on the $\nu_p$ approach for now, for any prime $p$, not just $3\pmod4$. The shortlist booklet phrases this well: "For each $x$ and each odd prime $p$ the maximal power of $p$ dividing $x^{2^n} − 1$ for some $n$ is bounded and hence the same must be true for the numbers $2^ny + 1$."

Unfortunately we have to go through some slightly complicated expressions, so I'll express it in words first.

Let $m$ be the maximal $\nu_p$. We can change $2^ny+1$ to $2^{n+\varphi(p^m)}y+1$, while maintaining divisibility by $p^m$. In total, we choose to generate $p$ different numbers this way. When looking at $\bmod\,p^{m+1}$, the number is always a multiple of $p^m$ which limits it to $p$ distinct values, and this is further brought down to only $p-1$ values because $p^{m+1}$ never divides it. By pigeonhole, two of them must be the same $\bmod\,p^{m+1}$, so we can do some more algebraic manipulation to get the result.

Consider the maximal value of $\nu_p(2^ny+1)$, and say $\nu_p(2^ay+1)=m$. Now look at the $p$ numbers of the form $2^{a+t\varphi(p^m)}y+1\equiv r_tp^m\pmod{p^{m+1}}$, for $t=0,1,\dots,p-1$, where $r_t\in\{0,1,\dots,p-1\}$. However, $r_t\neq0$ by maximality of $m$. So, by pigeonhole, there exist distinct $s,t\in\{0,1,\dots,p-1\}$ such that $r_s=r_t$. By comparing the equations, we get $$p^{m+1}\mid2^{(s-t)\varphi(p^m)}-1=2^{(s-t)(p-1)(p^{m-1})}-1.$$

$s-t$ is not divisible by $p$, so by LTE (which is not an open problem), $$m+1\leq\nu_p\left(2^{(s-t)(p-1)(p^{m-1})}-1\right)=\nu_p\left(2^{p-1}-1\right)+\nu_p((s-t)p^{m-1})=\nu_p\left(2^{p-1}-1\right)+m-1$$ and so $p^2\mid 2^{p-1}-1$.

TL;DR suppose there was some other value of $x$ that worked. We can find a value of $y$ such that $\nu_p(2^ny+1)$ is bounded for every prime $p$ dividing some number of that form. Then, when the dust settles, each of these primes satisfies $p^2\mid 2^{p-1}-1$. But humanity only knows two of these Wieferich primes! This is a dead end, which prompts us to try another approach.

I will quote the shortlist booklet again on this: "However trying to reach a contradiction with this conclusion alone seems hopeless, since it is not even known if there are infinitely many primes $p$ without this property."

Another idea would be to consider a large enough prime number $q$, and force it to divide $2^ny+1$. It would be convenient if there just existed an $n$ that made this true - if $2^n$ took on every residue mod $q$, then we could force it to be $-y^{-1}$. But as fate would have it, this path runs head first into another open problem, Artin's conjecture on primitive roots.

Together, these two attempts at analysing individual prime numbers came up short, and as far as I know this problem is impermeable via only those methods. Now it's your turn to find out what works!

Example Set 3

The final problem is from the English Language Master's Open shortlist:

(ELMOSL 2011) Prove that $n^3-n-3$ is not a perfect square for any integer $n$.

This does not tie directly to any unsolved problems, unlike the above examples. Instead, this problem directly asks us to show that a specific elliptic curve has no solutions in the integers.

Elliptic curves are a gigantic subject on their own, forming the basis for the eventual resolution of Fermat's Last Theorem. For one of these to be solvable within olympiad means, there has to be something quite specific about the equation, for example a helpful factorisation or a particular mod that works.

When I tried this problem 4 years ago, I attempted to do some bounding: is $n^3-n-3$ never close to a perfect square, because this works when it is an even degree polynomial in $n$? But this is a trick that fails to deal with elliptic curves; when the degrees of variables are coprime, olympiad methods are unable to construct useful bounds.

What exactly goes wrong, you may ask? Apparently $n^3-n+4=m^2$ has solutions, which is not too far away from the original equation. Not only is $0^3-0+4=2^2$, but also $15^3-15+4=58^2$, and $4064^3-4064+4=67121410084=259078^2$... which is the largest out of seven solutions.

A bit further is $n^3-n+9=m^2$, where the largest solution evaluates to a $16$ digit number. So, yes, to me 4 years ago, it seems that bounding elliptic curves isn't the best idea.

Back to small integer values we go. An example of a modular contradiction is for the equation $n^3-n+2=m^2$. When taking $\bmod\,3$, the LHS can only take on the value $2$, which is the only value which is not a square $\bmod\,3$.

However, none of these seem to entirely work on our ELMOSL problem. The best option seems to be $\bmod\,8$, which limits $n\equiv4\pmod8$. Out of options, we turn to factorisation for help.

The factorisation that ends up being helpful is the unusual $(n+2)(n^2-2n+3)=m^2+9$. The sum of two squares has made its return for the third time in this post, and this time it restricts the possible prime factors of the LHS to $1\pmod4$ apart from $2$ and $\sqrt{9}=3$, which is great considering that the LHS is already partially factorised!

Using our knowledge of $n\equiv4\pmod8$, we have $n^2-2n+3\equiv3\pmod4$ and $\frac{n+2}{2}\equiv3\pmod4$. Both of these signal trouble: the only $3\pmod4$ prime factor available is $3$. And therefore, $3$ must divide both of the factors, which forces $3\mid n+2$, which makes $3\nmid n^2-2n+3$ contradiction.

Upon closer inspection, the reason why this works while there are still solutions to the equation $\bmod\,9$ or $\bmod\,27$, is that $3$ was not the only prime in play. We were able to get rid of the influence of all other $3\bmod\,4$ prime factors using the magical factorisation, and pave the way for $3$ to make its final stand.

Concluding Remarks

In this post, we have explored the limitations of our mathematical abilities. Honestly, it's surprising to me that so many olympiad problems border unsolved problems, and the wrong rabbitholes that appear in olympiad NT can often be related to these problems.

The knowledge and intuition I have gained from these open problems is hard to state, since I am only seeing this perspective looking back on my contestant years. Maybe there were a couple of times that I was guided by these ideas, 2022 N6 comes to mind. Maybe my time on Wikipedia might not have been wasted after all.

FErmat's Last Theorem can rest after solving that FE; we now await the day that someone will prove that $n^2+1$ is prime infinitely often, and put to rest that IMO problem which may be hundreds of years old by then.