Let $p_1$, $p_2$, $p_3$ and $p$ be prime numbers. Prove that there are whole numbers $x$ and $y$ such that $y^2 \equiv p_1x^4-p_1p_2^2p_3^2 \pmod{p}$.

Can you please help me solve this number theory problem from a Bulgarian 2008 olympiad. I'm very very new to number theory and can't solve it. Thank you in advance!

  • $\begingroup$ $x=p_2^2p_3^2$, $y=0$? $\endgroup$ – Mindlack Sep 7 '19 at 8:16
  • $\begingroup$ I'm sorry it's x^4 $\endgroup$ – Hex Master Sep 7 '19 at 8:22
  • $\begingroup$ It might be related to "Pell" like equation $y^2-p_1x^4$ ... $\endgroup$ – rtybase Sep 7 '19 at 9:59

If $-p_1$ is a square mod $p$ or $p|p_2p_3$, $x=0$ works.

If $p=3$ mod $4$, then $p_1(1-p_2^2p_3^2)$ square iff $p_1(p_2^2p_3^2-1)$ not square iff $p_1((p_2p_3)^4-p_2^2p_3^2)$ not square. So either $x=1$ or $x=p_2p_3$ work.

Otherwise, $p=1$ mod $4$, and $-p_1$ and $p_1$ are squares mod $p$, so it is enough to find $x$ such that $x^4-p_2^2p_3^2$ is a square mod $p$.

If $p_2p_3$ is a square mod $p$, we are obviously done. Else, we can assume wlog $p_2$ square mod $p$, so up to factoring $p_2^2$ (a fourth power) out, we just need, given a non-square $q=p_3$ mod $p$, find a square $z$ such that $z^2-q^2$ is a square.

Factoring $q$ out, it is equivalent to show that for some non-square $u=z/q$, $u^2-1$ is a square.

Assume it is impossible: then, $u \longmapsto u^2-1$ maps non-squares into non-squares.

So if $u$ is a non square, exactly one of $u \pm 1$ is a non square, say $u+1$. Then for the same reason, exactly one of $(u+1)\pm 1$ is a square, that is, $u-1$ and $u+2$ are squares. So all the non-squares are grouped into “cells” square-non square-nonsquare-square.

Since cells do not share their non-squares and contain exactly two of them, since there are $\frac{p-1}{2}$ nonsquares, there are exactly $\frac{p-1}{4}$ cells and $\frac{p-1}{4}$ top squares in cells (since $0$ belongs to no cell, the definition of top number means something).

Note that there are also exactly $\frac{p-1}{4}$ squares of non-squares, and that they all are top squares of certain cells.

So the squares of non-squares (ie squares not being fourth powers) are exactly the top numbers of cells. So all the top non-squares in cells are of the form $u^2-1$ for some non-square $u$.

Now, let $u$ be a non-square such that for some $t$, $u=\frac{t^2-1}{1+t^2}$. Since $-1$ is a square (of, say, $i$), $u^2-1=\left(\frac{2it}{t^2+1}\right)^2$, which is impossible. So for all $t$ non squares, either $t^2+1=0$ or $\frac{t^2-1}{t^2+1}$ is a square, ie $t^2+1$ is either a nonsquare or zero.

So as a consequence, every top number of cell (except possibly $-1$) is the bottom number of another cell.

So the pattern (for reasons of cardinality) in $\{1,\ldots,p-1\}$ of squares/non-squares mod $p$ is $S\ldots SNNSNNSNNSNNS \ldots SNNS$ where the last $S$ is $-1$.

Now, assume the bottom number of the first cell is $t^2 > 1$. Then $\frac{t^2-1}{t^2+1}$ is a square, so $t^2+1$ (inside the first cell, not a square) is a square. So the pattern is actually SNNSNNS...SNNS. This gives $\frac{p-1}{2}$ nonsquares and $\frac{p-1}{4}+2$ squares (counting zero). So $p=\frac{3(p-1)+8}{4}=\frac{3p+5}{4}$ so $p=5$.

$p=5$ is left to the reader as an exercise.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.