If $n=3^{2^k}-2^{2^k}$, then $n\mid 3^{n-1}-2^{n-1}$

Question

Let $k \in \mathbb{N}$ and let $n=3^{2^k}-2^{2^k}$. Show that $$n\mid 3^{n-1}-2^{n-1}.$$

I have no idea how to prove this. Any suggestions?

Answer 1

Hints:

1. Show that $n-1 \equiv 0 \pmod {2^k}$. (Hint: $\phi(2^k) = 2^{k-1}$)
2. Use the fact that $3^{2^k} \equiv 2^{2^k} \pmod n$ (since $n \equiv 0 \pmod n$) and that $2^k \mid n-1$ to get the result.

Answer 2

It is enough to prove that $$2^k\mid n-1,$$ since than, using $a-b\mid a^m-b^m$, the proof is complete.

Proving $2^k\mid n-1$ is easy: just use the binomial theoremEuler's theorem and we get the result.

Answer 3

The more compact way in this kind of questions is to let $a_t = 3^t - 2^t$ and see when $n\mid m$ then $a_n \mid a_m$ for positive integers $n,m.$ If you show that $2^k \mid a_{2^k}-1$ therefore, $a_{2^k} \mid a_{a_{2^k}-1}.$

Since $\gcd(3, 2^k)=1$ then by Euler's theorem $3^{2^{k-1}} \equiv 1 \;\; \text{mod} \; 2^k$ because $\varphi(2^k)=2^{k-1}.$ Moreover,

$$a_{2^{k}}=3^{2^{k}}-2^{2^k} \equiv (3^{2^{k-1}})^2 - 0 \equiv 1 \;\; \text{mod} \; 2^k$$

which is what we wanted.