Track / Stage 4 / 195 of 340 #935 of 2444

Problem 935

AMC 12 late, AIME early

Number theory Difficulty 4.8 Prove it Berkeley Math Circle: Monthly Contest 1 · United States

Let $n$ be an odd positive integer not divisible by $3$ . Show that $n^{2}-1$ is divisible by $24$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

We will show it is divisible by $8$ and $3$ . Since the least common multiple of $8$ and $3$ is $24$ , this implies the result.

We factor $n^{2}-1 = (n-1)(n+1)$ .

To show divisibility by $8$ , note that $n-1$ and $n+1$ are two consecutive even integers. Among any two consecutive even integers, one of them must be divisible by $4$ ; the other one is divisible by $2$ by definition, so their product is divisible by $8$ .

To show divisibility by $3$ , note that $\{n-1, n, n+1\}$ form three consecutive integers. Thus at least one of them is divisible by $3$ . We assumed $n$ was not divisible by $3$ , so it must be either $n-1$ or $n+1$ , hence their product is divisible by $3$ as well.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.