8
$\begingroup$

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

I have tried many things, but nothing worked.

$\endgroup$
  • $\begingroup$ n needs to be an integer? $\endgroup$ – Fawad Feb 5 '17 at 20:53
  • 2
    $\begingroup$ Firstly $n$ is odd because if $n$ is even, then $3\mid 2^n-1\mid 3^n-1$, contradiction. $\endgroup$ – user236182 Feb 5 '17 at 20:56
  • 2
    $\begingroup$ 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. $\endgroup$ – TastyRomeo Mar 7 '17 at 8:57
5
$\begingroup$

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

\begin{equation} 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}) \end{equation}

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

\begin{equation} (\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 \end{equation}

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Julian Mejia May 26 at 16:38
  • $\begingroup$ 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? $\endgroup$ – Zeno May 26 at 16:40
  • $\begingroup$ Oh, nvm no typo. I just understood what you wrote. And yes, you are right, quadratic reciprocity still holds in that case. $\endgroup$ – Julian Mejia May 26 at 17:03
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.