Perfect Squares

Try this

Click the $mod 3$ row: only $0$ and $1$ are filled in. Can a number that leaves remainder $2$ when divided by $3$ be a square?
Click $mod 4$ and $mod 8$ . Mod $8$ , only three of the eight remainders are filled in. How much does that rule out at a stroke?
Click $mod 10$ : this row is about the last digit of a square. Which digits can never be the last digit of a square?
Look at the small table “ $x$ and $x^{2}$ ” on the right. Is the second row symmetric? Why do $x$ and $m - x$ have squares with the same remainder?
Switch to “Cubes” and look at $mod 7$ and $mod 9$ ; switch to “4th powers” and look at $mod 5$ .

The squares of integers, $0, 1, 4, 9, 16, \dots$ , are called perfect squares. To find their remainders mod $m$ , you only need to work out $x = 0, 1, \dots, m - 1$ once each (the method from the residue systems stop). The three most useful rows are worth learning by heart:

x^{2} \equiv 0, 1 (mod 3) x^{2} \equiv 0, 1 (mod 4) x^{2} \equiv 0, 1, 4 (mod 8)

Predict first

How many possible remainders does the square of an odd number leave when divided by $8$ ?

1

2

3

4

Choose an answer first; then you can see the result.

Why

The biggest use of a remainder table is proving that an equation has no integer solutions. There is only one hard part: choosing the modulus.

Does x² + y² = 2023 have integer solutions?

Step 1 / 5

Try mod 3 first
Squares leave $0$ or $1$ mod $3$ , so the sum of two squares can leave $0, 1, 2$ : anything at all. The right side, $2023$ , leaves $1$ . No contradiction.

$x^{2} + y^{2} 2023 \in {0, 1, 2} \equiv 1 (mod 3)$
Then try mod 5
Switch to mod 4
And the right side leaves exactly 3
Why 4?

Two more tools

The barcode. By the Fundamental Theorem of Arithmetic, $n$ is a perfect square $⟺$ every exponent in its prime factorization is even. So the number of divisors of a square, $(a_{1} + 1) (a_{2} + 1) \dots$ , is odd, and only squares have this property.

Squeezing. There are no squares strictly between two neighboring squares $n^{2}$ and $(n + 1)^{2}$ . So if you can show that a number lies strictly between them, it is not a square. For example, when $n > 0$ ,

n^{2} < n^{2} + n + 1 < n^{2} + 2 n + 1 = (n + 1)^{2},

so $n^{2} + n + 1$ is never a perfect square.

Remove one condition

Break it

Counterexample lab: remove one condition

Conclusion: if $ab$ is a perfect square, then $a$ and $b$ are each perfect squares

$a = 4$ and $b = 9$ are coprime: each prime's bar appears on one side only. Every exponent of $ab = 36$ is even, so every exponent of $a$ and of $b$ must be even too.

Practice

Exercise 1Basic

Which digits can never be the last digit of a perfect square? List them all.

Exercise 2Basic

How many perfect squares are there in the sequence $11, 111, 1111, 11111, \dots$ ?

Exercise 3Advanced

Find the positive integer $n$ for which $n^{2} + n + 6$ is a perfect square.

Exercise 4Challenge

Prove that a positive integer that leaves remainder $7$ when divided by $8$ cannot be written as a sum of three squares of integers.

Try this

Why

Does x² + y² = 2023 have integer solutions?

Two more tools

Remove one condition

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

The remainders fit, so it must be a square

The product is a square, so each factor is a square