Question

I'm trying to find a proof that the congruence
\[ x^2 \equiv a\mod m \]
only has solutions for all integer \(a\) for \(m=1,2\).

Answer 1

For example, when \(m=3\), there is no \(x\) such that
\[ x^2\equiv2\mod 3.\]
This is because any integer \(x\) can be written as either \(x_0=3k,\ x_1=3k+1\) or \(x_2=3k+2\). Squaring these three, we see that
\[ x_0^2=9k^2 \\
x_1^2=9k^2+6k+1=3(3k^2+2)+1 \\
x_2^2=9k^2+12k+4=3(3k^2+6k+1)+1\]
So the rest on division by 3 of \(x^2\) for any integer \(x\) is either 0 or 1. I'm pretty sure that there is always an \(a\) for which there is no solution when \(m>2\), but I haven't been able to prove it yet.

Answer 2

Sorry for the late reply, but I just couldn't resist adding my input.

Suppose \(m\ge 3\). Then \(x^2=1\) has two unique solutions: 1, and -1. So then if you take every element in the set \(S=\{0,1,...,m-1\}\) and square it modulo \(m\), then your resulting set of squares will have size at most \(m-1\lneq m\). So not every element in \(S\) can be a perfect square modulo \(m\).

I think this will do it.

Answer 3

Awesome, thanks! Really a case of over complicating things on my part.

Answer 4

I've done my fair share of over complicating :P