Suppose that positive integers $m,n,k$ satisfy the equations $$m^2+1=2n^2, 2m^2+1=11k^2.$$Find the residue when $n$ is divided by $17$.
Problem
Source: Korean National Olympiad 2nd Round 2019 #3
Tags: number theory
16.11.2019 15:51
I think this was the best of all $8$ problems, though the solution requires Pell equations. The only answer is $5$, and it's easy to see that $(k,m,n)=(3,7,5)$ is a solution. We claim that other residues are impossible. Recursively define the sequence $\{m_i\}_{i=1}^\infty$ and $\{n_i\}_{i=1}^\infty$ as the following. $$m_1=n_1=1, m_{i+1}=3m_i+4n_i, n_{i+1}=2m_i +3n_i (i \ge 1)$$By the well-known lemma on Pell equations, we know that $(m,n)=(m_j,n_j)$ for some $j \ge 1$. We know that $n^2 \equiv 3(mod 11) \Longrightarrow n \equiv \pm 5 (mod 11)$. We check how $(m_i,n_i)$ is in mod $11$. \begin{align*}&(1,1)\rightarrow(7,5)\rightarrow(8,7)\rightarrow(8,4)\rightarrow(7,6)\rightarrow(1,-1) \\ \rightarrow&(-1,-1)\rightarrow(-7,-5)\rightarrow(-8,-7)\rightarrow(-8,-4)\rightarrow(-7,5)\rightarrow(-1,1) \\ \rightarrow&(1,1)\rightarrow\dots\end{align*}This implies $j \equiv 2(mod 3)$. Now we see how $(m_i ,n_i)$ is in mod $17$. \begin{align*}&(1,1)\rightarrow(7,5)\rightarrow(7,12)\rightarrow(1,-1) \\ \rightarrow &(-1,-1)\rightarrow(-7,12)\rightarrow(-7,5)\rightarrow(-1,1)) \\ \rightarrow & (1,1) \rightarrow \dots\end{align*}, which give no information. But we still have hope; observe that $(2n-1)(2n+1)=4n^2-1=11k^2$. $2n-1,2n+1$ are positive, thus either $$\begin{cases}&2n-1=11u^2 \\ &2n+1 =v^2 \end{cases}\text{ or }\begin{cases} &2n+1 = 11u^2 \\ &2n-1=v^2\end{cases}$$. For the first case, $11u^2+2=v^2$, a contradiction since $\left(\frac{2}{11}\right)=-1$. The second case implies $n\equiv 5 (mod 11)$, hence $j \equiv 2,11 (mod 12)$, or $j \equiv 2,3(mod 4) \Longrightarrow n\equiv \pm 5(mod17)$. It remains to prove that $n \equiv -5 (mod 17)$ is impossible. But then $v^2 =2n-1 \equiv 6 (mod 17)$, but $\left(\frac{6}{17}\right)=-1$, a contradiction!
23.03.2020 14:51
Most common way to solve this, is just know (k,m,n)=(3,7,5) and proving to make 5 as a real solution