For positive integer $n$, find all pairs of coprime integers $p$ and $q$ such that $p+q^2=(n^2+1)p^2+q$
Problem
Source: Regional Olympiad - Federation of Bosnia and Herzegovina 2015
Tags: number theory, coprime
23.09.2018 19:44
gobathegreat wrote: For positive integer $n$, find all pairs of coprime integers $p$ and $q$ such that $p+q^2=(n^2+1)p^2+q$ If we rewrite this equation in the following form $q^2-q+p-(n^2+1)p^2=0$, then $D=1-4p+4(n^2+1)p^2 = (2p-1)^2+(2np)^2=m^2$. Hence according to the theory of Pythagorean triplets, one has $2p-1 = k(a^2-b^2)$, $2np=2abk$ and $m=k(a^2+b^2)$. Using these formulas, it is easy to write the exact solution. But there is one problem: if we express $n$ in terms of $a$, $b$ and $k$, we have to find the condition when $n$ will be integer...
24.09.2018 10:57
[Solution] $\displaystyle p+q^{2} =\left( n^{2} +1\right) p^{2} +q \ \Longrightarrow \ q^{2} \equiv q\pmod p$ Since $\displaystyle gcd( p,q) =1$ , we have $\displaystyle q\equiv 1\pmod p$ So we can choose non-negative integer $\displaystyle k$ such that $\displaystyle q=kp+1$. And then we get $\displaystyle \left( n^{2} -k^{2} +1\right) p=k+1$. Since both $\displaystyle p$ and $\displaystyle k+1$ are positive, we have $\displaystyle n\geq k$. Assume that $\displaystyle n\geq k+1$. Then we have $\displaystyle k+1\geq ( k+1)^{2} -k^{2} +1\geq 2k+2$. This is clearly impossible. Therefore, we must have $\displaystyle k=n$. This implies that $\displaystyle ( p,q) =\left( n+1,n^{2} +n+1\right)$. On the other hand, we can verify that $\displaystyle ( p,q) =\left( n+1,n^{2} +n+1\right)$ satisfies the original equation and $\displaystyle gcd( p,q) =1$. Hence we can conclude that $\displaystyle ( p,q) =\left( n+1,n^{2} +n+1\right)$ is the only solution.