BxMO/EGMO Team Selection Test

We note that $2 \nmid 2^n - 1$ for all $n > 1$, so we are looking for all $n$ such that 3, 5 and 7 are the only divisors, or $2^n - 1 = 3^a 5^b 7^c$. The answers are $n = 1, 2, 3, 4, 6$, which we easily check with outcomes 1, 3, 7, $3 \cdot 5$, $3^2 \cdot 7$.

We compute $2^2 \equiv 1 \pmod{3}$, $2^4 \equiv 1 \pmod{5}$ and $2^3 \equiv 1 \pmod{7}$, and these are the smallest positive exponents for which $2^n$ is congruent to 1. That means that $3 \mid 2^n - 1$ if and only if $2 \mid n$, that $5 \mid 2^n - 1$ if and only if $4 \mid n$ and that $7 \mid 2^n - 1$ if and only if $3 \mid n$.

If $n$ is odd, then it follows from what we said before that $2^n - 1$ has no factors 3 or 5. We distinguish two cases. If $3 \nmid n$ and $n > 1$, the prime 7 is not a divisor either, while $2^n - 1 > 1$. So $2^n - 1$ must have a prime divisor greater than 7, and these $n$ do not satisfy the conditions. The other option for odd $n$ is that $3 \mid n$. To satisfy the conditions, we must then have that $2^n - 1 = 7^c$. Thus, if $n \ge 4$ we find the relation $7^c \equiv -1 \pmod{16}$. However, this contradicts $7^c \equiv 7, 1 \pmod{16}$, because $7^2 = 49 = 3 \cdot 16 + 1$. So the only possibility is $n = 3$.

$$\begin{aligned} 2^8 - 1 &= 3 \cdot 5 \cdot 17, \\ 2^{10} - 1 &= 3 \cdot 11 \cdot 31, \\ 2^{12} - 1 &= 3^2 \cdot 5 \cdot 7 \cdot 13. \end{aligned}$$

Now suppose $n = 2m$ with $m \ge 7$, and suppose that for all even $k$ with $8 \le k < n$, the number $2^k - 1$ has a prime factor greater than 7. Consider the factorisation $2^n - 1 = 2^{2m} - 1 = (2^m - 1)(2^m + 1)$. If $m$ is odd, then the first factor has a prime factor greater than 7 since $m \ge 7 > 3$. If $m$ is even, then the same is true based on the induction hypothesis since now $8 \le m < 2m = n$. This completes the proof by induction. $\square$