Prove that 3 is not a quadratic residue of $2^n-1$ when n is odd.

Question

The problem is to show that 3 not a quadratic residue mod $2^n-1$ when n is odd and $n>\geq 3$. As for now I can see that $2^n-1$ is $1$ mod $3$ which means that $2^n-1$ has an even number of prime factors of the form $3k+2$. However, I can't see if this is useful. Any suggestions on how to approach the problem?

Answer 1

First let us write as $\cal{P}$ the set of primes $p$ dividing $2^n-1$. Next, let us state quadratic reciprocity [with one of the primes fixed at $3$ and the other prime as $p$]:

$$\left(\frac{p }{ 3}\right) \left(\frac{3}{p}\right) = -1^{\frac{p-1}{2}}.$$

So from this we note the following:

Lemma 1: Writing as $\cal{P}$ the set of primes $p$ dividing $2^n-1$:

• (i) The integer $3$ is not a quadratic residue mod $2^n-1$ iff there is a prime $p \in \cal{P}$ such that $3$ is not a quadratic residue in $\mathbb{Z}/p\mathbb{Z}$.

• (ii) Let $p$ be a prime satisfying both $p \equiv_4 3$ and $p \equiv_3 1$. Then $3$ is not a quadratic residue in $\mathbb{Z}/p\mathbb{Z}$. Thus, the integer $3$ is not a quadratic residue mod $2^n-1$ if there is a prime $p \in \cal{P}$ that satisfies both $p \equiv_4 3$ and $p \equiv_3 1$.

• (iii) Let $p$ be a prime satisfying both $p \equiv_4 1$ and $p \equiv_3 2$. Then $3$ is not a quadratic residue in $\mathbb{Z}/p\mathbb{Z}$. Thus, the integer $3$ is not a quadratic residue mod $2^n-1$ if there a prime $p \in \cal{P}$ that satisfies both $p \equiv_4 1$ and $p \equiv_3 2$.

We now use Lemma 1 to finish.

Now, note that $2^n-1 \equiv_4 3$, so there is an odd number of primes $p \in \cal{P}$ satisfying $p \equiv_3 4$.

Next note that $2^n-1 \equiv_3 1$ so there are an even number [perhaps zero] of primes $p \in \cal{P}$ that satisfy $p \equiv_2 3$.

Suppose on the one hand that there is a $p \in \cal{P}$ such that $p \equiv_4 3$ and $p \equiv_3 1$. Then finish using Lemma 1 (ii).

Suppose on the other hand that there are no primes $p \in \cal{P}$ such that $p \equiv_4 3$ and $p \equiv_3 1$. Then every prime $p \in \cal{P}$ satisfying $p \equiv_3 4$ [and there is at least one such $p$] satisfies $p \equiv_3 2$, so there are a nonzero number of primes $p \in \cal{P}$ satisfying $p \equiv_3 2$. Furthermore, there exists a prime $p \in \cal{P}$ satisfying $p \equiv_3 2$ and $p \equiv_4 1$. [Indeed, if every prime $p$ satisfying $p \equiv_4 3$ also satisfies $p \equiv_3 2$, then the number of primes $p \in \cal{P}$ satisfying $p \equiv_3 2$ is at least the number of primes $p$ satisfying $p \equiv_4 3$. But there is an even number of primes $p$ satisfying $p \equiv_3 2$ and an odd number primes $p \in \cal{P}$ satisfying $p \equiv_4 3$, so there must be more primes $p \in \cal{P}$ satisfying $p \equiv_3 2$, than there are primes $p$ satisfying $p \equiv_4 3$, so there is at least one prime $p \in \cal{P}$ satisfying $p \equiv_3 2$ and $p \equiv_4 1$ after all.] So then finish using Lemma 1 (iii).

---

You could also conclude directly from Lemma 1 that $\left(\frac{3}{p}\right)$ is $1$ only if $p \equiv_{12} \pm 1$. But then one can also clearly check that $2^n-1 \equiv_{12} 7$ for odd $n \ge 3$. Now, for any set $Q$ of primes $q$ satisfying $q \equiv_{12} \pm 1$ and any set of nonnegative integral exponents $\{e_q; q \in Q\}$, it is easy to see that $\prod_{q \in \cal{Q}}q^{e_q} \equiv_{12} \pm 1$. So from this one can conclude that there must be a $p \in \cal{P}$ that satisfies $p \not \equiv_{12} \pm 1$ [because $2^n-1 \not \equiv_{12} \pm 1$] so there must be a $p \in \cal{P}$ such that $\left(\frac{3}{p} \right)$ is not $1$; namely any $p \in \cal{P}$ satisfying $p \not \equiv_{12} \pm 1$. Then finish using (i) of Lemma 1.

This approach was outlined from the comments.