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

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?

-
Based on some of your comments, I would suggest you avoid thinking or writing 'equal' when working with congruences. $a \equiv b \operatorname{mod} m$ means that $m \mid a-b$. It does NOT mean that $a = b$. – NotAwake Nov 24 '13 at 2:24
I think the fact that he's aware of that is precisely what's causing his confusion, because then he doesn't understand why you can just check the cases up to $\pm 11$ or up to $23$. – Dustan Levenstein Nov 24 '13 at 2:29
For starters, modulo 24, there are only $12$ odd numbers in existence! – Hurkyl Nov 24 '13 at 2:35
I've always thought of 'modulo' as just describing a function which returns the remainder when you divide two numbers and nothing more. – Bob Nov 24 '13 at 2:38
@Bob: An example of something not well defined is if we tried to define a function on the rational numbers $f(x/y) = x+y$. This is not well-defined, because $1/2$ and $2/4$ are the same rational number, however $f(1/2) = 3$ and $f(2/4) = 6$ are not the same. – Hurkyl Nov 25 '13 at 6:08

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$.

-
I think this is an excellent answer that combines all the things myself and others were trying (unsuccessfully, I think) to explain in comments. +1 – NotAwake Nov 24 '13 at 3:50
I agree. Thank you very much for this answer. While I still have some work to do -- this explanation is very insightful and answers all of my confusions regarding the solutions offered by others! – Bob Nov 24 '13 at 3:56
You are welcome! I am glad that we were able to get to the heart of the matter. – MJD Nov 24 '13 at 3:57
It's worth noting that in an equivalence mod n, you can't always replace arbitrary numbers with equivalent numbers mod n; for example, you can't do it with exponents. It is only the case that if $a\equiv x$ and $b\equiv y$, then $a+b\equiv x+y$ and $ab\equiv xy$. – user2357112 Nov 24 '13 at 4:51
Just note that sometimes the notation $a \bmod b$ is used for the remainder when $a$ is divided by $b$. Often enough, in fact, for LaTeX to predefine the operation... – vonbrand May 3 '14 at 16:07

When in doubt, you can simply square all of the odd numbers 1, 3, 5, up to 23, and verify that each one is congruent to either 1 or 9 modulo 24. What follows is a trick, which will get you the result much more quickly.

Write $(2k+1)^2 = 4k^2 + 4k+1 = 4k(k+1)+1$.

The claim then is that for all $k$, $24$ divides either $(2k+1)^2-1 = [4k(k+1)+1]-1 = 4k(k+1)$ or $(2k+1)^2-9 = [4k(k+1)+1-9] = 4k(k+1)-8 = 4[k(k+1)-2]$. From the fact that either $k$ or $k+1$ is even, notice that $8$ divides both quantities. So it is sufficient to see that $3$ divides one or the other. Now consider cases based on whether $k \equiv 0, 1,$ or $2 \mod 3$.

-

Based on your comments to the first answer, you may need a further review of the modulo concept. There are many resources so I will leave you to use your favorite or use a search engine.

As stated in other answers, the most straightforward way to verify the claim is to square each number from 1 to 23 (or -11 to 11) and reduce the result modulo 24. However, I will show you a method that makes problems with much larger numbers manageable.

The key is to realize that conditions modulo different moduli are independent for coprime moduli. Therefore, you can first show that all odd squares are $1 \mod 8$ by only checking four values. You can then show that all squares are $0$ or $1\mod 3$ (realizing that you must check all values since you cannot tell which numbers are even mod 3). You can then combine these conditions as follows: the numbers less than 24 which are 0 or 1 mod 3 are: $$0,1,3,4,6,7,9,10,12,13,15,16,18,19,21,22$$ and the numbers which are 1 mod 8 are: $$1,9, 17$$ the only numbers which are in both lists are 1 and 9, therefore these are the only numbers which may be squares modulo 24.

-

Since we are told that x is odd, then there are only six cases of congruence: $x\equiv\pm1,\pm3,\pm5,\pm7,$ $\pm9,\pm11\mod 24$. In the first case, $x^2\equiv1^2\equiv1\mod24$. In the second, $x^2\equiv3^2\equiv9\text{ mod } 24$. In the third, $x^2\equiv5^2\equiv25\equiv(24+1)\equiv1\mod24$. In the fourth, $x^2\equiv7^2\equiv49\equiv(2\cdot24+1)$ $\equiv1\mod24$. In the fifth case, $x^2\equiv9^2\equiv81\equiv(3\cdot24+9)\equiv9\mod24$. In the last case, $x^2$ $\equiv11^2\equiv121\equiv(5\cdot24+1)\equiv1\mod24$. QED. Obviously, if the remainder $\mod24$ would be even, then the entire number would also be even. And the square of a negative number is the same as that of its positive counterpart. Hence the reduction in the total number of distinct cases.

