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

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?

-
Binomial expansion? $3^{n-1}=(2+1)^{n-1}$ – voldemort Aug 9 '14 at 23:32
I would use modular arithmetic and simplify to the best of my ability until I finally get $0$. e.g. as a starting point, $$3^{2^k} \equiv 2^{2^k} \pmod{n}$$ which would let you do some simplification to $3^{n-1} \bmod n$. – Hurkyl Aug 9 '14 at 23:54

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.
-
n is odd so n is relatively prime with 2^k. So we have $n^2^{k-1}} \equiv 1 (\mod 2^k) => n^{2^k} \equiv 1 (\mod 2^k)$ But I don't see how to show that n - 1 | 2^k – xawey Aug 10 '14 at 18:18

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.

-
"just use the binomial theorem and we get the result." - How ? – xawey Aug 10 '14 at 18:16
@xawey Hmm... not seems to be directly. Using Euler's theorem is more easier, than. – The Great Seo Aug 11 '14 at 1:39
When it comes to ELT I deal with it – xawey Aug 11 '14 at 8:25

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.

-