Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Have you tried using the standard factorization: $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+..+a^{n-k}b^{k-1}+...+b^{k-1})$? – AQP Mar 6 '12 at 6:33
Maybe you could work in the case n=2k+1, since , when n is even, $2^n -1$ is divisible by 3, and $3^n-1$ is clearly not. – AQP Mar 6 '12 at 18:03
@ksjo3: Please tell us the source of the problem. Did you get it somewhere? Do you know there is a solution? Did you make it up yourself? – Aryabhata Mar 6 '12 at 18:04
It is an exercise in a book. I don't konw how to prove it. – ksj03 Mar 7 '12 at 2:38
@ksjo3 Please tell us which book, and where in that book. This could help people know what sort of techniques you are expected to apply to the problem. – Matthew Conroy Mar 7 '12 at 22:58

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

share|cite|improve this answer

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.

share|cite|improve this answer
You are right. Thanks for explanation. – ksj03 Mar 10 '12 at 4:53
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$. – ksj03 Mar 11 '12 at 5:25

Your Answer


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.