Add Me!Close Menu Navigation

Maximum Divisor

Prove that the maximum power of 2 divisor of 32n – 1 is 2n+2

We’re basically asked to show that

    \[2^{n+2} \left\| 3^{2^n}-1\right.\]

The proof of this will be done through construction, although we will assume that 2\|3^{2^n}+1 in order to complete our proof.

First, we observe that (x^2 - 1^2) = (x+1)(x-1), therefore we can rewrite 3^{2^n}-1^2 as the product of two similar terms.

(1)   \begin{align*} 3^{2^n}-1 &= (3^{2^{n-1}}+1)(3^{2^{n-1}}-1) \\ &= (3^{2^{n-1}}+1)(3^{2^{n-2}}+1)(3^{2^{n-2}}-1) \\ &= (3^{2^{n-1}}+1)(3^{2^{n-2}}+1)(3^{2^{n-3}}+1)(3^{2^{n-3}}-1) \\ & \hspace{4mm} \vdots \\ &= (3^{2^{n-1}}+1) \cdots (3^{2^{0}}+1) (3^{2^{0}}-1) \\ &= \underbrace{(3^{2^{n-1}}+1)}_{2^1\|3^{2^{n-1}}+1} \stackrel{n-1}{\ldots} \underbrace{(3^{2^{1}}+1)}_{2^1\|10} \underbrace{(4)}_{2^2\|4} \underbrace{(2)}_{2^1|2} \\ &\implies 2^{(n-1)+2+1} \| 3^{2^n}-1 \end{align*}

Hence, according to (1), it must be the case that 2^{n+2} \| 3^{2^n}-1, and therefore the maximum power of 2 that divides 3^{2^n}-1 is n+2. \blacksquare

Posted By Lee

Woosh