[Math] Proving for every odd number $x$, $x^2$ is always congruent to $1$ or $9$ modulo $24$

discrete mathematics

A problem I have been presented with asks the following:

Prove for every odd number $x$, $ x^2$ is always congruent to $1$ or $9$ modulo $24$.

This seems odd and non-intuitive to me. Of course, it must be true other wise they wouldn't be asking for me to prove it.

I know that:
$9$ modulo $24$ $=$ $9$

$1 = 1$

How could every odd number in existence squared be equal to either 1 or 9?

Best Answer

The original poster, Bob, said in a comment:

The questions asks if $x^2$ is equivalent to 1mod24 or 9mod24 where $x$ is an odd integer. However, based on the responses here it is actually asking if $x^2$mod24 is equivalent to 1mod24 or 9mod24.

I think this comment is revealing the real source of OP's difficulty with this question.

First, the "mod" does not apply to a number or to an expression like $x$ or $x^2$. It applies to the equivalence. When we say that 289 is equivalent to 1 (mod 24) we are not talking about some special kind of 1 called "1mod24". We are not talking about a special kind of 289 either. They are the same 1 and the same 289 as always. The "mod 24" applies to "equivalent": it is the equivalence that is mod 24: 289 and 1 are equivalent (mod 24) but are not equivalent (mod 17); that is a different kind of equivalence.

A better way to say it, maybe, would be to say "1 is equivalent, mod 24, to 289". There is a special kind of "equivalence mod 24", and that is what is meant here: If $n$ is odd, then $n^2$ is equivalent (mod 24) to 1 or 9.

Similarly, the notation is misleading. We write $$289\equiv1\pmod{24},$$ which suggests that the $\pmod{24}$ applies to the 1. But it doesn't. It applies to the $\equiv$. A better notation might be something like $$\def\mtf{\stackrel{\mod\!\!{24}}\equiv}289\mtf1.$$ But that's not how we write it, because that's not how it has been written in the past.

So that's one problem: you are confused by the notation and the terminology. There is no such thing as "1 mod 24" or "$x^2$ mod 24", because the "mod 24" is talking about whether two things are equivalent in a certain way. Specifically, two things are equivalent (mod 24) when they differ by a multiple of 24.

A second problem is that we abuse the notation and we do sometimes speak of “the value of $x^2$, mod 24”. I did this myself in the header of the table in my other answer:

$$\begin{array}{r|r|l} n & n^2 & \color{darkred}{n^2\pmod{24}} \\\hline \end{array}$$

When we speak of something like “the value of $x^2$, mod 24”, what we mean is this: It is not hard to see that every number is equivalent (mod 24) to one of $0, 1, 2, \ldots,\text{ or }23$, which is called its "residue". For all mod-24-related purposes the residue behaves just like the original number, so for mod-24 purposes, we can pretend that the residue is the original number. Any time you have some equivalence mod 24 that involves the number 289 somewhere, you can replace the 289 with its mod-24 residue 1, because 289 is equivalent (mod 24) to 1.

And that last bit may be the essential piece you are missing in all this, a deep theorem that is crucial to all work with modular equivalence: If $x$ and $y$ are equivalent (mod 24), and you have some expression involving $x$, then the value of that expression is equivalent (mod 24) to the value you get if you replace $x$ with $y$, or with anything else that is equivalent (mod 24) to $x$. If $x$ and $y$ are equivalent (mod 24), they are interchangeable as far as equivalence-mod-24 is concerned.

In particular, if $x$ and $y$ are equivalent (mod 24) then so are their squares $x^2$ and $y^2$. Because certainly $$x^2\mtf x^2$$ and if we replace that $x$ on the right-hand side with the equivalent (mod 24) value $y$ we get $$x^2\mtf y^2.$$

Similarly, suppose we want to know if $$289\mtf 1\text{ or } 9 ?$$ is true. Instead of dealing with 289, we can deal with its mod-24 residue 1 instead, because 289 and 1 are equivalent (mod 24). So we can replace the 289 with its mod-24 residue 1, and the result is $$1\mtf 1\text{ or } 9 ?$$

which is obviously true.

And again: suppose we know that some number $n$ is equivalent (mod 24) to 17: $$n\mtf 17.$$ Then $$\begin{array}{rcl} n^2& \mtf & 17^2 \\ & = & 289\\ & \mtf & 1 \end{array}$$

So if $n$ is any number equivalent (mod 24) to 17, then $n^2$ is equivalent (mod 24) to 1.

This is why we can argue like this: “Since any odd number is equivalent (mod 24) to one of 1, 3, 5, …, or 23, it's enough to check that each of these 12 numbers has the required property, of having a square that is equivalent (mod 24) to 1 or to 9. Because if all 12 of those do, then so will any number that is equivalent (mod 24) to one of them, and therefore so will any odd number at all.”

For example, how do I now know that $1111^2$ is equivalent (mod 24) to 1 or to 9? It's because $1111$ is equivalent(mod 24) to 7, and so its square, $1111^2$, must be equivalent (mod 24) to $7^2$, which is 49, which is equivalent (mod 24) to 1. So I can know that $1111^2\mtf 1$, without having to do a long calculation. And I can know that once I check the claim (that $n^2$ is equivalent (mod 24) to 1 or to 9) for the 12 residues $1, 3, 5, \ldots, 23$, I know that it is true for every odd integer, because every odd integer is equivalent (mod 24) to its (mod 24) residue which is one of $1, 3, 5, \ldots, 23$.