I have the following problem:

Given $k\geq 1$, find $h$ such that

$$2^h \frac{4^k-1}{3}-1 \equiv 0 ~(\text{mod}~3).$$

This is my attempt using the invariance of multiplication:

$$2^h \frac{4^k-1}{3} \equiv 1 ~(\text{mod}~3) \Rightarrow 2^h \frac{4^k-1}{3}\cdot3 \equiv 1\cdot3 ~(\text{mod}~3) \Rightarrow 2^h(4^k-1) \equiv 0 ~(\text{mod}~3)$$

Since I know that

$$4^k - 1 \equiv 0 ~(\text{mod}~3) $$

then I can conclude that

$$\forall k, \forall h, 2^h(4^k-1) \equiv 0 ~(\text{mod}~3)$$

Anyway, this seems really wrong, since if I choose $h=3$ and $k=1$, then I get:

$$2^3 \frac{4^1-1}{3}-1 = 7 \not\equiv 0 ~(\text{mod}~3).$$

What's wrong with this proof?

  • $\begingroup$ You cannot multiply by 3, it's part of the zero equivalence class. $\endgroup$ – David Peterson Oct 18 '14 at 18:56
  • $\begingroup$ what you did was right, but you're assuming you have an if and only if. clearly $3n$ is always $0$ mod 3, so you can't conclude absolutely anything about $n$ from that fact $\endgroup$ – Jorge Fernández Hidalgo Oct 18 '14 at 18:56
  • $\begingroup$ oK! So what can I do to find $h$? $\endgroup$ – the_candyman Oct 18 '14 at 19:01


$\dfrac{4^k-1}3=1+4+4^2+\dots+4^{k-1}=k \pmod 3$ and using $2^h=(-1)^h$ you get $(-1)^h=k \pmod 3$ for solutions.


$$ \begin{align} \frac{(1+3)^k-1}{3} &=\frac{\left[\binom{k}{0}3^0+\binom{k}{1}3^1+3^2\sum\limits_{j=2}^k\binom{k}{j}3^{j-2}\right]-1}{3}\\ &=\binom{k}{1}+3\sum\limits_{j=2}^k\binom{k}{j}3^{j-2}\\ &\equiv\binom{k}{1}\pmod3 \end{align} $$ Therefore, $$ 2^h\frac{(1+3)^k-1}{3}-1\equiv0\pmod3 $$ is the same as $$ 2^hk\equiv1\pmod3 $$ which is solvable when $k\not\equiv0\pmod3$ and then $$ h=\left\{\begin{array}{} 0&\text{if }k\equiv1\pmod3\\ 1&\text{if }k\equiv2\pmod3\\ \end{array}\right. $$ satisfies the equation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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