If $n\ge 3$, $4^n \nmid 9^n-1$ Could anyone give me a hint to prove the following?
If $n\ge 3$, $4^n \nmid 9^n-1$

Possibly I’m missing something obvious, but I don’t see any straightforward way to make pedja’s induction work, and ehsanmo’s answer amounts to waving a magic wand unless you sit down and go through the proof of the lifting-the-exponent lemma in the PDF to which he linked, so I’m going to offer an argument using only tools that you already have; it’s basically a special case of the lifting-the-exponent lemma adapted to your specific problem.
Let’s look at the highest power of $2$ that divides $9^n-1$; call it $t(n)$. $$9^n-1=(9-1)(9^{n-1}+9^{n-2}+\cdots+9+1)=8(9^{n-1}+9^{n-2}+\cdots+9+1)\;,$$ and each term inside the parentheses is odd, so $t(n)=3$ when $n$ is odd. In order for $9^n-1$ to be divisible by $4^n$, we must have $t(n)\ge 2n$, so we’ve at least shown that $4^n\nmid 9^n-1$ when $n\ge 3$ is odd. What about even $n$? 
Suppose that $n=2^km$, where $k\ge 1$ and $m$ is odd. Then we can factor $9^n-1$ as a difference of squares to get $$9^n-1=9^{2^km}-1=\left(9^{2^{k-1}m}+1\right)\left(9^{2^{k-1}m}-1\right)\;.$$ If $k>1$ we can keep repeating the process on the last factor until the exponent reaches $m$: 
$$\begin{align*}
9^n-1&=9^{2^km}-1\\
&=\left(9^{2^{k-1}m}+1\right)\left(9^{2^{k-1}m}-1\right)\\
&=\left(9^{2^{k-1}m}+1\right)\left(9^{2^{k-2}m}+1\right)\left(9^{2^{k-2}m}-1\right)\\
&\;\vdots\\
&=\left(9^{2^{k-1}m}+1\right)\left(9^{2^{k-2}m}+1\right)\cdots\left(9^{2^0m}+1\right)\left(9^{2^0m}-1\right)\;.\tag{1}\\
\end{align*}$$
Now $9\equiv 1\pmod 4$, so $9^a\equiv 1\pmod 4$ for all $a\ge 0$, and $9^a+1\equiv 2\pmod 4$ for all $a\ge 0$. This means that $9^a+1$ is divisible by $2$ but not by $4$ for $a\ge 0$. The total number of factors of $2$ in the product $(1)$ is therefore $k+t(m)$, where $m$ is odd. We saw in the first paragraph that $t(m)=3$ when $m$ is odd, so $$t(2^km)=k+3\;,\tag{2}$$ and it’s easy to check that $t(n)=k+3<2^{k+1}\le 2\left(2^km\right)=2n$ for $k>1$. This shows that $4^n\nmid 9^n-1$ whenever $4\mid n$, leaving only the case $n=2m$, $m$ odd. In this case $(2)$ implies that $t(n)=4$, and $4<2n$ whenever $n>2$, so we’ve now finally shown that $4^n\nmid 9^n-1$ whenever $n>2$.
The trick of writing a positive integer in the form $2^km$, where $k\ge 0$ and $m$ is odd, is worth remembering: it’s surprisingly useful.
