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