Maths Olympiad Prep

Library / /26 of 38

Number theory Difficulty 7.0 National olympiad Prove it China

Suppose positive integers mm, nn, kk satisfy mn=k2+k+3mn = k^2 + k + 3. Prove that at least one of the following Diophantine equations
x2+11y2=4m and x2+11y2=4n x^2 + 11y^2 = 4m \text{ and } x^2 + 11y^2 = 4n
has a solution (x,y)(x, y) with xx, yy being odd numbers.

Solution

First, we prove a lemma.

Lemma The following Diophantine equation
x2+11y2=4m x^2 + 11y^2 = 4m
has a solution (x0,y0)(x_0, y_0), such that either x0x_0, y0y_0 are odd numbers or x0x_0, y0y_0 are even numbers with x0(2k+1)y0(modm)x_0 \equiv (2k+1)y_0 \pmod m.

Consider the expression x+(2k+1)yx + (2k+1)y, where xx, yy are integers, and 0x2m0 \le x \le 2\sqrt{m}, 0ym20 \le y \le \frac{\sqrt{m}}{2}.

There are ([2m]+1)m2+1m([2\sqrt{m}]+1)\left\lfloor\frac{\sqrt{m}}{2}\right\rfloor+1 \ge m such expressions. So there exist integers x1x_1, x2[0,2m]x_2 \in [0, 2\sqrt{m}], y1y_1, y2[0,m2]y_2 \in [0, \frac{\sqrt{m}}{2}], such that (x1,y1)(x2,y2)(x_1, y_1) \ne (x_2, y_2), and
x1+(2k+1)y1x2+(2k+1)y2(modm), x_1 + (2k+1)y_1 \equiv x_2 + (2k+1)y_2 \pmod m,
So
x(2k+1)y(modm),wherex=x1x2, y=y2y1. x \equiv (2k+1)y \pmod m, \quad \text{where} \quad x = x_1 - x_2, \ y = y_2 - y_1.
This means
x2(2k+1)2y211y2(modm), x^2 \equiv (2k+1)^2 y^2 \equiv -11y^2 \pmod m,
that is, x2+11y2=tmx^2 + 11y^2 = tm for some integer tt.
Since x2m|x| \le 2\sqrt{m}, ym2|y| \le \frac{\sqrt{m}}{2}, we have
x2+11y2<4m+114m<7m. x^2 + 11y^2 < 4m + \frac{11}{4}m < 7m.
So 1t61 \le t \le 6.
As mm is an odd number, obviously the equations x2+11y2=2mx^2 + 11y^2 = 2m, and x2+11y2=6mx^2 + 11y^2 = 6m have no integer solution.

(1) If x2+11y2=mx^2 + 11y^2 = m, then x0=2xx_0 = 2x, y0=2yy_0 = 2y is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.

(2) If x2+11y2=4mx^2 + 11y^2 = 4m, then x0=xx_0 = x, y0=yy_0 = y is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.

(3) If x2+11y2=3mx^2 + 11y^2 = 3m, then (x±11y)2+11(xy)2=94m(x \pm 11y)^2 + 11(x \mp y)^2 = 9 \cdot 4m.
First, assume that 3m3 \mid m. If x≢0(mod3)x \not\equiv 0 \pmod{3}, y≢0(mod3)y \not\equiv 0 \pmod{3}, and x≢y(mod3)x \not\equiv y \pmod{3}, then
x0=x11y3,y0=x+y3 x_0 = \frac{x - 11y}{3}, \quad y_0 = \frac{x + y}{3}
is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.
If xy≢0(mod3)x \equiv y \not\equiv 0 \pmod{3}, then
x0=x+11y3,y0=yx3 x_0 = \frac{x + 11y}{3}, \quad y_0 = \frac{y - x}{3}
is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.
Now suppose 3m3 \mid m. Then the above are still integer solutions. If x2+11y2=4mx^2 + 11y^2 = 4m has an even integer solution x0=2x1x_0 = 2x_1, y0=2y1y_0 = 2y_1, then
x12+11y12=m36m=(5x1±11y1)2+11(5y1x1)2. x_1^2 + 11y_1^2 = m \Leftrightarrow 36m = (5x_1 \pm 11y_1)^2 + 11(5y_1 \mp x_1)^2.
Since one of x1x_1, y1y_1 is even and the other is odd, so 5x1±11y15x_1 \pm 11y_1, 5y1x15y_1 \mp x_1 are odd numbers.
If x1y1(mod3)x_1 \equiv y_1 \pmod{3}, then x0=5x111y13x_0 = \frac{5x_1 - 11y_1}{3}, y0=5y1+x13y_0 = \frac{5y_1 + x_1}{3} is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.
If x1≢y1(mod3)x_1 \not\equiv y_1 \pmod{3}, then x0=5x1+11y13x_0 = \frac{5x_1 + 11y_1}{3}, y0=5y1x13y_0 = \frac{5y_1 - x_1}{3} is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.

