Square Modulo 24 of Odd Integer Not Divisible by 3/Proof 2
Jump to navigation
Jump to search
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
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$