Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks

share|improve this question
add comment

4 Answers 4

up vote 6 down vote accepted

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.

share|improve this answer
add comment

Look at the possible remainders when $3$ divides an integer. The set of possible remainders when a number is divided by $3$ is $\{0,1,2\}$. You are given that $3$ does not divide $n$. Hence, the possible remainders when $3$ divides $n$ are $1$ and $2$. Hence $n=3k+1$ or $n=3k+2$. Now look at the square of the two cases.

If $n=3k+1$, then $n^2 = 9k^2 + 6k + 1 = 3(3k^2+2k) + 1 \Rightarrow (n^2-1) = 3(3k^2+2k)$

If $n=3k+2$, then $n^2 = 9k^2 + 12k + 4 = 3(3k^2+4k+1) + 1 \Rightarrow (n^2-1) = 3(3k^2+4k+1)$

Hence in both the cases $3|(n^2-1)$.

share|improve this answer
add comment

Case: $n = 1 \pmod{3}$. Then $n^2 = 1 \pmod{3}$
i.e. $n^2 - 1 = 0 \pmod{3}$
i.e. $3$ divides $n^2 - 1$.

Case: $n = 2 \pmod{3}$. (The next lines are identical to the above, since 2^2 = 4 = 1 (mod 3))

share|improve this answer
add comment

HINT $\ $ If not, and $\rm\ n-1,\ n,\ n+1 \ $ is the least consecutive triple of naturals all not divisible by $3$ then $\rm\ n-2,\ n-1,\ n\ $ would be a smaller triple (since $\rm\ 3\ |\ n-2\iff 3\ |\ n+1)\:,\:$ a contradiction. The case analysis arises when showing that the leftshifted sequence remains nonnegative (and also we use sign case analysis since we exploit $\rm\ n\to -n\ $ symmetry to reduce to the nonnegative case).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.