Not-so-elementary number theory

I’ve had a longtime interest in the realm of contest mathematics to the extent that I think that it’s probably a bit unhealthy. I learned about it too little too late, having only heard about the olympiad contests for the first time when I was just graduating from high school. Ever since making that discovery, I’ve had a passive interest in becoming better at contest math, even though I’ll never actually be able to do any of the contests.

Elaborating on my relationship with the olympiad community is probably something that’s worthy of its own separate blog post, but the short story is that due to complications and other waxing and waning interests, I always find myself teetering along the edge of the community, always having the inclination to dive right into it but never having the time or the raw motivation to actually do so. Instead of spending a long stretch of dedicated time to getting better, I end up learning more about the tools and the questions in procedural batches, collecting important concepts bit by bit as I go along.

I recently learned some number theory in college, so I figured, why not try my hand at some of the number theory problems that the contest math community likes to ask? After searching around, I found this document from the Art Of Problem Solving website: a collection of number theory problems written up by a few of its members. So, I decided to start looking through it, starting at the beginning and seeing how far I could go until I hit a problem that stumped me.

It immediately became clear that that this strategy wasn’t going to work.

See, the thing about a lot of problem-solving mathematics is that it has a lot of bags of tricks that you need to familiarize yourself with. And I don’t just mean in the jovial “here are a million different theorems that will be useful to you” sense, although that’s certainly a large part of it. I also mean in the sense of how to actually solve the problems. There are techniques as well as theorems: there’s infinite descent, and proof by induction, and a slightly more nuanced form of proof-by-contradiction, and the whole issue of finding out what approaches, techniques, and tools are relevant, plus finding out what sorts of things need to be ironed out if the approach you’re interested in taking is somewhat unorthodox, etc. This is why even the intermediate level olympiad problems are incredibly intimidating to someone who’s not familiar with the contest math community—even if they have something flashy like a Master’s or a PhD.

I realized that these were advanced level problems that I wouldn’t be able to solve on my own when I spotted question A3 in this document. A3 was problem 6 from the 1988 IMO.

Now, I just want to make a thing or two clear here before showing the problem. To those of you who are unaware, the IMO is effectively the hardest of the olympiad tests. In the USA, in order to qualify for the IMO, you need to do well on the USAMO, which to qualify for requires doing well on the AIME, which to qualify for requires doing well on the AMC, which still has some pretty hard problems near the end of it!

Oh, and problem 6 on the IMO is usually the hardest question on the test.

Oh, and this specific problem 6 was so hard that none of the mathematicians who oversaw the IMO were able to solve it on their own.

I am not quite at the level where I can easily solve any IMO problems without help. I’m getting there, but it’ll take some time.

Before deciding to put away this document of devilish number theory problems, I decided that I’d try and find a solution to this question that made sense to me. There’s a big difference between coming up with a solution on your own and being able to understand a solution that someone presents. Some of the solutions to IMO problems absolutely go over my head. But this question’s solution actually didn’t. It’s actually pretty straightforward! Straightforward enough that I bet I can explain it here.

Problem: Let ${ a}$ and ${ b}$ be positive integers such that ${ ab+1}$ divides ${ a^2 + b^2}$ . Show that

$\displaystyle \frac{a^2+b^2}{ab+1}$

is the square of an integer.

Solution: First, let’s try and parse out what this is even saying. We’ve got positive integers ${ a}$ and ${ b}$ . Whenever

$\displaystyle \frac{a^2+b^2}{ab+1}$

is an integer, we want to show that it is also a perfect square.

Alright, that sounds like a job for proof-by-contradiction. We’ll assume that there are two positive integers that satisfy

$\displaystyle \frac{a^2+b^2}{ab+1}=k$

where ${ k}$ is an integer but not a perfect square.

This is the proposition that we’re ultimately going to be contradicting, but we need to do it by proxy of another assumption. If you’ve ever seen the proof that ${ \sqrt{2}}$ is irrational, then this line of attack may look familiar.

If our equation has any solutions, then there must be one or more solutions that minimize their sum. In other words, suppose ${ S}$ is the set of ordered pairs of positive integers ${ (a,b)}$ that satisfy

$\displaystyle \frac{a^2+b^2}{ab+1}=k.$

If ${ S}$ is non-empty, then we can we can find a solution ${ (A,B) \in S}$ such that ${ A + B}$ is minimized. Thus, if we contradict the minimality of ${ A+B}$ by finding a solution whose sum must be smaller, then that proves that ${ S}$ is empty, which is precisely what we want.

So let’s assume that ${ A+B}$ is minimized for our solution here. Furthermore, let’s assume that ${A\geq B}$ . The first thing we can do is multiply both sides by the denominator and get everything on one side to get

$\displaystyle A^2 - ABk + B^2 - k = 0.$

The clever bit here now is to replace ${ A}$ with a variable ${ x}$ . We can instead consider the quadratic equation

${ x^2 - (Bk)x + (B^2 - k) = 0.}$

This quadratic equation has two roots. One of them, as we saw previously, is ${ A}$ . Suppose the other one is ${ x_1}$ . Note that ${ (x_1, B)\in S}$ as well, or that if ${(A,B)}$ is a solution to

$\displaystyle \frac{a^2+b^2}{ab+1}=k$

then ${ (x_1,B)}$ is a solution as well. So, if we can show that ${ x_1}$ is a positive integer that is less than ${ A}$ , then we will have a solution whose sum is less than ${A+B}$ , thus demonstrating what we want to show.

We can affirm that this is indeed the case with the help of Vieta’s Formulas. In this case, we’ll just highlight that ${ (x-a)(x-b) = x^2 - (a+b)x + ab}$ , or that the coefficient of the ${ x}$ term is the negative of the sum of the roots, while the constant term is the product of the roots. From this we gather that

$\displaystyle x_1 + A = Bk \implies x_1 = Bk - A,$

$\displaystyle x_1 \cdot A = B^2 - k \implies x_1 = \frac{B^2 - k}{A}.$

Since ${ x_1 = Bk - A}$ , it follows that ${ x_1}$ is an integer. Since ${ k > 0}$ , and since ${ (x_1,B)\in S}$ , we have

$\displaystyle \frac{x_1^2+B^2}{x_1B+1}=k>0$

which forces ${ x_1 \geq 0}$ , or else the denominator would be negative while the numerator was positive.

Since ${ B\leq A}$ , it follows that ${ B^2 - k < A^2}$ . Divide both sides by ${ A}$ and you get

$\displaystyle x_1 = \frac{B^2 - k}{A}<A$

and so ${ x_1 < A}$ .

So, to recap, ${ x_1}$ is a non-negative integer less than ${ A}$ . All we need now is to show that ${ x_1 \neq 0}$ . This is where our assumption that ${ k}$ is not a perfect square comes into play. Recall that

$\displaystyle x_1 = \frac{B^2 - k}{A}.$

For ${ x_1}$ to be ${ 0}$ , we would need ${ B^2 - k = 0}$ , or that ${ k = B^2}$ . But since ${ k}$ isn’t a perfect square, this doesn’t happen. Hence, ${ x_1 \neq 0.}$ ${\square}$