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

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

  • 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
    Charles, not seein$g$ how I could use Fermat's little theorem since the modulus would be still be composite.2011-04-26