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.

Trying to prove that $(3^n - 2^n)/n$ is not an integer for $n\geq 2$.

Was trying something along the lines of induction with:

$3^{n+1} - 2^{n+1} = 2(3^n - 2^n) + 3^n \equiv 0 \mod (n+1)$

But that gets messy...

share|improve this question
    
I don't believe your equality as written - do you mean for the $3n$ to be $3^{n + 1}$, for example? –  Hans Parshall Apr 26 '11 at 16:01
    
Yes, fixed in the original –  user10084 Apr 26 '11 at 18:12
1  
Induction is generally bad at proving non-equalities, as opposed to equalities; what are you supposed to induct on? –  Qiaochu Yuan Apr 26 '11 at 18:18
add comment

3 Answers

up vote 15 down vote accepted

Let $p$ be the smallest prime factor of $n$ and write $n = p^k m$ where $p \nmid m$. By repeated application of Fermat's little theorem it follows that $3^n - 2^n \equiv 3^m - 2^m \equiv 0 \bmod p$. If $p = 2, 3$ then this is clearly never possible; otherwise, it follows that $\left( \frac{2}{3} \right)^m \equiv 1 \bmod p$, hence that $\gcd(p-1, m) > 1$. But this is also impossible since the prime factors of $m$ are all larger than $p$.

share|improve this answer
3  
Note: Being a homogenization of this prior problem, the proof is just a homogenization of its proof. –  Bill Dubuque Apr 26 '11 at 19:12
    
@Bill, What does that mean? Homogenization? –  quanta Apr 26 '11 at 19:21
1  
The homogenization of a polynomial $\rm\:f(x)\ =\ a_n x^n + \cdots + a_1\ x + a_0\ $ is the *homogeneous* polynomial $\rm\:y^n\ f(x/y)\ =\ a_n x^n + \cdots + a_1\ x\ y^{n-1} + a_0\ y^n\:.\:$ In particular, $\rm\: x^n - 1\ \to\ x^n - y^n\:,\:$ explaining the intimate connection between the two problems. –  Bill Dubuque Apr 26 '11 at 19:31
1  
@quanta: to be honest, I've seen this problem before. It's an old chestnut, as they say. I guess the idea is to start with the case that $n$ is prime and then see how far you can generalize that argument, picking any prime factor of $n$ at first, and then noting that you get a contradiction if the factor you chose is minimal. –  Qiaochu Yuan Apr 26 '11 at 19:38
1  
@Saurabh: repeated applications of Fermat's little theorem show that if $p-1 | n - m$ and $n, m \ge 1$ then $a^n \equiv a^m \bmod p$. Now let $n = p^k m$ as above. We have $n - m = (p^k - 1) m$ which is divisible by $p-1$. –  Qiaochu Yuan Jun 10 '12 at 19:46
show 4 more comments

If $$ (3^n−2^n)/n $$ is an integer, then $$n |(3^n−2^n)$$ i.e., $$3^n−2^n=kn $$ for some integer k. $$ 3^n=2^n+kn. $$ If kn is even, then the LHS must be even, so $$2∤n.$$ $$ 2^n=3^n-kn $$ If 3|kn, then 3 will divide $$2^n$$(the LHS), so $$3∤n.$$ It implies n is co-prime to 3*2 i.e, (3*2,n)=1. $$3^n−2^n=kn =>3^n≡2^n(mod\ n)=>(3*2^{-1})^n≡1(mod\ n)$$

If p is the smallest prime that divides n, then $$(3*2^{-1})^n≡1(mod\ p)$$ If $$ ord_p(3*2^{-1})=D,\ then\ D|(p-1,n).$$ But. p being the smallest factor of n, n can not have any factor>1 common with p-1 =>D=1=>3≡2(mod p) i.e., 1|p.

Observation: If $$ ord_n(3*2^{-1})=d,$$ then the problem reduces to find d such that d|n and d|φ(n).

share|improve this answer
add comment

I would consider first the case that $n \geq 3$ is prime. Using Fermat's Little Theorem, you should be able to show $3^{n} - 2^{n} \equiv 1 \text{ (mod }n)$.

EDIT: I retract what I said about the composite case. I'll keep thinking about it.

share|improve this answer
    
@Hans: "Argue this is not the case by the induction hypothesis": I don't get it. The induction hypothesis says that $3^p-2^p$ is not divisible by $p$; why does this imply $3^{n+1}-2^{n+1}$ is not divisible by $p$? Perhaps I'm being stupid... –  TonyK Apr 26 '11 at 16:08
    
Suppose pk = n+1. Then 3^(n+1) = 3^(pk) = (3^k)^p and now you can use Fermat's little theorem. –  Charles Apr 26 '11 at 17:05
    
Equivalently, you can use the lemma that $p|n$ implies that $(a^p-b^p)|(a^n-b^n)$ (which can be shown via an easy explicit factorization - with $n=pq$, say, let $c=a^p$, $b=d^p$; then the lemma is equivalent to $(c-d)|(c^q-d^q)$ ) –  Steven Stadnicki Apr 26 '11 at 17:09
    
You don't need any induction Charle's remark above helps use fermat when n is not prime. moreover you need to notice that any power of 3 and n are coprime same goes for any power of 2 and n. At the end one could generalize the question by putting a instead of 3 and b instead of 2 with the condition that a and b are coprime. –  El Moro Apr 26 '11 at 17:20
1  
Comments are appreciated but I still don't see how this solves the problem. If anyone sees it clearly, maybe they should post an answer. –  Hans Parshall Apr 26 '11 at 17:51
show 1 more comment

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.