Romanian Mathematical Olympiad 1997 | Classic Number Theory

In this video I go over problem 6 of the 2nd round of the Romanian Mathematical Olympiad that was held in 1997. The problem is quite a classic number theory problem with a simple and nice solution that familiarizes oneself with the most common strategies in olympiad number theory

[anomalous]

looking at other comments ( which are very long and boring to read ) here is a simple summary .
1. gcd ( x, y ) = gcd ( x + y, y )
note that in the problem if
p ^ 2 = a ^ 2 + 2 * b ^ 2
then a < p . and so gcd ( p - a, p + a ) = gcd ( 2 * p, a + p ) = 2 gcd ( p, ( a + p ) / 2 ) = 2. since (a+p )/ 2 < p . and any number less than a prime is co prime to that prime .
this was the main crux of the problem.

[bernat]

What's interesting is that the converse is also true.
Suppose p = a^2+2b^2. Then p^2 = (a^2+2b^2)^2 = (a^2-2b^2)^2 + 2(2ab)^2

This identity is just a form of Brahmagupta's identity for n=2, but can also be proved by simply expanding both sides.

Continuing with this approach, a good idea is to find what is the actual set A = {a^2+2b^2 | a, b \in Z}. It might seem hard at first but if it was instead a^2+b^2 for example, this set is pretty wellknown and it contains all the numbers that do not have any prime of the form 4k+3 with a power of an odd number dividing it. Doing a similar proof with the a^2+2b^2 case, you get that S = all the numbers that do not have any prime of the form 8k+5 or 8k+7 to a power of an odd number dividing it. Sadly this doesn't work neither lol cuz b != 0 ruins it :(

[moonlightcocktail]

My proof was the same, but I want to talk about the method I discovered it.
Earlier I tried to take the modulo of the equation mod some numbers, so at least I knew p and a were odd and b was even.
I looked and found two cases for (a, b, p, c, d) for small p: (1, 2, 3, 1, 1) and (7, 6, 11, 3, 1), where (c, d) is the pair s.t. c^2 + 2d^2 = p.
So something I noticed was that c = b/2 for these examples. I tried to expand p = c^2 + 2d^2 => c^4 + 4c^2d^2 + d^4 = p^2 = a^2 + 2b^2. Of course you shouldn't preassume that c, d already exist, but I did this to see if good forms of c and d in terms of a, b, existed. So first I substituted c = b/2, but there was not a good result there. Somehow I figured out that one of the b^2s is equal to the 4c^2d^2 term, so I found that we could get
c^2 - d^2 = a
2cd = b
as a system of equations of c and d. For such c and d, (c^2 + 2d^2)^2 = a^2 + 2b^2.
In fact we can usually find c and d now from this system of equations by solving a quadratic, it just won't usually be an integer (but somehow, when p is prime, it is!) So I tried to solve for d and got d = sqrt((p + a))/2.
Then I discovered that sqrt(p+a) had to be an integer, except that in the 11 example I discovered it clearly wasn't: 11 + 7 = 18??? This confused me for a while until I realized if (a, b) is a working solution, so is (-a, b). The quadratic from this would give sqrt(p - a)/2, and indeed sqrt(11 - 7)/2 is an integer.
So now I had to prove that p - a or p + a was a square, and since (p - a)(p + a) = 2b^2, it is (by the means shown in the video). I also got a second helpful hint that d^2 | one of p - a or p + a | 2b2, so d | b and as c = b/2d, c is an integer too. So we've found a (c, d) pair generating p from the (a, b) making p^2.
It's funny that this fact was the last I discovered when it's the first thing you should prove when proving the problem statement. In writing the proof I started with this fact instead, but for this scratch work I had the reverse order.
I didn't have the olympiad intuition or knowledge of the trick to solve this at first, but I was eventually able to power through and discover the tactic I was supposed to use. I'm ashamed to say that some of my first attempts were taking mod p, which led nowhere and got me stuck for a while. It's probably not a good sign to overuse the strategies you know.
In the end it was a good problem.

[adrien]

Wow that’s very interesting, actually very classic but beautiful!

[gigagrzybiarz]

Great but gcd means greatest common divisor, not denominator