Take the 2-minute tour ×
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.

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|improve this question
1  
Binomial expansion? $3^{n-1}=(2+1)^{n-1}$ –  voldemort Aug 9 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 at 23:54

3 Answers 3

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.
share|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 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|improve this answer
    
"just use the binomial theorem and we get the result." - How ? –  xawey Aug 10 at 18:16
    
@xawey Hmm... not seems to be directly. Using Euler's theorem is more easier, than. –  The Great Seo Aug 11 at 1:39
    
When it comes to ELT I deal with it –  xawey Aug 11 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|improve this answer

Your Answer

 
discard

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.