Prove that 3 is not a quadratic residue of $2^n-1$ when n is odd. 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?
 A: 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.
