5
$\begingroup$

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

Answer:

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.

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

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

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Cave Johnson Sep 12 '17 at 5:47
  • $\begingroup$ $\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. $\endgroup$ – dxiv Sep 12 '17 at 5:48
  • $\begingroup$ I edited that thing $\endgroup$ – neonpokharkar Sep 12 '17 at 5:51
  • $\begingroup$ 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. $\endgroup$ – dxiv Sep 12 '17 at 6:19
  • $\begingroup$ Ok Ok i am proving it $\endgroup$ – neonpokharkar Sep 12 '17 at 6:21
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.