Could anyone give me a hint to prove the following?
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$
This is in fact more than a hint!
Using lifting the exponent lemma (page 4, the case for $p=2$), we see that $4|9-1,$ so $v_2(9^n-1)=v_2(9-1)+v_2(n).$
Also, $v_2(n) < \sum_{k=1}^{\infty} \frac{n}{2^k}=\frac n2.$ Therefore,
$ v_2(9^n-1) < \frac n2 +3<2n,$
holds for $n \geq 3.$
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.
I think most people missed the obvious here:
$9^n-1=(3^n-1)(3^n+1)$.
Now $3^n-1$ and $3^n+1$ are two consecutive even numbers so one of them cannot be divisible by $4$.
The other is at most $3^n+1<\frac{4^n}{2}$( easy induction for $n \geq 3$.
Thus one factor is divisible by $2$, but not $4$, while the other cannot be divisible by $\frac{4^n}{2}$, hence the product is not divisible by $4^n$.
$\bf Hint:$ Use the identity $a^n-b^n=(a-b)(a^{n-1}+...+b^{n-1})$ and reduce the expression $mod(4)$.
Hint :
Try to prove using induction :
$1.$ $9^3 \not \equiv 1 \pmod {4^3}$
$2.$ suppose : $9^k \not \equiv 1 \pmod {4^k}$
$3.$ $9^k \not \equiv 1 \pmod {4^k} \Rightarrow 9^{k+1} \not \equiv 9 \pmod {4^k}$
So you have to prove :
$ 9^{k+1} \not \equiv 9 \pmod {4^k} \Rightarrow 9^{k+1} \not \equiv 1 \pmod {4^{k+1}}$