# $3^{2^n }- 1$ is divisible by $2^{n+2}$

Prove that if n is a positive integer, then $\ \large 3^{2^n }- 1$ is divisible by $\ \large 2^{n+2}$ .

For $n=1 \$ we have

$\large 3^{2^1}-1=9-1=8 \ \ an d \ \ 2^{1+2}=8$

So the statement hold for n=1.

For $n=2$ we have

$\large 3^{2^2}-1=81-1=80 \ \ and \ \ 2^{2+2}=16 \$

$Also \ \ \ 16 /80$ .

Thus the statement hold for $n=2$ also.

Let the statement hold for $n=m \$

Then $a_m=3^{2^m}-1 \ \ is \ \ divisible \ \ by \ \ b_m=2^{m+2} \$

We have to show that $b_{m+1}=2^{m+3} \$ divide $\ \large a_{m+1}=3^{2^{m+1}}-1 \$

But right here I am unable to solve . If there any help doing this ?

Else any other method is applicable also.

• Hint. $3^{2^{m+1}}-1 = (3^{2^m})^2-1=(3^{2^m}-1)(3^{2^m}+1)$ – steven gregory Sep 12 '17 at 5:22
• How to show that $\large (3^{2^m} +1 ) \$ is divisible by $\ 2 \$ ? – M. A. SARKAR Sep 12 '17 at 6:18
• because $3^{2^m}$ is an odd number. Or $3^{2^m} \equiv 1^{2^m} \equiv 1 \pmod 2$ – steven gregory Sep 12 '17 at 6:21

We can write, $$(3)^{2^n}-1$$ $$(4-1)^{2^n}-1$$ Using binomial,

$$=\color{red}{\binom{2^n}{0}}-\color{blue}{\binom{2^n}{1}4}+\color{green}{\binom{2^n}{2}4^2}-\cdots-\color{orange}{\binom{2^n}{2^n-1} 4^{2^n-1}}+\color{purple}{\binom{2^n}{2^n}4^{2^n}}-\color{red}{1}$$ 

$$\binom{n}{r}=n (r+1) \binom{n-1}{r+1}$$

$$-\color{blue}{ 2^n 2 \binom{2^n-1}{2}4}+\color{green}{2^n 3\binom{2^n-1}{3}4^2}-\cdots+\color{magenta}{2^n (2^n-1) \binom{2^n-1}{2^n-1}4^{2^n-2}} -\color{orange}{2^n 4^{2^n-1}} +\color{purple}{4^{2^n}}$$  $$- \color{red}{2^{n+2}}(-\color{blue}{2\binom{2^n-1}{2}}+\color{green}{3\binom{2^n-1}{3}4}-\cdots+\color{magenta}{(2^n-1)\binom{2^n-1}{2^n-1}4})-\color{orange}{2^n4^{2^n-1}}+\color{purple}{4^{2^n}}$$  $$\color{red}{2^{n+2}}(-\color{grey}{\binom{2^n-1}{1}}+\color{blue}{2\binom{2^n-1}{2}}-\color{green}{3\binom{2^n-1}{3}4}-\cdots-\color\magenta{(2^n-1)\binom{2^n-1}{2^n-1}4^{2^n-2}}-\color{grey}{2^n +1})-\color{orange}{2^n4^{2^n-1}}+\color{purple}{4^{2^n}}$$  $$\color{red}{2^{n+2}}(f'(4)-\color{grey}{2^n+1})-\color{orange}{2^n4^{2^n-1}}+\color{purple}{4^{2^n}}$$

(f(x) being $=(x-1)^{2^n-1}$) Hence$$f'(4)=(2^n-1)3^{2^n-2}$$

$$\color{red}{2^{n+2}}((2^n-1)3^{2^n-2}+\color{grey}{2^n+1}-\color{orange}{4^{2^n-3}}+\color{purple}{2^{2^n}2^{2^n-n-2}})$$

 $$\color{red}{2^{n+2}}C$$ 

Hence.......

OR

$$3^{2^{m+1}}-1$$ $$3^{2^m×2}-1$$ $$(3^{2^m}-1)(3^{2m}+1)$$ $$k×2^{m+2} ×(3^{2^m}-1+2)$$

$$2^{m+2} ×k× (k2^{m+2}+2)$$$$2^{m+2} ×k× 2×(k2^{m+1}+1)$$$$2^{m+3} ×\gamma$$

• You'll still need to prove that the power of $2$ in $4^k$ is no less than that in $k!$, which is not so obvious(compared to the original question). – Cave Johnson Sep 12 '17 at 5:47
• $\displaystyle\color{green}{\frac{2^{n+2}(2^n-1)}{2!}}$ is not an integer multiple of $2^{n+2}\,$. That term should rather be $\displaystyle\color{green}{\frac{2^{n+\color{red}{4}}(2^n-1)}{2!}}\,$, instead, but technically you do have to prove that all other terms are integer multiples of $2^{n+2}\,$ as well. – dxiv Sep 12 '17 at 5:48
• I edited that thing – neonpokharkar Sep 12 '17 at 5:51
• My previous comment stands as written. You can't just hand-wave all remaining $\;\cdots\;$ terms as integer multiples of $\,2^{n+2}\,$ without backing that assertion up somehow. – dxiv Sep 12 '17 at 6:19
• Ok Ok i am proving it – neonpokharkar Sep 12 '17 at 6:21

You could apply [Lifting the Exponent lemma][1]

[1]: https://brilliant.org/wiki/lifting-the-exponent/ for the case $p=2$ and obtain $v_2(3^{2^n} - 1) = v_2(3-1)+v_2(2^n)+v_2(3+1)-1 = n+2$

$$\begin{array}{} &3^{2^m} -1 &=x 2^{m+2} & \text{assumed and checked by } m=1 \text{with x odd}\\ &3^{2^{m+1}} -1 &= 3^{2 \cdot 2^m} -1 & \text{general step in induction} \\ & &= (3^{2^m})^2 -1\\ & &= (3^{2^m} -1)(3^{2^m} +1) \\ & &=x 2^{m+2}(3^{2^m} +1) & \text{ with x odd }\\ & &=x 2^{m+2}(3 \cdot 3^{2^m-1} +1) \\ & &=x 2^{m+2}(2 \cdot 3^{2^m-1}+ (3^{2^m-1}+1)) \\ & &=x 2^{m+2}(2 \cdot 3^{2^m-1}+ (3+1) \cdot y) & \text{by 3^{2w+1}+1}=(3+1)\cdot y\\ & &=x 2^{m+2}2 \cdot (3^{2^m-1}+ 2 y) &\text{by factoring out }2\\ & &=x 2^{m+3} z &\text{with x and z odd}\\ \end{array}$$ $$\begin{array}{l}\implies 2^{m+3} \mid 3^{2^{m+1}}-1 & \phantom {\text{yxcyxcyyxcyxcycyxcyc}}& \text{induction successful, proof complete} \end{array}$$

The Carmichael function $\lambda(2^{n+2})=2^n$ for positive $n$. Thus for any odd number $k$, $k^{2^n}\equiv 1 \bmod 2^{n+2}$ and thus $2^{n+2}$ divides $k^{2^n}- 1$.