Find all primes $p$ such that there exist an integer $n$ and positive integers $k, m$ which satisfies the following. $$ \frac{(mk^2+2)p-(m^2+2k^2)}{mp+2} = n^2$$
Problem
Source: 2017 KMO Problem 2
Tags: number theory
rkm0959
12.11.2017 13:56
I heard infinite descent can be used here. The answer seems to be $3$ and primes of the form $4k+1$. It's not very difficult to show that there exists $n, k, m$ for such primes, (use fermat's two square for $4k+1$) Proving that there are no solution for $2$ and $4k+3$ primes other than $3$ seems to be very difficult.
Vietnamisalwaysinmyheart
12.11.2017 16:45
Okay, last week I didn't solve a Markov equation on my test so I hope my below solution is right so that I can have a sweet revenge! Firstly, assume $n\in\mathbb{N}$ doesn't cost anything. Rewrite the equation as: $(mk^2+2)p-x^2-2k^2=(mp+2)n^2$ $\Leftrightarrow p(mk^2-mn^2+2)=m^2+2k^2+2n^2$ $\Leftrightarrow p=\frac{m^2+(k+n)^2+(k-n)^2}{m.(k-n).(k+n)+2}$ Checking the case: $m(k-n)(k+n)=-1$ we have the answer $p\equiv 1 \pmod 4$ Now, assume: $k>n$, and so the equation is equivalence to solve the following equation (call it $(1)$) $p=\frac{a^2+b^2+c^2}{abc+2}$ in natural numbers. (Note, we may concern about the parity of $(k+n,k-n)$ but for $3$ numbers, there are two of them which are same parity) The case $p=2$ can be handled with the same method as the below but of course will take some small case so I won't consider it. Assume $p\geq 3$ Consider a natural roots of $(1)$ as: $(a_1,b,c)$ with $a_1\geq \text{max}\{b,c\}$, and consider the quantity $a_1+b+c$ minimum. Rewrite the equation $(1)$ as variable of $a_1$: $X^2-X.pbc+b^2+c^2-2p=0$, since it has a root $a_1$, it also has another $a_2$. By Viet, we have: $a_1+a_2=pbc$ and: $a_1a_2=b^2+c^2-2p$ Case 1 $b^2+c^2=2p$, this gives the answer all primes $p\equiv 1 \pmod 4$ (you can check it by replace: $a_1=pbc$) Case 2 $b^2+c^2>2p$, this gives: $a_2\in\mathbb{N}$ and thus, by the minimum assumption, we must have: $a_2\geq a_1$ Since: $a_1a_2=b^2+c^2-2p<2a_1^2$, hence: $2a_1>a_2$, since: $a_1+a_2=pbc$, we have: $3a_1>pbc$, since: $p\geq 3$, thus, $a_1>bc$ Since: $a_2\geq a_1$, thus, $b^2+c^2>b^2+c^2-2p=a_1a_2>b^2c^2$, which is contradition. Case 3 $b^2+c^2<2p$. This implies $a_2<0$ and it's a integer. We have: $a_1+a_2=bcp, so: a_1>pbc\geq p$ Since: $a_1.|a_2|=2p-b^2-c^2<2p$ If $|a_2|\geq 2$, then $a_1<p$, a contradition. So: $a_2=-1$, which gives: $p(2-bc)=b^2+c^2+1$, which gives: $b=c=1$ and $p=3$
talkon
12.11.2017 17:23
Sniped ._. Answer. $p=3$ and $p\equiv 1\pmod{4}$. Solution.
First we isolate $p$ out, getting $p =\frac{m^2+2k^2+2n^2}{2 + mk^2 - mn^2}.$
Let $u=k+n$ and $v=k-n$, so the above equation is now $ p =\frac{m^2+u^2 + v^2}{2 + muv}$
with the extra condition $u\equiv v\pmod{2}$.
It turns out to be better to just solve the equation
$$ p = \frac{a^2+b^2+c^2}{2+abc}$$over $\mathbb Z$.
Since we can flip the sign of two of $a,b,c$ without affecting anything, we may force at least two numbers in $\{a,b,c\}$ to be nonnegative. Call this Call this equation with the condition (eq1).
We will use Vieta jumping here. Throughout this part, let $S=\{a,b,c\}$ be the solution to (eq1) with minimal $a+b+c$.
Write the above equation as a quadratic equation in $a$:
$$ a^2 - (bcp) a + (b^2+c^2-2p) = 0$$Now consider two cases:
Case 1: $S$ contains $0$.
This is easy. WLOG $c=0$ then we have $p=\frac{a^2+b^2}{2}$, therefore $p=2$ or $p\equiv 1\pmod{4}$.
Case 2: $S$ doesn't contain $0$.
WLOG $a\geq b\geq c$.
Case 2.1 all members of $S$ are positive
Solving for $a$, we have
$$ a = \frac{pbc - \sqrt{p^2b^2c^2 - 4b^2 - 4c^2 + 8p}}{2}$$where the sign after $pbc$ must be $-$ to minimize $a+b+c$.
Since $a\geq b\geq c$,
$$ 2a = pbc - \sqrt{p^2b^2c^2 - 4b^2 - 4c^2 + 8p} \geq 2b$$$$ (pbc - 2b)^2 \geq p^2b^2c^2 - 4b^2 - 4c^2 + 8p$$After expanding, this reduces to
$$ 2b^2 + c^2 \geq 2p+ pb^2c $$Since $b\geq c>0$,
$$3b^2 \geq 2b^2 + c^2 \geq 2p + pb^2c > pb^2c$$Hence $pc<3$ so $(p,c) = (2,1)$. However, this contradicts $2b^2+c^2 > 2p+pb^2c$, so no possible $p$ in this subcase.
Case 2.2 $c<0$
From $p>0$ and $a^2+b^2+c^2\geq 0$ it follows that $2+abc>0$. Therefore $\{a,b,c\} = \{1,1,-1\}$ and this gives $p=3$.
Suppose that we have solutions $S=\{a,b,c\}$ and $S'=\{a',b',c'\}$ to (eq1). We'll call them similar, denoted by $S\sim S'$ if the multiset $S$ and $S'$ satisfy $|S\cap S'|=2$, i.e. they have two pairs of equal members. Furthermore, call two solutions $S$ and $S'$ connected if there are a series of solutions such that $S\sim S_1\sim S_2\sim\cdots\sim S'$.
Now fix a "connected component" of the solutions to (eq1) and $S=\{a',b',c'\}$ be the solution in that component with minimal $a+b+c$ where WLOG $a\geq b\geq c$. Similar to in 1., we have $c=0$, and $4=2p=a^2+b^2$ so $\{a,b,c\}=\{2,0,0\}$. However, it's easy to check that the connected component containing $\{2,0,0\}$ has only two members : $\{2,0,0\}$ and $\{0,0,-2\}$, and when plugged back to $m,n,k$, these two fail to give both $k,m$ positive. Hence there are no solutions for $p=2$.
For $p=3$, just choose $(a,b,c)=(4,1,1)$ which reduces to $(m,k,n) = (4,1,0)$.
For $p=4k+1$, let $x,y$ be positive integers such that $x^2+y^2=p$. WLOG $x$ is even.
Then $(m,n,k) = \left(y,\frac{x}{2},\frac{x}{2}\right)$ is a solution. This ends our proof. $\blacksquare$