Which numbers are square modulo 9?

Question

How can I prove that n = $1,4,7,9$ for every integer k such that $k^2 = n$ (mod9)?

Answer 1

You would better state it using $0$ instead of $9$, i.e., $\forall{k}:k^2\equiv0,1,4,7\pmod9$.

---

There you go:

• $k\equiv0\pmod9 \implies k^2\equiv0^2\equiv0\pmod9$
• $k\equiv1\pmod9 \implies k^2\equiv1^2\equiv1\pmod9$
• $k\equiv2\pmod9 \implies k^2\equiv2^2\equiv4\pmod9$
• $k\equiv3\pmod9 \implies k^2\equiv3^2\equiv9\equiv0\pmod9$
• $k\equiv4\pmod9 \implies k^2\equiv4^2\equiv16\equiv7\pmod9$
• $k\equiv5\pmod9 \implies k^2\equiv5^2\equiv25\equiv7\pmod9$
• $k\equiv6\pmod9 \implies k^2\equiv6^2\equiv36\equiv0\pmod9$
• $k\equiv7\pmod9 \implies k^2\equiv7^2\equiv49\equiv4\pmod9$
• $k\equiv8\pmod9 \implies k^2\equiv8^2\equiv64\equiv1\pmod9$

Answer 2

k^2 = n mod 9

I would start with observing that for any integer k, k=9a+b where b=0,1,2,3,4,5,6,7 or 8 and a is any integer.

so, k^2 = (81 a^2 + 18ab + b^2) = b^2 mod 9

So possible solutions for n are 0,1,4,9,16,25,36,49,64 = 0,1,4,0,7,7,4,1 mod 9 = 0,1,4,7 mod 9