(4) If x2+11y2=5mx^2 + 11y^2 = 5m, then 254m=(3x11y)2+11(3y±x)225 \cdot 4m = (3x \mp 11y)^2 + 11(3y \pm x)^2.
When 5m5 \nmid m, if
x±1(mod5),y2(mod5),or x±2(mod5),y±1(mod5), x \equiv \pm 1 \pmod{5}, \quad y \equiv \mp 2 \pmod{5}, \quad \text{or } x \equiv \pm 2 \pmod{5}, \quad y \equiv \pm 1 \pmod{5},
then
x0=3x11y5,y0=3y+x5 x_0 = \frac{3x - 11y}{5}, \quad y_0 = \frac{3y + x}{5}
is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.
If x±1(mod5)x \equiv \pm 1 \pmod{5}, y±2(mod5)y \equiv \pm 2 \pmod{5}, or x±2(mod5)x \equiv \pm 2 \pmod{5}, y1(mod5)y \equiv \mp 1 \pmod{5}, then
x0=3x+11y5,y0=3yx5 x_0 = \frac{3x + 11y}{5}, \quad y_0 = \frac{3y - x}{5}
is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.

When 5m5 \mid m, then the above are still integer solutions. If x2+11y2=4mx^2 + 11y^2 = 4m has an even integer solution x0=2x1x_0 = 2x_1, y0=2y1y_0 = 2y_1, then
x12+11y12=m,x1≢y1(mod2), x_1^2 + 11y_1^2 = m, \quad x_1 \not\equiv y_1 \pmod 2,
and we have 100m=(x133y1)2+11(y1±3x1)2100m = (x_1 \mp 33y_1)^2 + 11(y_1 \pm 3x_1)^2.
If x1y10(mod5)x_1 \equiv y_1 \equiv 0 \pmod{5}, or x1±1(mod5)x_1 \equiv \pm 1 \pmod{5}, y1±2(mod5)y_1 \equiv \pm 2 \pmod{5}, or
x1±2(mod5),y11(mod5), x_1 \equiv \pm 2 \pmod{5}, \quad y_1 \equiv \mp 1 \pmod{5},
then x0=x133y15x_0 = \frac{x_1 - 33y_1}{5}, y0=y1+3x15y_0 = \frac{y_1 + 3x_1}{5} is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.
If x1±1(mod5)x_1 \equiv \pm 1 \pmod{5}, y12(mod5)y_1 \equiv \mp 2 \pmod{5}, or x1±2(mod5)x_1 \equiv \pm 2 \pmod{5}, y1±1(mod5)y_1 \equiv \pm 1 \pmod{5}, then
x0=x1+33y15,y0=y133x15 x_0 = \frac{x_1 + 33y_1}{5}, \quad y_0 = \frac{y_1 - 33x_1}{5}
is a solution of x2+11y2=4mx^2 + 11y^2 = 4m satisfying the lemma.

The lemma is proved.

From the lemma, if x2+11y2=4mx^2 + 11y^2 = 4m has a solution (x,y)(x, y) with xx, yy being odd numbers, then it has a solution (x0,y0)(x_0, y_0) with x0x_0, y0y_0 being even numbers satisfying x0(2k+1)y0(modm)x_0 \equiv (2k+1)y_0 \pmod m.

Let l=2k+1l = 2k + 1, the solution of the quadratic equation
mx2+ly0x+ny021=0 mx^2 + ly_0x + ny_0^2 - 1 = 0
is
x=ly0±l2y024mny02+4m2m=ly0±x02m. x = \frac{-ly_0 \pm \sqrt{l^2 y_0^2 - 4mny_0^2 + 4m}}{2m} = \frac{-ly_0 \pm x_0}{2m}.
So the equation
mx12+ly0x1+ny021=0 mx_1^2 + ly_0x_1 + ny_0^2 - 1 = 0
has at least an integer solution x1x_1, i.e.
mx12+ly0x1+ny021=0. mx_1^2 + ly_0x_1 + ny_0^2 - 1 = 0.
This indicates that x1x_1 is an odd number. Now, from this equation, it follows that
(2ny0+lx1)2+11x12=4n. (2ny_0 + lx_1)^2 + 11x_1^2 = 4n.
This means x2+11y2=4nx^2 + 11y^2 = 4n has a solution (x,y)(x, y) with xx, yy being odd numbers, where x=2ny0+lx1x = 2ny_0 + lx_1, y=x1y = x_1.

Therefore, at least one of the equations x2+11y2=4mx^2 + 11y^2 = 4m or x2+11y2=4nx^2 + 11y^2 = 4n has a solution (x,y)(x, y) with xx, yy odd.

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.