Proving If A then B ...

Question

I have an assignment and one of the questions is this: if $n$ is a natural number, prove that if $n$ is not divisible by $2$ & $3$ (which means that it is not divisible by $6$) then $n^2 + 23$ is divisible by $24$.

Here is my approach : if $n^2 + 23$ is divisible by $24$, then for sure $n^2$ % $24$ should be equal to $1$, so I set $n=6k+1$, which is a number that is surely not divisible by $2$ or $3$, so $(6k+1)^2 $ % $ 24$ is supposed to be equal to $1$. But for some reason I just got stuck in that equation; is there something wrong that I am doing here? or is my approach right?

Answer 1

If $n$ is not divisible by $2$ or $3$, then $n=6k\color{red}\pm1$.

$(6k\pm1)^2=36k^2\pm12k+1=12k(3k\pm1)+1.$

Can you show $k(3k\pm1)$ is divisible by $2$ for all $k\in\mathbb Z$?

Answer 2

To start with you missed a case, if $n$ is not divisible by 2 or 3 then

$$n = 6k \pm 1$$

Therefore,

$$n^2 + 23 = ( 6k \pm 1 )^2 + 23 $$

$$n^2 + 23 = 36k^2 \pm 12k + 1 + 23 $$

$$ \left( n^2 + 23 \right) \mod 24 = \left( 36k^2 \pm 12k + 24 \right) \mod 24$$

Obviously, $24 \mod 24 \equiv 0$, so

$$ \left( n^2 + 23 \right) \mod 24 \equiv \left( 12 ( 3k^2 \pm k ) \right) \mod 24$$

So, if

$$ 3k^2 \pm k \mod 2 \equiv 0$$

Then,

$$ \left( n^2 + 23 \right) \mod 24 \equiv 0$$

As a bit of a hint to proving that, I've seen it that you prove for even $k$ and odd $k$.

Answer 3

Note that if $n$ is not divisible by $2$ or $3$ then $n=3k\pm 1$ for some integer $k$ and $n=2m+1$ for some integer $m$

Also we have $$n^2+23 \equiv n^2-1 =(n-1)(n+1), \mod 24$$

It suffices to show that $(n-1)(n+1) $ is a multiple of $3$ and a multiple of $8$

With $n=2m+1$ we get $(n-1)(n+1) = (2m)(2m+2)=4m(m+1)$ which is a multiple of $8$

with $n=3k\pm 1 $ we get $n^2-1\equiv 0,\mod 3$

Thus $n^2+23$ is a multiple of $24$.