题目

Problem

(i) Prove by counter example that the statement

“If $n$ is a prime number then $3^n+2$ is also a prime number.”

is false.

(2)

(ii) Use proof by exhaustion to prove that if $m$ is an integer that is not divisible by $3$ , then

m^2-1

is divisible by $3$

(4)

解答

展开

反例只需要找一个 prime $n$ ，使 $3^n+2$ 不是 prime。选 $n=5$ 很方便。

展开

Take

\begin{align*} n=5. \end{align*}

This is prime. But

\begin{align*} 3^5+2=&\,243+2\\ =&\,245\\ =&\,5\times49. \end{align*}

So $3^5+2$ is not prime. Therefore, the statement is false.

展开

一个整数不被 $3$ 整除，只可能形如 $3k+1$ 或 $3k+2$ 。proof by exhaustion 就是把这两种情况都检查完。

展开

If $m$ is not divisible by $3$ , then either

\begin{align*} m=3k+1 \end{align*}

\begin{align*} m=3k+2, \end{align*}

where $k$ is an integer.

Case 1:

\begin{align*} m=&\,3k+1\\ m^2-1=&\,(3k+1)^2-1\\ =&\,9k^2+6k+1-1\\ =&\,9k^2+6k\\ =&\,3(3k^2+2k). \end{align*}

So $m^2-1$ is divisible by $3$ .

Case 2:

\begin{align*} m=&\,3k+2\\ m^2-1=&\,(3k+2)^2-1\\ =&\,9k^2+12k+4-1\\ =&\,9k^2+12k+3\\ =&\,3(3k^2+4k+1). \end{align*}

So $m^2-1$ is divisible by $3$ .

In all possible cases where $m$ is not divisible by $3$ , $m^2-1$ is divisible by $3$ .