# Stuck with modular arithmetic problem using multiplication property

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?

• You cannot multiply by 3, it's part of the zero equivalence class. – David Peterson Oct 18 '14 at 18:56
• 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 – Jorge Fernández Hidalgo Oct 18 '14 at 18:56
• oK! So what can I do to find $h$? – 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.