13
$\begingroup$

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...

  • 0
    I don't believe your equality as written - do you mean for the $3n$ to be $3^{n + 1}$, for example?2011-04-26
  • 0
    Yes, fixed in the original2011-04-26
  • 1
    Induction is generally bad at proving non-equalities, as opposed to equalities; what are you supposed to induct on?2011-04-26

3 Answers 3

15

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$.

  • 3
    Note: Being a homogenization of this [prior problem,](http://math.stackexchange.com/questions/20487/for-n-geq-2-show-that-n-nmid-2n-1/20490#20490) the proof is just a homogenization of its proof.2011-04-26
  • 0
    @Bill, What does that mean? Homogenization?2011-04-26
  • 0
    Great solution! How did you know to look at the smallest prime factor?2011-04-26
  • 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.2011-04-26
  • 0
    edit: nevermind I see it now2011-04-26
  • 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.2011-04-26
  • 0
    @Qia As I mentioned in the [prior problem](http://math.stackexchange.com/questions/20487/for-n-geq-2-show-that-n-nmid-2n-1/20490#20490), one way to view the essence of the problem is by dehomogenizing and canonicalizing, reducing to the fact that if $\rm\ A^N = 1\ $ then the order of $\rm\:A\:$ is $\ge$ the least prime factor $\rm\:P\:$ of $\rm\:N\:$. In particular this implies that $\rm\ A^{P-1}\ne 1\:,\ $ which settles the problem at hand.2011-04-26
  • 0
    @QiaochuYuan I couldn't understand your 2nd statement "By repeated application of Fermat's little theorem it follows that......".Can you insert some more steps so that I can understand.2012-06-10
  • 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$.2012-06-10
1

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).

-1

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.

  • 0
    @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...2011-04-26
  • 0
    Suppose pk = n+1. Then 3^(n+1) = 3^(pk) = (3^k)^p and now you can use Fermat's little theorem.2011-04-26
  • 0
    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)$ )2011-04-26
  • 0
    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.2011-04-26
  • 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.2011-04-26
  • 0
    Charles, not seeing how I could use Fermat's little theorem since the modulus would be still be composite.2011-04-26