Square Modulo 24 of Odd Integer Not Divisible by 3
Theorem
Let $a \in \Z$ be an integer such that:
- $2 \nmid a$
- $3 \nmid a$
where $\nmid$ denotes non-divisibility.
Then:
- $a^2 \equiv 1 \pmod {24}$
That is:
- $24 \divides \paren {a^2 - 1}$
where $\divides$ denotes divisibility.
Proof 1
Let $a$ be as asserted.
We have that:
- $2 \nmid a$
From Odd Square Modulo 8:
- $a^2 \equiv 1 \pmod 8$
which means:
- $8 \divides a^2 - 1$
We also have that:
- $3 \nmid a$
From Square Modulo 3: Corollary 3:
- $3 \divides a^2 - 1$
We have from Coprime Integers: $3$ and $8$ that:
- $3 \perp 8$
where $\perp$ denotes coprimality.
As we have that:
- $8 \divides a^2 - 1$
and:
- $3 \divides a^2 - 1$
it follows from Product of Coprime Factors that:
- $24 \divides a^2 - 1$
Hence the result.
$\blacksquare$
Proof 2
Let $a$ be as asserted.
We have that:
- $3 \nmid a$
which means that either of the following hold:
\(\ds \exists k_1 \in \Z: \, \) | \(\ds a\) | \(=\) | \(\ds 3 k_1 + 1\) | |||||||||||
\(\ds \exists k_2 \in \Z: \, \) | \(\ds a\) | \(=\) | \(\ds 3 k_2 + 2\) |
Suppose $a = 3 k_1 + 1$.
As $a$ is odd, it must be the case that $k_1$ is even.
Hence:
\(\ds \exists k \in \Z: \, \) | \(\ds a\) | \(=\) | \(\ds 3 \paren {2 k} + 1\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds a^2\) | \(=\) | \(\ds \paren {6 k + 1}^2\) | |||||||||||
\(\ds \) | \(=\) | \(\ds 36 k^2 + 12 k + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 12 \paren {3 k^2 + k} + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 12 k \paren {3 k + 1} + 1\) |
If $k$ is even, then:
- $\exists r \in \Z: k = 2 r$
Hence:
- $a^2 = 24 r \paren {3 k + 1} + 1$
and so:
- $24 \divides a^2 - 1$
If $k$ is odd, then $3 k + 1$ is even, and:
- $\exists r \in \Z: 3 k + 1 = 2 r$
Hence:
- $a^2 = 24 r k + 1$
and so:
- $24 \divides a^2 - 1$
$\Box$
Suppose $a = 3 k_2 + 2$.
As $a$ is odd, it must be the case that $k_2$ is also odd.
Hence:
\(\ds \exists k \in \Z: \, \) | \(\ds a\) | \(=\) | \(\ds 3 \paren {2 k + 1} + 2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds a^2\) | \(=\) | \(\ds \paren {3 \paren {2 k + 1} + 2}^2\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {6 k + 5}^2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 36 k^2 + 60 k + 25\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 12 \paren {3 k^2 + 5 k} + 25\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 12 k \paren {3 k + 5} + 25\) |
If $k$ is even, then:
- $\exists r \in \Z: k = 2 r$
Hence:
\(\ds a^2\) | \(=\) | \(\ds 24 r \paren {3 k + 5} + 25\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 24 \paren {r \paren {3 k + 5} + 1} + 1\) |
and so:
- $24 \divides a^2 - 1$
If $k$ is odd, then $\paren {3 k + 5}$ is even, and:
- $\exists r \in \Z: 3 k + 5 = 2 r$
Hence:
\(\ds a^2\) | \(=\) | \(\ds 24 k r + 25\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 24 \paren {k r + 1} + 1\) |
and so again:
- $24 \divides a^2 - 1$
$\Box$
All cases have been accounted for.
Hence the result.
$\blacksquare$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $7$