Finding all primes $(p,q)$ for perfect squares.

Find all prime pairs $(p,q)$ such that $2p-1, 2q-1, 2pq-1$ are all perfect squares.

Source: St.Petersburg Olympiad 2011

I have only found the pair $(5,5)$ so I am thinking that maybe a modulo $5$ approach could work.

Solution 1:

Although Ivan Loh's answer is correct, I believe I may have found a much simpler and elementary proof that $(5,5)$ is the only pair.

Assume without loss of generality that $q\geq p$ and write $2pq-1 = x^2$, $2q-1 = y^2$, with $x$ and $y$ positive integers which are necessarily both odd.

We have the following inequalities.

$$x = \sqrt{2pq-1} < \sqrt{2pq} \leq q\sqrt{2}$$

$$y = \sqrt{2q-1} < \sqrt{2q}$$

For the first inequality we have used the assumption that $p\leq q$. Now we have that

$$x^2 - y^2 = (2pq-1) - (2q-1) = 2q(p-1)$$

So $2q(p-1) | (x+y)(x-y)$. Since $q$ is prime, we must now have either $q|(x-y)$ or $q|(x+y)$. Additionally, $x$ and $y$ are both odd, so $x-y$ and $x+y$ are both even. Combining this with the preceding statement we see that either $2q|(x-y)$ or $2q|(x+y)$.

The former cannot occur since $x-y < x < q\sqrt{2} < 2q$, so if $2q|(x-y)$ then $x = y$ which would imply that $p = 1$.

So $2q|(x+y)$. Now $x + y > 0$ so we must have

$$2q \leq x + y < q\sqrt{2} + \sqrt{2q}$$

Rearranging this we get

$$(2-\sqrt{2})q < \sqrt{2q}$$

so

$$(2-\sqrt{2})^2q < 2$$ and so $q < \frac{2}{(2-\sqrt{2})^2} < 5.8$. Since both $p$ and $q$ are $1$ mod $4$, this leaves $p = q = 5$ as the only possible pair.

Solution 2:

First note that $2p-1=x^2$ gives $p \mid x^2+1$ so $p \equiv 1 \pmod{4}$. Similarly $q \equiv 1 \pmod{4}$.

Result: Suppose $p, q \equiv 1 \pmod{4}$ are primes, and that $p=w^2+x^2, q=y^2+z^2$, where $w, x, y, z \in \mathbb{Z}^+$. Then there are exactly two ways to write $2pq$ as a sum of two perfect squares (up to order and signs), and the two ways are

\begin{align} 2pq& =((w+x)(y+z)-2wy)^2+((w+x)(y+z)-2xz)^2 \\ & =((w+x)(y+z)-2wz)^2+((w+x)(y+z)-2xy)^2 \end{align}

Before I go on to prove this result, let me first show how this finishes the problem. Since $2p-1$ is an odd perfect square and $>1$, we have $2p-1=(2s+1)^2$ for some positive integer $s$, so $p=2s^2+2s+1=(s+1)^2+s^2$. Similarly $q=(t+1)^2+t^2$ for some positive integer $t$. We may thus take $w=s+1, x=s, y=t+1, z=t$ in the result above.

If $s=t=1$, then we get $p=\frac{(2s+1)^2+1}{2}=5, q=\frac{(2t+1)^2+1}{2}=5$, giving the solution $(p, q)=(5, 5)$, which is easily checked to work.

Otherwise $st \geq 2$.

We are given that $2pq-1=k^2$ for some $k$, so $2pq=k^2+1$, giving a representation of $2pq$ as a sum of two squares. Applying the result, we have that one of $(w+x)(y+z)-2wy, (w+x)(y+z)-2xz, (w+x)(y+z)-2wz, (w+x)(y+z)-2xy$ must be $\pm 1$, where $(w, x, y, z)=(s+1, s, t+1, t)$.

However since $w=s+1>s=x, y=t+1>t=z$, we have that $(w+x)(y+z)-2wy$ is the smallest of the four, and thus must be $\leq 1$ (since one of the four is $\pm 1$) However

\begin{align} (w+x)(y+z)-2wy &=(2s+1)(2t+1)-2(s+1)(t+1) \\ &=2st-1 \\ & \geq 2(2)-1 \\ & >1 \end{align}

so we get a contradiction.

Therefore the only solution is given by $(p, q)=(5, 5)$.

Next, I will give two proofs of the result above. First, I will give a proof via algebraic number theory, but not as suitable (since this is supposed to be an olympiad problem). Next, I will give, as this is supposed to be an olympiad problem, a purely elementary proof.

Proof 1 (Algebraic number theory):

