Number theoryDifficulty 7.0National olympiadProve itChina
Suppose positive integers m, n, k satisfy mn=k2+k+3. Prove that at least one of the following Diophantine equations x2+11y2=4m and x2+11y2=4n has a solution (x,y) with x, y being odd numbers.
Solution
First, we prove a lemma.
Lemma The following Diophantine equation x2+11y2=4m has a solution (x0,y0), such that either x0, y0 are odd numbers or x0, y0 are even numbers with x0≡(2k+1)y0(modm).
Consider the expression x+(2k+1)y, where x, y are integers, and 0≤x≤2m, 0≤y≤2m.
There are ([2m]+1)⌊2m⌋+1≥m such expressions. So there exist integers x1, x2∈[0,2m], y1, y2∈[0,2m], such that (x1,y1)=(x2,y2), and x1+(2k+1)y1≡x2+(2k+1)y2(modm), So x≡(2k+1)y(modm),wherex=x1−x2,y=y2−y1. This means x2≡(2k+1)2y2≡−11y2(modm), that is, x2+11y2=tm for some integer t. Since ∣x∣≤2m, ∣y∣≤2m, we have x2+11y2<4m+411m<7m. So 1≤t≤6. As m is an odd number, obviously the equations x2+11y2=2m, and x2+11y2=6m have no integer solution.
(1) If x2+11y2=m, then x0=2x, y0=2y is a solution of x2+11y2=4m satisfying the lemma.
(2) If x2+11y2=4m, then x0=x, y0=y is a solution of x2+11y2=4m satisfying the lemma.
(3) If x2+11y2=3m, then (x±11y)2+11(x∓y)2=9⋅4m. First, assume that 3∣m. If x≡0(mod3), y≡0(mod3), and x≡y(mod3), then x0=3x−11y,y0=3x+y is a solution of x2+11y2=4m satisfying the lemma. If x≡y≡0(mod3), then x0=3x+11y,y0=3y−x is a solution of x2+11y2=4m satisfying the lemma. Now suppose 3∣m. Then the above are still integer solutions. If x2+11y2=4m has an even integer solution x0=2x1, y0=2y1, then x12+11y12=m⇔36m=(5x1±11y1)2+11(5y1∓x1)2. Since one of x1, y1 is even and the other is odd, so 5x1±11y1, 5y1∓x1 are odd numbers. If x1≡y1(mod3), then x0=35x1−11y1, y0=35y1+x1 is a solution of x2+11y2=4m satisfying the lemma. If x1≡y1(mod3), then x0=35x1+11y1, y0=35y1−x1 is a solution of x2+11y2=4m satisfying the lemma.
(4) If x2+11y2=5m, then 25⋅4m=(3x∓11y)2+11(3y±x)2. When 5∤m, if x≡±1(mod5),y≡∓2(mod5),or x≡±2(mod5),y≡±1(mod5), then x0=53x−11y,y0=53y+x is a solution of x2+11y2=4m satisfying the lemma. If x≡±1(mod5), y≡±2(mod5), or x≡±2(mod5), y≡∓1(mod5), then x0=53x+11y,y0=53y−x is a solution of x2+11y2=4m satisfying the lemma.
When 5∣m, then the above are still integer solutions. If x2+11y2=4m has an even integer solution x0=2x1, y0=2y1, then x12+11y12=m,x1≡y1(mod2), and we have 100m=(x1∓33y1)2+11(y1±3x1)2. If x1≡y1≡0(mod5), or x1≡±1(mod5), y1≡±2(mod5), or x1≡±2(mod5),y1≡∓1(mod5), then x0=5x1−33y1, y0=5y1+3x1 is a solution of x2+11y2=4m satisfying the lemma. If x1≡±1(mod5), y1≡∓2(mod5), or x1≡±2(mod5), y1≡±1(mod5), then x0=5x1+33y1,y0=5y1−33x1 is a solution of x2+11y2=4m satisfying the lemma.
The lemma is proved.
From the lemma, if x2+11y2=4m has a solution (x,y) with x, y being odd numbers, then it has a solution (x0,y0) with x0, y0 being even numbers satisfying x0≡(2k+1)y0(modm).
Let l=2k+1, the solution of the quadratic equation mx2+ly0x+ny02−1=0 is x=2m−ly0±l2y02−4mny02+4m=2m−ly0±x0. So the equation mx12+ly0x1+ny02−1=0 has at least an integer solution x1, i.e. mx12+ly0x1+ny02−1=0. This indicates that x1 is an odd number. Now, from this equation, it follows that (2ny0+lx1)2+11x12=4n. This means x2+11y2=4n has a solution (x,y) with x, y being odd numbers, where x=2ny0+lx1, y=x1.
Therefore, at least one of the equations x2+11y2=4m or x2+11y2=4n has a solution (x,y) with x, y 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.