Croatian Mathematical Competitions

We will prove that for all positive integers of the form $n = 2^{2p} - 1$ (where $p > 3$ is a prime number) $n \mid 2^n - 8$ and $n$ has at least three distinct prime divisors.

Since $2^n - 8 = 8(2^{n-3} - 1)$, to prove $n \mid 2^n - 8$ it is sufficient to prove
$$2^p \mid n - 3.$$
Namely, in this case $n - 3 = 2pk$ for some positive integer $k$, so
$$2^{n-3} - 1 = 2^{2pk} - 1 = (2^{2p})^k - 1 = (2^{2p} - 1)(2^{2p(k-1)} + 2^{2p(k-2)} + \dots + 2^{2p} + 1),$$
i.e. $2^{2p} - 1 = n \mid 2^{n-3} - 1 \Rightarrow n \mid 2^n - 8$.

By Fermat's little theorem we have $2^p \equiv 2 \pmod p$, so it follows that
$$n - 3 = 2^{2p} - 4 = (2^p)^2 - 4 \equiv 2^2 - 4 = 0 \pmod p.$$
Obviously $n-3$ is an even number and since $2$ and $p$ are relatively prime we conclude that
$$n - 3 = 2^{2p} - 4 \equiv 0 \pmod{2p}.$$

Now we will show that $n$ has at least three distinct prime divisors. Note that
$$n = 2^{2p} - 1 = (2^p - 1)(2^p + 1).$$
Since $2^p - 1$ and $2^p + 1$ are two consecutive odd numbers they are relatively prime, so they don't have any common prime divisor. $2^p - 1$ has at least one prime divisor so it is sufficient to show that $2^p + 1$ has at least two distinct prime divisors. Since $p > 3$ we can write $p = 3k + r$, where $k \ge 1$ and $r \in \{1, 2\}$.

Since $p$ is odd, we have:
$$2^p + 1 \equiv (-1)^p + 1 = -1 + 1 = 0 \pmod{3}$$
and
$$2^p + 1 = (2^3)^k \cdot 2^r + 1 \equiv (-1)^k 2^r + 1 \neq 0 \pmod{9}.$$
We have proved that $2^p + 1$ is divisible by $3$, but it's not divisible by $9$ which means that $2^p + 1$ can not be a power of $3$, i.e. $2^p + 1$ has at least one prime divisor different from $3$.

This proves the assertion of the problem.