## Prime Partner

#### Problem

Given that $p$ is an odd prime and $n$ is a positive integer, prove that there always exists a value of $n$ for which the expression $n^2 + np$ is a perfect square.

For example, when $p = 7$, $9^2 + 9 \times 7 = 144 = 12^2$.

Furthermore, prove that this value of $n$ is unique.

#### Solution

Let $n^2 + np = n(n + p) = a^2$.

We will begin by showing that $n$ and $n + p$ must be relatively prime.

If the prime $q$ were a common factor of both $n$ and $n + p$, then $q$ would divide $n + p - n = p \implies p = q$. Hence $n$ must be a multiple of $p$.

Let us suppose that $n = kp$.

\begin{align}\therefore kp(kp + p) &= a^2\\k(k+1) &= \left(\dfrac{a}{p}\right)^2\end{align}

As $k$ is integer, $\dfrac{a}{p}$ must also be integer.

But as $k(k+1) = \left(\dfrac{a}{p}\right)^2$ it follows that $k^2 \lt \left(\dfrac{a}{p}\right)^2 \lt (k+1)^2$.

$\therefore k \lt \dfrac{a}{p} \lt k + 1$

Clearly the integer $\dfrac{a}{p}$ cannot lie between two consecutive integers, hence we conclude that $n$ is not a multiple of $p$. Furthermore we demonstrate that $GCD(n, n + p) = 1$.

In which case, for $n(n + p)$ to be a perfect square, both $n$ and $n + p$ must be perfect squares.

Let $n = u^2$ and $n + p = v^2$.

$\therefore n + p - n = p = v^2 - u^2 = (v-u)(v+u)$

For this product to be prime, $v - u = 1$, and $v + u = p$. Subtracting we get $2u = p - 1$, hence $n = u^2 = \dfrac{(p - 1)^2}{4}$.

That is, a value of $n$ exists for every odd prime, and we have deductively shown that this value is necessarily of the form, $n = \dfrac{(p - 1)^2}{4}$.

Prove that for $k \gt 2$ there only exists a value of $n$ such that $n^k + n^{k-1}p$ is a perfect power of $k$ for some values of $p$ and when $n$ exists it is indeed unique; investigate the conditions for $p$ to have such a "partner".

Problem ID: 291 (22 Sep 2006)     Difficulty: 4 Star

Only Show Problem