Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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


  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.
share|cite|improve this answer
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.

share|cite|improve this answer
"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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.