Suppose that $2pq=(a^2+b^2)$. Then $a, b$ are odd, so $(w^2+x^2)(y^2+z^2)=pq=(\frac{a-b}{2})^2+(\frac{a+b}{2})^2=c^2+d^2$, where $c=\frac{a-b}{2}, d=\frac{a+b}{2}$ are integers. We work in the ring of Gaussian integers, $\mathbb{Z}[i]$, and rewrite the equation as

$$(w+xi)(w-xi)(y+zi)(y-zi)=pq=(c+di)(c-di)$$

If $p=q$, this reduces to $(w+xi)^2(w-xi)^2=p^2=(c+di)(c-di)$, so by unique factorisation in $\mathbb{Z}[i]$, we have $\epsilon(c+di)=(w+xi)^2$, $\epsilon(c+di)=(w+xi)(w-xi)$ or $\epsilon(c+di)=(w-xi)^2$, where $\epsilon$ is a unit and thus $=\pm 1, \pm i$. Multiplying by units just reorders and/or changes signs of $c, d$, so we may WLOG assume $\epsilon=1$. Thus we get $(c, d)=(w^2-x^2, \pm 2wx)$ or $(c, d)=(w^2+x^2, 0)$. This gives the two representations given in the result. (Note: we then have that $(w+xi)(w-xi)=p^2=(y+zi)(y-zi)$ so that by unique factorisation we have $\{w, x\}=\{y, z\}$ (recall that they are positive))

If $p \not =q$, then by unique factorisation in $\mathbb{Z}[i]$, and that $N(w \pm xi)=p, N(y \pm zi)=q, N(c \pm di)=pq$, and $p \not =q$, we have that

$$c+di=\epsilon_1(w \pm xi)(y \pm zi)$$ or $$c+di=\epsilon_2(w \pm xi)(y \mp zi)$$

where $\epsilon_1, \epsilon_2$ are units, so they are $\pm 1$ or $\pm i$. Multiplying by units just reorders and/or changes signs of $c, d$, so we may WLOG assume $\epsilon_1=\epsilon_2=1$. This gives $(c, d)=((wy-xz), \pm(xy+wz))$ or $(c, d)=((wy+xz), \pm(xy-wz))$. We have $$\{a, b\}=\{c+d, c-d\}=\{(wy-xz)-(xy+wz), (wy-xz)+(xy+wz)\}$$ or $$\{a, b\}=\{c+d, c-d\}=\{(wy+xz)-(xy-wz), (wy+xz)+(xy-wz)\}$$

Since the representation is up to reordering and changing sign, we get the two representations given above in the result.

Proof 2 (Elementary): It is straightforward to check (via boring albeit tedious expansion) that the two ways given in the result to express $2pq$ as a sum of two squares are valid and distinct. It thus suffices to prove that there are at most two representations of $2pq$ as a sum of two squares (up to reordering and changing sign).

As in the first proof we may rewrite $2pq=a^2+b^2$ as $pq=(\frac{a-b}{2})^2+(\frac{a+b}{2})^2$ since clearly $a, b$ odd. It thus suffices to prove that there are at most two representations of $pq$ as a sum of two squares (up to reordering and changing sign).

Lemma 1: If $pq=\alpha_1^2+\beta_1^2=\alpha_2^2+\beta_2^2$ where $0<\alpha_i<\beta_i$ are integers and $(\alpha_1, \beta_1) \not =(\alpha_2, \beta_2)$, then $pq \mid (\alpha_1\beta_2-\alpha_2\beta_1)(\alpha_1\beta_2+\alpha_2\beta_1)$ but $pq \nmid (\alpha_1\beta_2-\alpha_2\beta_1)$, $pq \nmid (\alpha_1\beta_2+\alpha_2\beta_1)$.

Proof: We have $$(\alpha_1\beta_2-\alpha_2\beta_1)(\alpha_1\beta_2+\alpha_2\beta_1)=\alpha_1^2\beta_2^2-\alpha_2^2\beta_1^2=(pq-\beta_1^2)\beta_2^2-(pq-\beta_2^2)\beta_1^2 \equiv 0 \pmod{pq}$$

If $pq \mid (\alpha_1\beta_2-\alpha_2\beta_1)$, then since $0<\alpha_1, \beta_1, \alpha_2, \beta_2<\sqrt{pq}$ we have $-pq<\alpha_1\beta_2-\alpha_2\beta_1<pq$ so $\alpha_1\beta_2-\alpha_2\beta_1=0$.

Now, if $(\alpha_1, \beta_1) \not =1$, then $(\alpha_1, \beta_1)^2 \mid pq$ implies that $p=q$ and $(\alpha_1, \beta_1)=p$. This gives $1=(\frac{\alpha_1}{p})^2+(\frac{\beta_1}{p})^2 \geq 1^2+1^2$, a contradiction.

