[Math] Using proof by cases — stuck

discrete mathematicslogic

Let $n$ be an integer.
If $3$ does not divide $n$, then $3$ divides $n^2 – 1$.

I'm trying to prove this using a "proof by cases". However, I'm lost as to how to start. I thought proof by cases started by making a logical expression, but I can't seem to find the right one.


Best Answer

If you want to do a proof by cases, the first step is to identify a complete list of possible cases (in principle, they need not be mutually exclusive, but in practice they usually are).

Once you have your completely list of possible cases, then you examine each case in turn. If in all cases you get the desired conclusion, then the conclusion holds in all cases.

So, here you want to show that if $3$ does not divide $n$, then $3$ divides $n^2-1$, and you want to do it "by cases". So, what is the complete list of "cases" that covers all possibilities? "Cases" for what or whom?

Since the only thing that can change from one instance of this problem to the other is $n$, then the cases will refer to $n$. There are many ways to break up all possible $n$ into cases. The simplest here, because you are dealing with divisibility by $3$, is to consider the possible remainders when you divide $n$ by $3$.

So what are all the possible situations when you divide $n$ by $3$? You can get a remainder of $0$, a remainder of $1$, or a remainder of $2$. So we go through each case in turn.

So, suppose that $3$ does not divide $n$; we want to conclude that $3$ divides $n^2-1$.

CASE 1: The remainder is $0$. This case is impossible, because in this case $3$ divides $n$, and we are assuming that $3$ does not divide $n$. So we can discard this case.

CASE 2: The remainder is $1$. Then $n$ can be written as $n=3k+1$; square both sides, subtract $1$, see what happens.

CASE 3: The remainder is $2$. Then $n$ can be written as $n=3k+2$; <continue here>.

Since, in all cases we get the conclusion we want, the conclusion holds for all $n, as desired.

Related Question