What do you mean by an odd solution?

Shall we prove the following: When $mn=k^2+k+3$, then at least one of the equations $x^2+11y^2=4m$ or $x^2+11y^2=4n$ has a solution $(x,y)$ with $xy$ being odd¿

Are the equations "$x^2+11y^2=4m$" and "$x^2+11y^2=4n$" independent?If there are simultaneous equations, it shows $m=n$ (Do I ask a silly question? )

ZetaX wrote: Shall we prove the following: When $mn=k^2+k+3$, then at least one of the equations $x^2+11y^2=4m$ or $x^2+11y^2=4n$ has a solution $(x,y)$ with $x,y$ being odd¿ Yes. I'll edit my problem.

Guys I think that for solve this problem we must looke at the complex nubers of $a+\sqrt{11}bi$ form wher $a,b\in{Z}$ and $i^2=-1$.

This is the most difficult problem in CMO 2006. Only one student got the full mark 21 points in this problem. The total score of this problem recieved by the first prize students is only 21+9+9=39.

Here's a way to prove it: Lemma 1: Prove all fctors of k^2+k+3 are expressible as form x^2+xy+3y^2. This is true as all binary quadratic forms of discrimant -11 are mutually equivalent. Lemma 2: Use mod- bash and completion of the square to finish off problem. Bomb

Lemma 1 p be a prime such that$\exists x\in Z+: x^2+11\vdots p$then $p=m^2+11n^2$or$4p=k^2+11l^2$(kl is odd) Lemma 2 If m,n are odd and$4m=x_1^2+11y_1^2,4n=x_2^2+11y_2^2$Where$x_1,x_2,y_1,y_2$ are positive odd integer)then exists positive odd integer k,l such that$4mn=k^2+11l^2$ Lemma 3 if p is prime and $p=x^2+11y^2$and positive integer m such that $4mp=z^2+11t^2$(where z,t are odd integer)then there exists 2 odd integers kand l such that $4m=k^2+11l^2$By using 3 lemmas,we can easily prove the problem

Can anybody post a complete solution?

One may remember the very beautiful fact tht if $xy=z^2+1$ then there are integers $a,b,c,d$ with $x=a^2+b^2,y=c^2+d^2,z=ac+bd$ (and of course $|ad-bc|=1$), connected close to Lagrange Identity $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$, and also remeber its proof by Fermat' Method of Finite Descent. Now we try to build a similar result for our problem, trying to use Lagrange Identity $(a^2+11b^2)(c^2+11d^2)=(ac+11bd)^2+11(ab-bd)^2$. After several trials, I have come to the following Lemma which implies the problem as a consequence: Let $k,m,n$ be positive integers with $k^2+11=4mn$ (of course $k$ is odd). Then there are positive integers $a,b,c,d$, not all even, with $4m=a^2+11b^2,4n=c^2+11d^2,2k=ac+11bd$ (and $2=|ad-bc|$). We use Fermat's Method of Finite Descent. Pick up a pair $(m,n,k)$ with $m+n+k$ minimal that fails our condition. If $k<2m,k<2n$ then $k^2+11=4mn\geq (k+1)^2$ then $k\leq 3$. If $k=1$ then the only possibility is $\{m,n\}=\{1,3\}$ and we can take $a,b,c,d$ to be $1,1,2,0$. If $k=3$ the only possibility is $\{m,n\}=\{1,5\}$ and we can take $a,b,c,d$ be $3,1,2,0$. If, for example $k>2n$, then $(k-2m)^2+11=4m(n-k+m)$ and this is a triple with smaller sum. so, there are positive integers $a,b,c,d$ with $4m=a^2+11b^2,4(n-k+m)=c^2+11d^2,k-2m=ac+11bd$. The simple computations show that $4m=a^2+11b^2, 4n=(a+c)^2+(b+d)^2. 2k=a(a+c)+11b(b+d)$ and so the conditions holds also for $m,n,k$, as if $a,b,c,d$ are not all even, the neither are $a,b,a+c,b+d$. We can now apply out lemma to the initial condition $4mn=4(k^2+k+3)=(2k+1)^2+11$

