Is there an elementary proof (i.e. without using fields and norms) for the fact that for a prime $p$ the congruence $x^2+y^2=-1 \mod p$ is solvable if $p \equiv 3 \mod 4$?
Asked
Active
Viewed 1,453 times
5
-
Without fields? Say, without using that the set of all non-zero elements in a field is a commutative multiplicative group which, in this particular case, is even cyclic? – DonAntonio May 24 '17 at 08:56
-
Must $p$ be prime? – BB3C May 24 '17 at 09:02
-
@DonAntonio I would consider cyclic groups as elementary, thus this would be ok – Martin May 24 '17 at 09:06
-
@BBC3 yes I forgot to mention that – Martin May 24 '17 at 09:06
1 Answers
5
If $p$ is a prime then $x^2$ can leave the remainders $0,1^2,2^2,\dots ,[(p-1)/2]^2$ when divided by $p$, and all of them are distinct.
Now suppose $x^2+y^2$ does not leave a remainder $p-1$ when divided by $p$ for any value of $x,y$.
So $y^2$ can't leave the remainders $(-1+0),(-1-1^2),(-1+2^2),(-1+3^2),\dots (-1+[(p-1)/2]^2)$ when divided by $p$.
Note that all of them are distinct and there are $(p+1)/2$ of them, so the cardinality of the set of remainders $y^2$ when divided by $p$ can be at most $(p-1)/2$ but we know that the cardinality of the set of remainders $y^2$ when divided by $p$ is $(p+1)/2$, hence a contradiction.
So for any prime $p$, irrespective of whether it is of the form $4k+1$ or $4k+3$, the above congruence has a solution!
Arpan1729
- 3,414
-
2No need to invoke contradiction. $x^2$ takes on $(p+1)/2$ values, so does $-1-y^2$, therefore there must be at least one value in common. – Gerry Myerson May 24 '17 at 10:10
-