# Proof that $(3^n - 2^n) / n$ is not an integer, $n \geq 2$

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

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

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

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

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

-

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.

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