# Show that if $n$ is prime then $2^n - 1$ is not divisible by $7$ for any $n > 3$

Show that if $n$ is prime then $2^n - 1$ is not divisible by $7$ for any $n > 3$ Hint: Follow the example in lectures to show that $2^n -1$ is not divisible by 3.

In lectures, the example showed the $3 \mid 2^n -1 \iff n$ is even. So what I have done is said all primes $>3$ are odd $\implies n = 2k + 1$ for some $k \in \mathbb{N}$. Checking $2^1$ and $2^3$, we see that $2^{2k+1} \equiv 2 \mod 3$. From the lecture notes, I know that $2^{2k} \equiv 1 \mod 3$. I can then write

$$2^{2k + 1} = \underbrace{2^{2}\times 2^{2} \times \cdots \times 2^{2}}_\text{k times} \times 2 \equiv (1 \times 1 \times \cdots \times 1) \times 2 \equiv 2 \mod 3.$$

So we get that

$$2^{n} - 1 \equiv (2 \mod 3) - 1 \equiv 1 \mod 3$$

and so $3$ does not divide $2^n - 1$ when $n$ is odd. How does this show for it not dividing by $7$?

-

In fact we can prove more general result.

This holds true any number of the form $3k\pm1$ where $k$ is an integer

because $2^3=8\equiv1\pmod 7\implies 2^{3k}\equiv1$

$\implies 2^{3k+1}\equiv2\pmod 7\not\equiv1$

and $2^{3k-1}=2^{3(k-1)}\cdot2^2\equiv4\pmod 7\not\equiv1$

We know any prime $>3$ can be written as $6r\pm1$ (where $r$ is an integer) which is a proper subset of the numbers of the form $3k\pm1$

-

Considering $7|2^n-1$.

$2^n-1= (2-1)(2^{n-1}+2^{n-2}+ \dots1)$

$7k=(2^{3m}-1)=(2-1)(2^{3m-1}+2^{3m-2}+ \dots1)$

Let $7k=2^n-1=(2-1)(2^{n-1}+2^{n-2}+ \dots1)=(2-1)(2^{3m-1}+2^{3m-2}+ \dots1)$

$(2^{n-1}+2^{n-2}+ \dots1)=(2^{3m-1}+2^{3m-2}+ \dots1) \implies n=3m$. But $n$ is a prime greater $3$, a contradiction.

-