# Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.

I thought I would do the following ... As $n$ is not divisible by $2$ and $3$ then $$n=2k+1\;\text{or}\\n=3k+1\;\text{or}\\n=3k+2\;\;\;\;$$for some $n\in\mathbb{N}$. And then make induction over $k$ in each case.$$24\mid (2k+1)^2-1\;\text{or}\\24\mid (3k+1)^2-1\;\text{or}\\24\mid (3k+2)^2-1\;\;\;\;$$This question is in a text of Euclidean Division I'm reviewing, and I wonder if there is a simpler, faster, or direct this way.

• if 2 does not divide n and 3 does not divide n then 6 cannot divide n. Therefore to synthetize we look for n=6k+something where that something is not divisible by 2 or 3 leaving as only possibilities 1 and 5. Then without the need for induction you can substitute this n and factorize such as to show that the number is indeed divisible by 24. Commented Nov 28, 2013 at 21:28
• This follows immediately from: math.stackexchange.com/questions/578749/… Commented Nov 28, 2013 at 21:33
• Commented Nov 29, 2013 at 4:05

$n^2-1=(n-1)(n+1)$

$n$ is not even so $n-1$ and $n+1$ are even. Also $n=4t+1$ or $4t+3$, this means at least one of $n-1$ or $n+1$ is divisible by 4.

$n$ is not $3k$ so at least one of $n-1$ or $n+1$ must be divisible by 3.

So $n^2-1$ has factors of 4, 2(distinct from the 4) and 3 so $24|n^2-1$

Edit: I updated my post after arbautjc's correction in his comment.

• Actually, it works, because not only $n-1$ and $n+1$ are even, but one is a multiple of 4. Otherwise, you would have only proved $12\,|\,n^2-1$. I'll upvote in few hours, after vote blocking ;-) Very nice proof, by the way. Commented Nov 28, 2013 at 21:21
• Yes you are right, let me see if I can fix it. Commented Nov 28, 2013 at 21:22
• I appreciate any improvement in the wording of the solution. Commented Nov 28, 2013 at 21:34

If n is neither divisible by 3 nor by 2 then it is of the form $n = 6k \pm 1$. Then we get $$(6k \pm 1)^2 - 1 = 36k^2 \pm 12 k \equiv 0 \pmod {24}$$ showing the divisibility

If $n$ is not divisible by either $2$ or $3$, then it must satisfy either $n \equiv 1 \pmod{6}$ or $n \equiv 5 \pmod{6}$. This can be used directly.

• Yes, but I would like to use the concepts of Euclidean division. Commented Nov 28, 2013 at 21:17

The long way to get at the same answer is to simply look at the squares modulo 24. Not divisible by 2 or 3 leaves us 1, 5, 7, 11, 13, 17, 19, 23. Obviously $1^2 \equiv 1 \pmod{24}$ and $5^2 = 25 \equiv 1 \pmod{24}$. Likewise $7^2 = 2 \times 24 + 1$.

This leaves five cases you can check easily enough, though this is not so much for your benefit but for those who come across this question through the duplicate.

Of course I don't recommend this approach if you're dealing with numbers greater than 24, even if just by a little bit.