<s>[INST] For every $n$ and $x$ there is an $m$ such that $3^n\mid 4^mx + (4^m-1)/3$ I am interested to know if for any $x\in 2\mathbb N +1$ and $n\in\mathbb N$ there exists a number $m\in \mathbb N\cup\{0\}$ such that
$3^n$ divides $$4^mx + \frac{4^m-1}{3}$$
I can easily show this if $x\equiv 1 \mod 3^n$, however I don't seem to be able to use this extra information to do it for any $x$. Here is the proof for $x\equiv 1\mod 3^n$:
Proof is by induction. If $n=1$, we can write $x=3y+1$ then with $m=2$ we have $3$ divides $4^2(3y+1)+(4^2-1)/3 = 21+3(16y)$. Let $n>1$ and suppose that the result is true for this $n$. Suppose also that $x\equiv 1 \mod 3^{n+1}$, then clearly $x\equiv 1 \mod 3^n$ so there is an $m\in\mathbb N$ such that $3^n$ divides  $4^mx + \displaystyle\frac{4^m-1}{3}$. We can write $x=3^{n+1}y+1$ and so $3^n$ divides 
$$4^m(3^{n+1}y+1) + \frac{4^m-1}{3}$$
so because of the formula for geometric series, $3^n$ divides $\frac{4^{m+1}-1}{3}$.
Consider now the fact that
$$4^{3(m+1)}-1 = (4^{2(m+1)}+4^{m+1} + 1)(4^{m+1}-1)$$
The left factor on the right hand side is a multiple of 3 (because $4 \equiv 1 \mod 3$), and so $3^{n+1}$ divides 
$$\frac{4^{3(m+1)}-1}{3}$$
Thus $3^{n+1}$ divides 
$$4^{3(m+1)-1}(3^{n+1}y+1) + \frac{4^{3(m+1)-1}-1}{3}$$
so we choose $3m+2$ for $x$.
Maybe someone can use this to help me figure this out for any $x$ independent of $n$?
 [/INST] Generalizing slightly: Let $p$ be an odd prime (in the question we have $p=3$) and $n$ be a positive integer. We want to show that for every integer $x$ there exists an $m\in\mathbb N$ such that
$$p^n\mid (p+1)^mx+\dfrac{(p+1)^m−1}p$$
We multiply this by $p$ on both sides to get
$$p^{n+1}\mid (p+1)^m(px+1)−1$$
or in other words
$$\tag{*} (p+1)^m(px+1)\equiv 1\pmod{p^{n+1}}.$$
At this stage we can see that the question's restriction to odd $x$ doesn't matter -- an $m$ that works for some $x$ will also work for $x+p^n$, so if there are $m$ for every odd $x$, there is also an $m$ that works for every even $x$, namely the one we get for $x+p^n$.
On the other hand, the values of $px+1$ for $x\in\{0,1,2,\ldots,p^n-1\}$ are all coprime to $p^{n+1}$ and different modulo $p^{n+1}$. In fact they are exactly the elements of a group $G$ of order $p^n$ under multiplication modulo $p^{n+1}$.
What we need is that $(px+1)^{-1}$ is always a power of $p+1$, which is the same as saying that $p+1$ generates $G$.
The multiplicative group modulo a power of an odd prime is always cyclic, and therefore in particular its subgroup $G$ is cyclic. And in a cyclic group of order $p^n$, everything that is not a generator is the $p$th power of something. However, by the binomial theorem,
$$(px+1)^p = 1+\binom{p}{1}px+(\text{terms involving }p^2) \equiv 1 \pmod{p^2} $$
So in particular $p+1$ cannot be a $p$th power, so it does generate $G$, and therefore $(px+1)^{-1}$ is always a power of $p+1\pmod{p^{n+1}}$.

An aside: The case where $x\equiv 1\pmod{p^n}$ (which was proved in the question) can be handled directly from $\text{(*)}$. Namely if $x=p^nj+1$ then $px+1=p^{n+1}j+p+1\equiv p+1\pmod{p^{n+1}}$, and then simply because $p+1$ is coprime to $p^{n+1}$, some positive power of it must be $1$ modulo $p^{n+1}$.
</s>