Question

Prove that for any integer n such that n≡2 mod 3 , n^k≡1 or 2 (mod 3) , where k∈N

Answer 1

Answer on Question #71820 – Math – Discrete Mathematics

Question

Prove that for any integer $n$ such that $n \equiv 2 \mod 3$, $n^k \equiv 1$ or 2 (mod 3), where $k \in \mathbb{N}$

Solution

From $n \equiv 2 \mod 3$ we can write $n$ as $n = 3t + 2$, where $t$ is integer number.

Consider

$$n^k = (3t + 2)^k.$$

Using formula

$$(a + b)^k = \sum_{i=0}^{k} \binom{k}{i} a^{k-i} b^i,$$ $$(3t + 2)^k = \binom{k}{0} (3t)^k + \binom{k}{1} (3t)^{k-1} 2^1 + \cdots + \binom{k}{k-1} (3t)^1 2^{k-1} + \binom{k}{k} 2^k.$$

Obviously,

$$\left( \binom{k}{0} (3t)^k + \binom{k}{1} (3t)^{k-1} 2^1 + \cdots + \binom{k}{k-1} (3t)^1 2^{k-1} \right) \equiv 0 \mod 3$$

because each term of the sum has a multiplier of 3.

Therefore,

$$n^k \equiv (3t + 2)^k \equiv 2^k \mod 3.$$

Using the principle of mathematical induction verify statement

$$2^k \equiv 1 \mod 3 \text{ or } 2^k \equiv 2 \mod 3 \text{ for } k \in \mathbb{N}.$$

For $k = 1$ and $k = 2$ statement is true:

$$2^1 \equiv 2 \mod 3, \quad 2^2 \equiv 4 \equiv 1 \mod 3.$$

Let the statement be true for $k = l$:

$$2^l \equiv 1 \mod 3 \text{ or } 2^l \equiv 2 \mod 3.$$

Consider $k = l + 1$.

If $2^l \equiv 1 \mod 3$ then $2^{l+1} \equiv 2 \cdot 2^l \equiv 2 \cdot 1 \equiv 2 \mod 3$.

If $2^l \equiv 2 \mod 3$ then $2^{l+1} \equiv 2 \cdot 2^l \equiv 2 \cdot 2 \equiv 4 \equiv 1 \mod 3$.

Hence the statement $2^{l+1} \equiv 2 \mod 3$ or $2^{l+1} \equiv 1 \mod 3$ is true.

According to the principle of mathematical induction the statement is true for $k \in \mathbb{N}$.

As a result, one gets $n^k \equiv 2^k \equiv 1 \mod 3$ or $n^k \equiv 2^k \equiv 2 \mod 3$.

Answer provided by https://www.AssignmentExpert.com