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.

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 \}$

share|improve this question
    
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
3  
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

6 Answers 6

up vote 16 down vote accepted

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

share|improve this answer
6  
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. –  Nikhil Bellarykar Jan 3 '12 at 15:12

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.

share|improve this answer

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$

share|improve this answer

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.

share|improve this answer

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...

share|improve this answer
    
Very nice elementary approach. +1 –  Patrick Da Silva Jan 4 '12 at 13:16

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$.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.