8
$\begingroup$

Let $n > 1$ be an integer. Then $2^n - 1\nmid 3^n - 1$. I don't know how to prove it. Can anybody help me, please?

In general, for a fixed positive integer $a > 1$, has $a^n - 1|(a +1)^n - 1$ any integer solutions?

  • 0
    If $2^n - 1|3^n - 1$, then we have $\frac{3^n - 1}{2^n - 1} = [(\frac{3}{2})^n] + 1$. But I don't know what to do next. – 2012-03-08

2 Answers 2

3

As @AQP said, if $n$ is even then $3\mid 2^n-1$ so $2^n-1\nmid 3^n-1$.

If $n=2k-1$ then $2^n-1 \equiv 1 \pmod{3}$ so $2^n-1$ is a quadratic residue mod 3.

$3(3^n-1)=3^{2k}-3$ so $2^n-1 \mid 3^n-1$ would require that $3^{2k}\equiv 3 \pmod{2^n-1} $, i.e. that 3 is a quadratic residue mod $2^n-1$.

But $2^n-1\equiv 3 \pmod{4}$ so is divisible by an odd number of primes $p\equiv 3\pmod{4}$. By quadratic reciprocity 3 cannot be a quadratic residue mod $2^n-1$, hence $2^n-1\nmid 3^n-1$.

2

The idea used below is very close to the one used by @Zander. It will not be a surprise to those who have seen my other posts that the details take longer.

If $n$ is even, then $2^n-1$ is divisible by $3$, so $2^n-1$ cannot divide $3^n-1$ unless $n=0$.

So let $n>1$ be odd. Let $p$ be a prime that divides $2^n-1$. Then since $2^n \equiv 1 \pmod{p}$, the order of $2$ modulo $p$ is odd, so $2$ is a quadratic residue of $p$. If furthermore $2^n-1$ divides $3^n-1$, then $3^n \equiv 1 \pmod {p}$, and therefore $3$ is also a quadratic residue of $p$.

The number $2$ is a quadratic residue of the odd prime $p$ iff $p\equiv \pm 1 \pmod{8}$. So $p$ must be of the shape $24k+1$, $24k+7$, $24k+17$, or $24k+23$. But by Quadratic Reciprocity, $3$ is a non-residue of $p$ if $p$ is of the shape $24k+7$ or $24k+17$. Thus it is enough to show that if $n$ is odd, then $2^n-1$ has at least one prime factor of the shape $24k+7$ or $24k+17$.

To do this, we show that not all primes in the prime factorization of $2^n-1$ can be of shapes $24k+1$ and/or $24k+23$. Suppose to the contrary that they all are. We will obtain a contradiction.

Note that $24k+1$ is congruent to $1$ modulo both $3$ and $8$, while $24k+23$ is congruent to $-1$ modulo both $3$ and $8$. Since $2^n-1$ has shape $8s-1$, its prime factorization must have an odd number of occurrences of (not necessarily distinct) primes of the form $24k+23$. But that implies that $2^n-1\equiv -1 \pmod 3$, which is not the case when $n$ is odd.

  • 0
    The assertion that $2^m−1$ cannot divide $3^n−1$ if m>1 is not correct. Let $m$ be any odd positive integer, $n = \phi(2^m - 1)$, then by Euler's Theorem we have $3^n\equiv1\mod 2^m - 1$. – 2012-03-11