Add Me!Close Menu Navigation

Why not Four?

Let n be a positive integer. Prove that 32n+1 is divisible by 2,but not by 4.

We want to show that if n > 0 \in \bf Z

(1)   \begin{align*}3^{2^n} + 1 \mod 4 \ne 0\end{align*}

By the properties of the \mod operation,

    \[a + b \mod 4 = (a \mod 4 + b \mod 4) \mod 4\]

(1) can be rewritten as

(2)   \begin{align*} 3^{2^n} + 1 \mod 4 \ne 0 &\implies (3^{2^n} \mod 4) + 1 \ne 4 \\ &\implies 3^{2^n} \mod 4 \ne 3 \end{align*}

Furthermore, we observe that 9 \mod 4 = 1 \implies 9^x \mod 4 = 1.

    \begin{align*} 9^x \mod 4 &= \left(\prod^x (9 \mod 4) \right) \mod 4 \\ &= \prod^x 1 \mod 4 \\ &= 1 \\ &\square \end{align*}

Because 3^{2^n} = 3^{2\times 2^{n-1}} = 9^{2^{n-1}}, then (2) becomes

    \[3^{2^n} \mod 4 = 9^{2^{n-1}} \mod 4 = 1 \ne 3\]

Therefore, 3^{2^n}+1 is not divisible by 4. Since 3^x is clearly odd, then 3^{2^n}+1 must be even. \blacksquare

Posted By Lee

Woosh