<s>[INST] Prove that for all $n \in \mathbb N$ the quotient of $\frac{3^{2^n}}{2^n}$ is an even number. Prove that for all $n \in \mathbb N$  the quotient of
$$\frac{3^{2^n}}{2^n}$$
is an even number. Maybe we have to check a more general case, namely $\displaystyle\frac{3^k}{k}$. What would you do here? Thanks!
 [/INST] From Euler's theorem, $3^{2^{n-1}} \equiv 1 \pmod {2^n}$
Hence, $$3^{2^{n-1}} = M2^n + 1 \implies 3^{2^n} = \left(3^{2^{n-1}} \right)^2 = \left(M2^n + 1 \right)^2 = 2^n \left( M^2 2^n + 2M\right) + 1$$
Hence, $$\dfrac{3^{2^n}}{2^n} = 2 M \left(2^{n-1} M + 1 \right) + \dfrac1{2^n}$$
</s>