# $3k-1$ can never be a power of $4$

How could we prove that $(3k-1)$ can never be any power of $4$ with $k \in \mathbb{N}$?

Please note $\mathbb{N} =\{1,2,3,\cdots \}$

• Even power of $2$? Why not just say a power of $4$? Now, $3k-1$ can never be a power of $4$ because $4^n$ is always $1$ mod $3$, not $-1$. – Eric Naslund Jan 3 '12 at 14:55
• I voted this down because it is the nth question from you without the least bit of own work shown. – t.b. Jan 3 '12 at 14:57
• @t.b.:I agree, I didn't showed any work because this is one of the nth problem/sub problem where I had no clue how to proceed, I always try to think and include my approach while asking and for this one I didn't realized that modular arithmetic is the key.Thanks. – Quixotic Jan 3 '12 at 15:07

$2 \equiv {-1} \pmod 3$ and $4^{n} \equiv 2^{2n} \equiv (-1)^{2n} \equiv 1 \pmod 3$, hence the result.

• You can also say: $4 \equiv 1 \pmod 3$, so $4^n \equiv 1$ as well. – Srivatsan Jan 3 '12 at 15:11
• ya, that is another approach as well. – nb1 Jan 3 '12 at 15:12

Congruence arithmetic is probably simplest, viz. $\rm\ mod\ 3\!:\ 4^n\ \equiv\ 1^n\ \equiv 1\ \not\equiv -1\:.\:$ If you don't know congruence arithmetic you can still understand this as follows. First, note that induction implies that any-length products of integers of the form $\rm\ 1+ 3\:m\$ have the same form since

$$\rm (1 + 3\:i)\ (1 + 3\:j)\ =\ 1 + 3\ (i + j + 3\:i\:j)$$

In particular $\rm\ 4^n = (1 + 3)^n\:$ is such a product so it must be equal to $\rm\ 1 + 3\:j\$ for some integer $\rm\:j\:.\:$ Thus $\rm\ 1 + 3\:j = 4^n = 3\:k - 1\ \Rightarrow\ 3\:(k-j) = 2\ \Rightarrow\ 3$ divides $2$, a contradiction.

The power of congruence arithmetic stems from the fact that it permits us to reuse our well-honed intuition of integer arithmetic in other arithmetic systems, bringing to the fore structural analogies. Thus the above observation about products of integers of the form $\rm\ 1 + 3\ m\$ translates to $\rm\ 1^n\equiv 1\$ in the arithmetic of integers modulo $3\:.\:$ Such common arithmetical structure will be exploited to the hilt when one studies the notion of congruences and quotient rings in abstract algebra.

The answer is simple : assume you have $3k-1 = 2^{2n} = 4^n$. Therefore, $-1 \equiv 4^n \mod 3$, but that means $-1 \equiv 1^n \equiv 1 \mod 3$. This is impossible.

Here is a "more elementary" solution: Observe that

$$4^n-1=(2^n)^2-1=(2^n-1)(2^n+1) \,.$$

Now, among any three consecutive integers you can find a multiple of $3$. Thus, one of $2^n-1, 2^n$ or $2^n+1$ must be divisible by $3$, and it cannot be $2^n$... Hence, either $2^n-1$ or $2^n+1$ is divisible by 3.

This shows that $3$ divides $(2^n-1)(2^n+1)=4^n-1$, and the rest is obvious...

• Very nice elementary approach. +1 – Patrick Da Silva Jan 4 '12 at 13:16

We have:

$4 \equiv {1} \pmod 3$

$3 \equiv 0 \pmod 3$

Therefore:

$4^n \equiv 1 \pmod 3 \ \forall n \in \mathbb N$

$3k - 1 \equiv -1 \pmod 3 \ \forall k \in \mathbb N$

So we prove:

$4^n \neq 3^k - 1 \ \forall k, n \in \mathbb N$

You could also use the binomial theorem: $4^n = (3 + 1)^n = \sum_{k=0}^n {n \choose k} 3^k1^{n-k} = \sum_{k=0}^n {n \choose k} 3^k$. Then $3$ divides each term of the sum except for the $k = 0$ term, which is just $1$. Thus $4^n$ is of the form $3j + 1$ and not $3j - 1$.