2
$\begingroup$

If we suppose that we are interested in non-negative integers less than a prime $p$, is it possible to find more than two of these integers, such that, when squared, are all congruent modulo $p$?

In other words, can we find non-negative integers $x$, $y$, $z$, such that $0 \le x < y < z < p$ and $x^2 \equiv y^2 \equiv z^2 \bmod p$

I believe that we can't, but I'm not sure how to prove this.

2 Answers 2

1

Note that the residues $\mod p$ form a field, so there are no zero divisors. If $x^2\equiv y^2 \equiv z^2 \pmod p$, you have $(y-x)(y+x)\equiv (z-x)(z+x) \equiv 0 \pmod p$ and you need a zero in each product.

2

there are at most two solutions of $x^2 \equiv a \pmod p$.

In general, let $P(x)$ be a degree $n$ polynomial, there are at most $n$ solutions to $P(x) \equiv 0 \pmod p$ (because mod p is a field domain).