iura wrote: One may remember the very beautiful fact tht if $ xy = z^2 + 1$ then there are integers $ a,b,c,d$ with $ x = a^2 + b^2,y = c^2 + d^2,z = ac + bd$ (and of course $ |ad - bc| = 1$), connected close to Lagrange Identity $ (a^2 + b^2)(c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2$, and also remeber its proof by Fermat' Method of Finite Descent. Now we try to build a similar result for our problem, trying to use Lagrange Identity $ (a^2 + 11b^2)(c^2 + 11d^2) = (ac + 11bd)^2 + 11(ab - bd)^2$. After several trials, I have come to the following Lemma which implies the problem as a consequence: Let $ k,m,n$ be positive integers with $ k^2 + 11 = 4mn$ (of course $ k$ is odd). Then there are positive integers $ a,b,c,d$, not all even, with $ 4m = a^2 + 11b^2,4n = c^2 + 11d^2,2k = ac + 11bd$ (and $ 2 = |ad - bc|$). We use Fermat's Method of Finite Descent. Pick up a pair $ (m,n,k)$ with $ m + n + k$ minimal that fails our condition. If $ k < 2m,k < 2n$ then $ k^2 + 11 = 4mn\geq (k + 1)^2$ then $ k\leq 3$. If $ k = 1$ then the only possibility is $ \{m,n\} = \{1,3\}$ and we can take $ a,b,c,d$ to be $ 1,1,2,0$. If $ k = 3$ the only possibility is $ \{m,n\} = \{1,5\}$ and we can take $ a,b,c,d$ be $ 3,1,2,0$. If, for example $ k > 2n$, then $ (k - 2m)^2 + 11 = 4m(n - k + m)$ and this is a triple with smaller sum. so, there are positive integers $ a,b,c,d$ with $ 4m = a^2 + 11b^2,4(n - k + m) = c^2 + 11d^2,k - 2m = ac + 11bd$. The simple computations show that $ 4m = a^2 + 11b^2, 4n = (a + c)^2 + (b + d)^2. 2k = a(a + c) + 11b(b + d)$ and so the conditions holds also for $ m,n,k$, as if $ a,b,c,d$ are not all even, the neither are $ a,b,a + c,b + d$. We can now apply out lemma to the initial condition $ 4mn = 4(k^2 + k + 3) = (2k + 1)^2 + 11$ You are really intelligent , Iura . Very nice , solution . But i think , there is a small mistake in your solution Note that : $ a ; b ; c ; d$ are just normal integer , they can be negative For example $ (m;k;n) = ( 3 ; 5 ; 3 )$ satisfies the equation $ k^2 + 11 = 4mn$ But you can't find nonnegative integer $ a ; b ; c ; d$ such that $ 4m = a^2 + 11b^2 ; 4n = c^2 + 11d^2 ; 2k = ac + 11bd$ $ a ; b ;c ;d$ not all even Otherwise , Your solution is very excellent .

Is it technically correct if I show that for every integer of the form $k^2+k+3$ we can find $(m,n)$ such that $mn=k^2+k+3$?

Here is a less clever solution. Call a prime tangfastic if it is congruent to one of $1, 3, 4, 5, 9$ modulo $11.$ Call a positive integer tasty if it is expressible as $a^2 + 11b^2$ for $a, b \in \mathbb{Z}.$ In other words, a prime $p$ is tangfastic if and only if it is not $11$ and it is a square modulo We will start by proving the following useful lemma. Lemma. If $p$ is tangfastic, then $4p$ is tasty. Proof. If $p = 3, 5$, the lemma is easily checked. Otherwise, suppose that $p \ge 23.$ Note that since $p$ is tangfastic, it's easily obtained by the Quadratic Reciprocity Theorem that $\left( \frac{-11}{p} \right) = 1.$ Therefore, Thue's Lemma implies that there exist integers $x, y \in [0, \sqrt{p}]$ so that $p|x^2 + 11y^2.$ Since $x^2 + 11y^2$ is a square modulo $p$, it must be one of $p, 3p, 4p, 5p, 9p$. If $x^2 + 11y^2 = p$ or $4p$, then we are clearly done. Otherwise, suppose that $x^2 + 11y^2 \in \{3p, 5p, 9p\}.$ First we'll show that for an integer $k$ if $3k$ can be expressed as $a^2 + 11b^2$ for integers $a$ and $b$ not divisible by $3$, then $4k$ is tasty. Indeed, observe that $36k = (a\pm11b)^2 + 11(a \mp b)^2.$ Now just pick the choice of signs so that $\frac{a \pm 11b}{3} \in \mathbb{Z}$, and we're done. Now, observe that if $x^2 + 11y^2=3p$, then since $9 \nmid 3p$, we have $3 \nmid x, y$ and so $4p$ is tasty and we're done. If $x^2 + 11y^2 = 9p$, then if $3 | x, y$, we have $4p = \left(\frac{2x}{3}\right)^2 + 11 \left(\frac{2y}{3}\right)^2$ is tasty and we're done. Otherwise, we have that $3 \nmid x, y$, which yields that $12p$ is tasty. As $9 \nmid 12p$, we in turn have that $16p$ is tasty, so let $16p = a^2 + 11b^2$ for $a, b \in \mathbb{Z}$. By modulo $8$, it's clear that $2 |a, b$, and so hence $4p = \left(\frac{a}{2}\right)^2 + 11 \left(\frac{b}{2}\right)^2$ is tasty. We can similarly show that for an integer $k$ so that $5k = a^2 + 11b^2$ with $5 \nmid a, b$, $4k$ is tasty. Indeed, just consider $(3a \pm 11y, a \mp 3y)$ and divide both entries of one of them by $5.$ Hence, if $x^2 + 11y^2 = 5p$, then $25 \nmid 5p$ implies that $5 \nmid x, y$. Therefore, $4p$ is tasty. As we've exhausted all cases, the lemma is proven. $\blacksquare$ Now, let us return to the problem. The condition of the problem implies that $4mn = (2k+1)^2 + 11$. By modulo $8$, we have that $m, n$ are both odd. Now, if $m = 1$, then $x^2+11y^2 = 4n$ has the desired odd solution (simply $(2k+1, 1)$). Otherwise, suppose that $m >1$, and analogously $n>1.$ Suppose that there was a prime divisor $p|m$ which was tangfastic but not tasty. Then, let's write $4p = a^2 + 11b^2.$ Since $p$ is not tasty, we can't have $2|a,b$, and so therefore $a, b$ are both odd. For $k \in \mathbb{Z}$, let $4k$ be called Muriatic if it can be written in the form $a^2 + 11b^2$, where $a, b$ are both odd. In particular, $4p$ is Muriatic. Observation. If $t$ is an odd positive integer so that $4t = a^2+11b^2$ for odd $a, b$, then for any tangfastic odd prime $q$, $4tq$ is Muriatic. Proof. Then $4q = c^2 + 11d^2$ for some $c, d \in \mathbb{Z}$, by the lemma. We consider two cases. Case 1. $c, d$ are both even. Then, we've that $q = c'^2 + 11d'^2$, where $c', d' \in \mathbb{Z}$ are just $c, d$ divided by two. Then, observe that exactly one of $c', d'$ is odd, and so therefore $ac' + 11bd', ad'-bc'$ are both odd. We are done since $4tq = (ac' + 11bd')^2 + 11(ad'-bc')^2$. Case 2. $c, d$ are both odd. Then, we have that $16tq = (ac\pm 11bd)^2 + 11(ad \mp bc)^2.$ Since $a, b, c, d$ are all odd, it's clear that we can pick the signs so that $ac \pm 11bd, ad \mp bc$ are both congruent to $2$ mod $4$. From here, we can just divide two to imply the observation. $\blacksquare$ In view of the observation, let $m = p_0p_1 \cdots p_t$, where $p_0 = p$, and $p_0, p_1, \cdots, p_t$ are (not necessarily distinct) primes. From the Observation, it can easily be shown by induction that $4p_0 p_1 p_2 \cdots p_i$ is Muriatic, for each $0 \le i \le t$. This means that $x^2 + 11y^2 = 4m$ has odd solutions, as desired. Observe that the previous argument works as long as there is a $p|mn$ so that $4p$ is Muriatic. Now, we will analyze the remaining case (or lack thereof). Namely, we will analyze the scenario when for each prime $p|mn$, $4p$ is not Muriatic, but is expressible as $a^2 + 11b^2$ where $2|a, b.$ The following claim will help to solve the problem. Claim. If $p, q$ are positive integers so that $p$ is an odd tangfastic prime, $4p$ is not Muriatic, and $4pq$ is Muriatic, then $4q$ is also Muriatic. Proof. Suppose that $4pq = a^2 + 11b^2$ for odd positive integers $a, b.$ If $p = 11$, then $11 | a$, and so $4q = b^2 + 11 \left(\frac{a}{11}\right)^2$ implies $4q$ is Muriatic. Hence, assume that $p \neq 11$ henceforth, and write $4p = c^2 + 11d^2$. Since $4p$ is not Muriatic, we have that $2|c, d$, and therefore $p = c'^2 + 11d'^2$, where $c', d' \in \mathbb{Z}$ are $c, d$ divided by two. Now, notice that $4p^2q = (a^2 + 11b^2) (c'^2 + 11d'^2) = (ac' \pm 11bd')^2 + 11 (ad' \mp bc')^2.$ By looking modulo $p$, it's easy to see that we can select the signs so that $p| ac' \pm 11bd', ad' \mp bc'.$ From here, it remains only to note that $ac' \pm 11bd', ad' \mp bc'$ are odd, and both are divisible by $p$. These clearly imply that $4q$ is Muriatic. The claim is thus proven. $\square$ Now, we will use the claim to derive a contradiction in this case. Let $mn = p_1p_2 \cdots p_t$, where $p_1, p_2, \cdots, p_t$ are not necessarily distinct tangfastic primes, so that $4p_i$ is not Muriatic for each $1 \le i \le t.$ It's known that $4mn = (2k+1)^2 + 11 \cdot 1^2$ is Muriatic. By the claim and downwards induction on $i$, it's easy to show that $4p_1p_2 \cdots p_i$ is not Muriatic for each $t \ge i \ge 1.$ However, this implies that $4p_1$ is Muriatic, which is clearly a contradiction. As we've exhausted all cases, we know that one of $4m$, $4n$ is Muriatic, as desired. $\square$

Here is a solution that uses the fact that $\mathbb{Z}[(-1+\sqrt{-11})/2]$ is a UFD. The above solutions more or less prove this implicitly. Consider $\alpha = ((2k+1)+\sqrt{-11})/2$. Clearly $N(\alpha)=k^2+k+3=mn$. By factorizing we know that there exist $\beta,\gamma\in \mathbb{Z}[(-1+\sqrt{-11})/2]$ such that $\alpha=\beta\gamma$ and $N(\beta)=m, N(\gamma)=n$. Since $\alpha\not\in \mathbb{Z}[\sqrt{-11}]$, we can WLOG assume that $\beta\not\in\mathbb{Z}[\sqrt{-11}]$, showing that $\beta=(x+y\sqrt{-11})/2$ for odd $x,y$. The statement $N(\beta)=m$ now becomes $x^2+11y^2=4m$. This is the desired statement as $x,y$ are both odd.

The most beautiful solution I've ever seen. We need this theorem below: $f(x,y)=Ax^2+2Bxy+Cy^2$, if $D=AC-B^2>0$ then there exists a pair of $(u,v)\in\mathbb{Z}^2$, $(u,v)\neq (0,0) $ such that $|f(u,v)|\leq (\frac{4}{3}D)^{\frac{1}{2}}$ Let $f(x,y)=mx^2+(2k+1)xy+ny^2$ and $D=mn-\frac{(2k+1)^2}{4}=\frac{11}{4}$ With the theorem above, there exists a pair of $(u,v)\in\mathbb{Z}^2$, $(u,v)\neq (0,0) $ such that $|f(u,v)|\leq\sqrt{\frac{11}{3}}<2$ $D>0\Rightarrow f(x,y)>0\Rightarrow f(u,v)=1$, that's $mu^2+(2k+1)uv+nv^2=1$ $m,n$ are both odd $\Rightarrow$ At least one of $u,v$ is odd. WLOG $u$ is odd, with $4mnu^2+4u(2k+1)uv+4u^2v^2=4n$ Let $l=2k+1$ is odd, then $l^2=4mn-11$ Then $(2nv+lu)^2+11u^2=4n$, so $(x,y)=(2nv+lu,u)$ is the desired solution.