Values of $n$ such that $2^{n}-1$ is divisible by 7

Question

For which values of n is $$2^{n}-1$$ divisible by 7? And why?

I've tried saying that $2^n\equiv 1 \pmod 7$ based on Little Fermat's Theorem $n$ should be a multiple of $6,$ but in fact the answer is that it should be a multiple of three and I don't know how to get there.

Answer 1

We can use modular arithmetic. First understand that $n$ is clearly an integer

$$2^n - 1 \equiv 0 \mod 7$$ $$2^n \equiv 1 \mod 7$$ $$2^{3 \cdot n/3} \equiv 1 \mod 7$$ $$8^{n/3} \equiv 1 \mod 7$$ The next step only holds if $n/3$ is an integer $$1^{n/3} \equiv 1 \mod 7$$

Therefore, if $ n \equiv 0 \mod 3$, then it is possible.

Answer 2

If $n = 3k+1 \implies 2^{3k+1} - 1= 2\cdot 2^{3k} -1 = 2(2^{3k} - 1) + 1 = 1\pmod 7$. If $n = 3k+2 \implies 2^n - 1 = 4(2^{3k} - 1) + 3 = 3\pmod 7$. Thus: $n = 3k$ is the only possibility left for $n$.

Answer 3

We know that the order of $2\bmod 7$ divides Euler's totient $\phi(7) = 7-1=6=2\cdot3$.

So the options for the order of $2$ from this are $\{1,2,3,6\}$. Only the identity and null residues have order $1$, and since $7$ is prime only $-1\equiv6$ has order $2$.

If $2$ has order $3$, there will be some number $a$ such that $a^2\equiv 2$. And such a number is easy to spot: $3^2\equiv 9\equiv 2\bmod 7$. For $2$ to have order $6$, there obviously could not be such a number since we would need $2^3 \not\equiv 1$ but we know that $a^6\equiv 1 \bmod 7$.

Direct investigation - simply computing the powers of $2\bmod 7$ - is an entirely valid method of demonstration, and for a small totient like $6$ it is also both viable and often most economical. So $\newcommand{twice}{\overset{{}_{\times 2}}{\to}} (2^0\equiv 1)\twice(2^1\equiv 2)\twice(2^2\equiv 4)\twice(2^3\equiv 8\equiv 1)$ shows the cycle of length $3$ directly.