Is $7+13k$ ever a perfect square (for $k$ in $Z$)? (Part of a question regarding modulus)

Question

The original question is whether or not $2x^2 ≡ 1 (mod 13)$ has an integer solution.

---

The way I solved it is:

Let $y = x^2$.

We can conclude that $y = 7+13k$ for $k$ in $Z$. I assert that $7 + 13k$ is never a perfect square.

---

However, I don't know how to prove it. Any suggestions on how to? Any other ways of solving this question (perhaps using residue classes)?

Answer 1

In $\mathbb F_{13}$ one has $$2x^2=1\iff x^2=2^{11}=7 \space \text{because } 2\cdot2^{11}=1$$ But $7$ is not residu quadratic modulo $13$. In fact, by the law of quadratic reciprocity, we have $$\left(\frac{7}{13}\right)\cdot\left(\frac{13}{7}\right)=(-1)^{\frac{7-1}{2}\cdot\frac{13-1}{2}}=1$$ But $$\left(\frac{13}{7}\right)=\left(\frac{-1}{7}\right)=(-1)^{\frac{7-1}{2}}=-1$$ Consequently $\left(\dfrac{7}{13}\right)$ must be equal to $-1$

Answer 2

If $a \equiv b\mod 13$ then $a^2 \equiv b^2 \mod 13$ where $b = 0,\pm 1, \pm2, \pm 3,... \pm 6$

Just test them out one after another $0^2 \equiv 0; 1^2 \equiv 1; 2^2 \equiv 4; 3^2 \equiv -4; 4^2\equiv 3; 5^2 \equiv -1; 6^2 \equiv -3 \mod 13$.

So $a^2 \not \equiv 7 \mod 13$ ever.

There's probably a slicker way to do it but that's pretty rock solid.

====

But I am concerned how to prove this if these were large numbers....

Read up on Quadratic Residues.

($q$ is a quadratic residue mod $n$ if $x^2 \equiv q \mod n$ has a solution.)

In the wikipedia article:

$x^2 \equiv 7 \mod p$ if and only if $p \equiv \pm1, \pm 3,\pm 9\mod 28$.

So that's the specific answer.

But if we avoid rote recital, a basic result will be:

If $p$ is prime then there are, including $0$, $\frac {p+1}2$ quadratic residues and $\frac {p-1}2$ quadratic non-residues.

So there are $\frac {p+1}2 = 7$ quadratic residues mod $13$ and $6$ quadratic non- residues.

(Also worth noting if $p \equiv 1 \mod 4$ as $13$ is, then $q$ is a quadratic residue if and only if $-q$ is. [And if $p \equiv 3 \mod 4$, the exact opposite is true; $q\ne 0$ is a quadratic residue if and only if $-q$ isn't.] But I didn't find this that helpful.)

As $0, 1,4,9,16\equiv 3, 25\equiv 12, 36\equiv 10$ are obviously $7$ perfect squares, then those are the seven quadratic residues.

And $7$ is not among them.

There's quite a bit to learn. But there's nothing wrong with punching a fist through a wall.