Maths Olympiad Prep

Library / /21 of 69

Number theory Difficulty 5.7 AIME, harder Prove it Mongolia

Let NN be an arbitrary integer. Prove that the equation
(m+n)2+mn+1=N(m+n) (m+n)^2 + mn + 1 = N(m+n)
has infinitely many integer (m,n)(m, n) solutions.
(Otgonbayar Uuye)

Solution

Let s=m+ns = m + n and p=mnp = mn. Then the equation becomes:
s2+p+1=Ns s^2 + p + 1 = N s
So,
p=Nss21 p = N s - s^2 - 1
Recall that mm and nn are roots of the quadratic equation x2sx+p=0x^2 - s x + p = 0.

The discriminant is:
D=s24p=s24(Nss21)=s24Ns+4s2+4 D = s^2 - 4p = s^2 - 4(N s - s^2 - 1) = s^2 - 4N s + 4s^2 + 4
=5s24Ns+4 = 5s^2 - 4N s + 4
For mm and nn to be integers, DD must be a perfect square.

Let D=t2D = t^2 for some integer tt.
So,
5s24Ns+4=t2 5s^2 - 4N s + 4 = t^2
This is a quadratic in ss for each integer tt.

For each integer tt, the equation
5s24Ns+4t2=0 5s^2 - 4N s + 4 - t^2 = 0
has discriminant in ss:
Δ=(4N)245(4t2)=16N220(4t2)=16N280+20t2 \Delta = (4N)^2 - 4 \cdot 5 \cdot (4 - t^2) = 16N^2 - 20(4 - t^2) = 16N^2 - 80 + 20 t^2
For sufficiently large t|t|, this is positive, so there are integer solutions for ss for infinitely many tt.

Alternatively, fix ss to be any integer, then p=Nss21p = N s - s^2 - 1 is also integer, and mm and nn are roots of x2sx+p=0x^2 - s x + p = 0.

The roots are
m,n=s±s24p2 m, n = \frac{s \pm \sqrt{s^2 - 4p}}{2}
So s24ps^2 - 4p must be a perfect square.
But s24p=s24(Nss21)=5s24Ns+4s^2 - 4p = s^2 - 4(N s - s^2 - 1) = 5s^2 - 4N s + 4

So for each ss such that 5s24Ns+45s^2 - 4N s + 4 is a perfect square, we get integer solutions.

But for each kk, let ss be such that 5s24Ns+4=k25s^2 - 4N s + 4 = k^2 for some integer kk.
This is a quadratic in ss:
5s24Ns+4k2=0 5s^2 - 4N s + 4 - k^2 = 0
For each integer kk, this quadratic has integer solutions for ss for infinitely many kk.

Therefore, there are infinitely many integer solutions (m,n)(m, n) to the given equation for any integer NN.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.