-
Shouldn't this question instead be asking is $x^2$ modulo $24$ always congruent to $1$ modulo $24$ OR $9$ modulo $24$, where x is an odd integer? – Bob Nov 24 '13 at 2:06
Why stop at the integer 11? – Bob Nov 24 '13 at 2:06
@Bob He stopped at 11 because $13 \equiv -11 \mod 24$, $15 \equiv -9 \mod 24$, etc... So all the cases have been enumerated. – Dustan Levenstein Nov 24 '13 at 2:08
@DustanLevenstein I don't follow your logic here. Can you explain how all the cases have been shown? – Bob Nov 24 '13 at 2:10
@Bob: You do understand that there's a difference between $\equiv$ and =, right ? $25\equiv1\mod2$ means that $25\mod2=1$, not that $25=1$ . $x\equiv y\mod z$ means that $x\mod z=y\mod z$, not that $x=y$ . – Lucian Nov 24 '13 at 2:50

Hint: write $x = 2k+1$, where $k$ is an integer. Any odd integer can be written this way. Expand $x^2$, consider cases depending on parity of $k$.

-
If we have an odd number 11 for example, and then you square it, $11^2=121\ne1$. What is this question asking then? – Bob Nov 24 '13 at 1:45
You have to reduce it modulo $24$. $11^2 \equiv 1 (\operatorname{mod} 24)$, but it is certainly not equal. Perhaps you should avoid using equal signs when you are talking about congruence, as it may be contributing to your confusion with the concept. – NotAwake Nov 24 '13 at 1:46
I don't see how $11^2$ would be congruent to 1(mod24). I've expanded the binomial like you've said and obtained $(2k+1)^2=4k^2+4k+1$. I don't see what I need to do with this. – Bob Nov 24 '13 at 1:49
Does the +1 piece at the end tell us something? – Bob Nov 24 '13 at 1:50
Notice that $24$ divides $120$, so $121 \equiv 1 \mod 24$. – Dustan Levenstein Nov 24 '13 at 1:57

Since $x$ is of the form $2n+1$ for some $n$, we want to find: $$4n(n+1)+1 \ (\textrm{mod} 24)$$ If $n$ is divisible by $3$, we know that $4n(n+1)$ is divisible by $4n$ (and therefore by $12$, and also by $n+1$ (and therefore by $2$), so: $$3 | n \longrightarrow 4n(n+1)+1 \ (\textrm{mod} 24) \equiv 0 +1\equiv1$$

A similar analysis can be done for the cases $n\ \textrm{mod} \ 3 \equiv 1,2$.

-

Every number is equivalent mod 24 to one of 0, 1, 2, 3 ,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, or 23.

But our number $n$ is odd, so it is equivalent mod 24 to one of 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23.

Then:

$$\begin{array}{r|r|l} n & n^2 & n^2\pmod{24} \\\hline 1 & 1 & 1 \\ 3 & 9 & 9 \\ 5 & 25 & 1 \\ 7 & 49 & 1 \\\hline 9 & 81 & 9 \\ 11 & 121 & 1\\ 13 & 169 & 1 \\ 15 & 225 & 9 \\\hline 17 & 289 & 1 \\ 19 & 361 & 1 \\ 21 & 441 & 9 \\ 23 & 529 & 1 \end{array}$$

So there you go.

-
I am a big fan of this approach. However, this question in the way it is worded doesn't really seem to make sense -- it seems like part of what it is asking is implied and expected to be known. – Bob Nov 24 '13 at 2:24
I don't understand what you mean. – MJD Nov 24 '13 at 2:29
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. – Bob Nov 24 '13 at 2:36
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". 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. – MJD Nov 24 '13 at 2:44
Similarly, the notation is misleading. We write “$289\equiv 1\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 “$289\stackrel{\mod 24}\equiv 1$”. But that's not how we write it, because that's not how it has been written in the past. – MJD Nov 24 '13 at 2:46

$$x^2-1=(x-1)(x+1)$$ is the product of two consecutive even numbers. Thus, one is multiple of $4$ and the other is even. This shows that $x^2-1$is a multiple of $8$.

Moreover, one of $x-1,x,x+1$ is a multiple of three.

Case 1: $x$ is not a multiple of $3$. Then $x^2-1$ must be a multiple of three. Thus $x^2-1$ is a multiple of $24$.

Case 2: $x$ is a multiple of $3$. Then $x^2$ is a multiple of $9$. In this case we have $$9|x^2 \, \mbox{and}\, 8 |x^2-1 \,.$$ Then $$9| x^2-9 \, \mbox{and}\, 8 |x^2-9 \,.$$ thus $$72|x^2-9 \,.$$

In this case $x^2-1$ is a multiple of $72$ hence of $24$.

-