Thus $(\alpha_1, \beta_1)=1$. We then have $\alpha_1 \mid \alpha_2\beta_1$, so $\alpha_1 \mid \alpha_2$. Write $\alpha_2=k\alpha_1$, then $\beta_2=k\beta_1$ so $pq=\alpha_1^2+\beta_1^2=\alpha_2^2+\beta_2^2=k^2(\alpha_1^2+\beta_1^2)$ so $k^2=1$ so $k=1$ (since $k>0$). Thus $(\alpha_1, \beta_1)=(\alpha_2, \beta_2)$, a contradiction.

Thus $pq \nmid (\alpha_1\beta_2-\alpha_2\beta_1)$.

If $pq \mid (\alpha_1\beta_2+\alpha_2\beta_1)$, then since $0<\alpha_1, \beta_1, \alpha_2, \beta_2<\sqrt{pq}$, we have $0<\alpha_1\beta_2+\alpha_2\beta_1<2pq$ so $\alpha_1\beta_2+\alpha_2\beta_1=pq$. Now $(pq)^2=(\alpha_1^2+\beta_1^2)(\alpha_2^2+\beta_2^2)=(\alpha_1\beta_2+\alpha_2\beta_1)^2+(\alpha_1\alpha_2-\beta_1\beta_2)^2=(pq)^2+(\alpha_1\alpha_2-\beta_1\beta_2)^2$. Thus $(\alpha_1\alpha_2-\beta_1\beta_2)=0$. However $0<\alpha_1\beta_1<\alpha_2\beta_2$ since $0<\alpha_i<\beta_i$, so we get a contradiction.

Thus $pq \nmid (\alpha_1\beta_2+\alpha_2\beta_1)$, and we are done with Lemma 1.

Lemma 2: If $p\not =q$, and $pq=\alpha_1^2+\beta_1^2=\alpha_2^2+\beta_2^2=\alpha_3^2+\beta_3^2$ where $0<\alpha_i<\beta_i$ are integers, then $(\alpha_1, \beta_1), (\alpha_2, \beta_2), (\alpha_3, \beta_3)$ are not pairwise distinct.

Proof: Assume on the contrary that they are pairwise distinct. Apply Lemma $1$ to $pq=\alpha_1^2+\beta_1^2=\alpha_2^2+\beta_2^2$, $pq=\alpha_1^2+\beta_1^2=\alpha_3^2+\beta_3^2$, and $pq=\alpha_2^2+\beta_2^2=\alpha_3^2+\beta_3^2$. We get:

\begin{align} pq \mid (\alpha_1\beta_2-\alpha_2\beta_1)(\alpha_1\beta_2+\alpha_2\beta_1) \\ pq \nmid (\alpha_1\beta_2-\alpha_2\beta_1) \\ pq \nmid (\alpha_1\beta_2+\alpha_2\beta_1) \\ pq \mid (\alpha_1\beta_3-\alpha_3\beta_1)(\alpha_1\beta_3+\alpha_3\beta_1) \\ pq \nmid (\alpha_1\beta_3-\alpha_3\beta_1) \\ pq \nmid (\alpha_1\beta_3+\alpha_3\beta_1) \\ pq \mid (\alpha_2\beta_3-\alpha_3\beta_2)(\alpha_2\beta_3+\alpha_3\beta_2) \\ pq \nmid (\alpha_2\beta_3-\alpha_3\beta_2) \\ pq \nmid (\alpha_2\beta_3+\alpha_3\beta_2) \\ \end{align}

From the first three equations, we may WLOG assume $p \mid (\alpha_1\beta_2-\alpha_2\beta_1)$ and $q \mid (\alpha_1\beta_2+\alpha_2\beta_1)$. (Otherwise switch roles of $p, q$)

We have $p \mid (\alpha_1\beta_3 \pm \alpha_3\beta_1)$ (for some choice of sign), then $q\nmid (\alpha_1\beta_3 \pm \alpha_3\beta_1)$ so $q \mid (\alpha_1\beta_3 \mp \alpha_3\beta_1)$.

Then $p \mid [\beta_3(\alpha_1\beta_2-\alpha_2\beta_1)-\beta_2(\alpha_1\beta_3 \pm \alpha_3\beta_1)]=-\beta_1(\beta_2\alpha_3 \pm \beta_3\alpha_2)$. Since $p \nmid \beta_1$, we get $p \mid (\beta_2\alpha_3 \pm \beta_3\alpha_2)$.

