# When does $2^n-1$ divide $3^n-1$?

Is it possible for some integer $n>1$ that $2^n-1\mid 3^n-1$ ?

I have tried many things, but nothing worked.

• n needs to be an integer? – Fawad Feb 5 '17 at 20:53
• Firstly $n$ is odd because if $n$ is even, then $3\mid 2^n-1\mid 3^n-1$, contradiction. – user236182 Feb 5 '17 at 20:56
• If you say you "tried many things", you should mention them! This shows effort on your part, and means others don't have to waste their time by trying the same approach. – TastyRomeo Mar 7 '17 at 8:57

I was looking for this as well, and eventually figured it out myself. So here's my solution for future reference. The short answer is, $$2^n - 1$$ never divides $$3^n - 1$$. Here's the proof, making use of the Jacobi symbol.

Assume $$2^n - 1 \mid 3^n - 1$$. If $$n = 2k$$ is even, then $$2^n - 1 = 4^k - 1 \equiv 0 \bmod 3$$. Consequently, $$3$$ must also divide $$3^n - 1$$, which is a contradiction. At the very least, we can already assume $$n = 2k + 1$$ is odd. Next, since $$3^n \equiv 1 \bmod 2^n - 1$$, from the properties of the Jacobi-symbol it follows that

$$$$1 = (\frac{1}{2^n - 1}) = (\frac{3^n}{2^n - 1}) = (\frac{3^{2k}}{2^n - 1}) \cdot (\frac{3}{2^n - 1}) = (\frac{3}{2^n - 1})$$$$

However, using Jacobi's law of reciprocity we also know

$$$$(\frac{2^n - 1}{3}) = (\frac{3}{2^n - 1}) \cdot (\frac{2^n - 1}{3}) = (-1)^{\frac{3 - 1}{2}\frac{2^n - 2}{2}} = (-1)^{2^{n - 1} - 1} = -1$$$$

The only quadratic non-residue $$\bmod 3$$ is $$2$$, therefore $$2^n - 1 \equiv 2 \bmod 3$$ or alternatively $$2^n \equiv 0 \bmod 3$$. Since this implies $$3$$ divides $$2^n$$, we again arrive at a contradiction.

• Quadratic reciprocity can only be used when they are prime numbers (i.e. your prove only works when $2^n-1$ is prime). Also, there is a typo when you apply quadratic reciprocity. – Julian Mejia May 26 at 16:38
• Jacobi has a generalized version of the law of reciprocity. It still holds as long as the two numbers are uneven and coprime. Can you be more specific about the typo? – Zeno May 26 at 16:40
• Oh, nvm no typo. I just understood what you wrote. And yes, you are right, quadratic reciprocity still holds in that case. – Julian Mejia May 26 at 17:03

When $$2^n-1$$ is a Mersenne prime,this can be resolved ( although this isn't very helpful, because we only know of 49 Mersenne primes and we don't know if they are finitely many.However, it sure is nice to know that $$2^{74,207,281} − 1$$ does not divide $$3^{74,207,281} − 1$$).

Let $$q = 2^p-1$$ be prime, therefore $$F_q$$ is a field. We know that polynomials of degree k must have at most k solutions in a field.Applying this to $$x^p-1$$, which has the solution 2 mod q, we see that this must have at most p solutions.But the set $$A=(1,2,...,2^{p-1})$$ obviously consists of different solutions, therefore it is the complete solution set. Since $$q|3^p-1$$ , we see that 3 is a solution, therefore $$3 \in A$$, but all the elements of the set $$A-3$$ have modulus less than q (obviously) and are different from 0, so no such solution may exist.

When n is a prime, but $$2^n-1$$ is not necessarily a Mersenne prime, we can employ the same reasoning for a prime divisor $$q$$ of $$2^n-1$$ :3 must be congruent to some power of 2 modulo q. Therefore q divides a number of the form $$2^i-3$$.I don't know what the prime divisors of the sequence $$2^i-3$$ are, but a very weak corollary is this : either $$3$$ or $$6$$ is a quadratic residue mod q, therefore, by toying with quadratic reciprocity a bit, we get this : $$q \equiv \pm 1, \pm 5, \pm 13\pmod{24}$$.So when n is prime, the prime divisors of $$2^n-1$$ must be of this specific form (note that this is a very weak corollary).