4
$\begingroup$

Could anyone give me a hint to prove the following?

If $n\ge 3$, $4^n \nmid 9^n-1$

5 Answers 5

4

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.$

  • 0
    Dear Matt E, thanks for pointing it out. After adding the last statement, that $n$ one was mistakenly erased.2012-01-19
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.

  • 0
    I think your proof has an advantage though: it probably works much more often than mine if we change the numbers. The downside of my proof is that it is based on the fact that \sqrt{9}<4, so it won't work to prove something like $4^n$ doesn't divide $19^n-1$ or something like that....2012-01-20
3

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$.

1

$\bf Hint:$ Use the identity $a^n-b^n=(a-b)(a^{n-1}+...+b^{n-1})$ and reduce the expression $mod(4)$.

  • 4
    Thanks, but I don't know where to use it. Because for example with $9^n-1=(9-1)(9^{n-1}+\cdots +1)\equiv 0\pmod{4}$ and I can't see how this helps.2012-01-19
1

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}}$