Also $q \mid [\beta_3(\alpha_1\beta_2+\alpha_2\beta_1)-\beta_2(\alpha_1\beta_3 \mp \alpha_3\beta_1)]=\pm \beta_1(\beta_2\alpha_3 \pm \beta_3\alpha_2)$. Since $q \nmid \beta_1$, we get $q \mid (\beta_2\alpha_3 \pm \beta_3\alpha_2)$.

Therefore $pq \mid (\beta_2\alpha_3 \pm \beta_3\alpha_2)$ for some choice of sign, a contradiction.

Therefore they are not pairwise distinct, so we are done with the proof of Lemma $2$.

Now for $p \not =q$ and $pq=\alpha^2+\beta^2$, we may clearly WLOG assume $0<\alpha<\beta$, so by virtue of Lemma $2$, there are at most two representations of $pq$ as the sum of two squares, up to reordering and changing signs.

For $p=q$, and $p^2=\alpha^2+\beta^2$, we have the trivial representation $p^2=p^2+0^2$. Otherwise we may WLOG assume $0<\alpha<\beta$. If we have two distinct (up to reordering and changing sign) representations of $p^2$ as a sum of two nonzero perfect squares (i.e. excluding $p^2+0^2$), then we have $p^2=\alpha_1^2+\beta_1^2=\alpha_2^2+\beta_2^2$, where $p \nmid \alpha_1\beta_1\alpha_2\beta_2$ (Otherwise we get the trivial representation)

Lemma $1$ gives $p^2 \mid (\alpha_1\beta_2-\alpha_2\beta_1)(\alpha_1\beta_2+\alpha_2\beta_1)$ but $p^2 \nmid (\alpha_1\beta_2-\alpha_2\beta_1)$, $p^2 \nmid (\alpha_1\beta_2+\alpha_2\beta_1)$. Thus $p \mid (\alpha_1\beta_2-\alpha_2\beta_1)$ and $p \mid (\alpha_1\beta_2+\alpha_2\beta_1)$. Thus $p\mid 2\alpha_1\beta_2$, a contradiction. Therefore there is at most one non-trivial representation of $pq$ as a sum of non-zero perfect squares, so there are at most two representations of $pq$ in total. (up to reordering and changing sign)

Solution 3:

Assume $p,q$ not divisible by $5$.

$p=5k\pm1$ or $p=5k\pm2$

$$p=5k-1,5k+1,5k-2,5k+2$$

$$2p-1 = 10k-3,10k+1,10k-5,10k+3$$

But $-3$ and $+3$ are not quadratic residues modulo $5$, so $$p=5k+1, 5k-2$$

Obtain similar constraint on $q$ using fact that $2q-1$ is perfect square. Use last condition for the kill.

Thus $p$ and $q$ have to be divisible by $5$, but they are prime, so $p=q=5$

Solution 4:

I'd like to offer another answer based on the unique factorization of $\mathbb{Z}[i]$.

Notice that if we let $a^2=2p-1$, $b^2=2q-1$ and $c^2=2pq-1$, we can write $$p=\left(\frac{a+1}{2}\right)^2+\left(\frac{a-1}{2}\right)^2, q=\left(\frac{b+1}{2}\right)^2+\left(\frac{b-1}{2}\right)^2$$ and $pq=\left(\frac{c+1}{2}\right)^2+\left(\frac{c-1}{2}\right)^2$. This already implies, that $a,b,c$ are odd (otherwise $p,q$ wouldn't be whole numbers) and by Fermat's theorem that $p,q$ are of the form $4k+1$ since they are sums of two squares. (Also this representation is unique).

Now let $\alpha=\frac{a+1}{2}+\frac{a-1}{2}i$, $\beta=\frac{b+1}{2}+\frac{b-1}{2}i$ and $\gamma=\frac{c+1}{2}+\frac{c-1}{2}i$. Then $\alpha$ and $\beta$ are Gaussian primes, since their norm is prime. Also, if we let $\epsilon$ be a unit ($\pm 1$ or $\pm i$) then by unique factorization of Gaussian integers, we can write $\alpha \beta=\epsilon \gamma$.

This equation leads to four cases, with two equations in each case (the real and the imaginary part). Writing out and adding/subtracting to eliminate $c$ gives the following four possibilities: $$ (a-1)(b-1)-2 = \pm2 \\ (a+1)(b+1)-2 = \pm2 $$ By unique factorization of the integers, this leads to: $$ a, b = \pm(1, k), \pm(k, 1), \pm(3, 3), \pm(2, 5), \pm(5, 2) $$ Since $a=\pm1$ or $b=\pm1$ implies that one of $p$ or $q$ equals $1$ and both $a$ and $b$ need to be odd, we are left with $a,b=\pm(3,3)$ which implies $p,q=5,5$