How prove such that $2^n-8$ is divisible by $n$, and $n$ has least three distinct prime factors.

Question

Prove that there are infinitely many postive integers $n$ such that $2^n-8$ is divisible by $n$, and $n$ has least three distinct prime factors.

I only find infinitely many postive integers $n$ such that $2^n-8$ is divisible by $n$,

such $n=3p$, use $$2^{3p}-8=8(2^{3(p-1)}-1)$$ Use Fermat theorem we have $$2^{p-1}-1\equiv 0\pmod p$$ and it is clear $$2^{3p}-8\equiv (-1)^{3p}-2\equiv 0\pmod 3$$ But this example is not such $n$ has least three distinct prime factors.so How find it? Thank you

PS:This problem is from Croatia Mathematical Olympiad exam (2013 or 2014)

Answer 1

A stupid proof would be the following: use Carmichael numbers (non-prime numbers $C$ for which $a^C \equiv 1 \bmod{C}$ holds if $\gcd(a, C) = 1$).

We know the following about Carmichael numbers:

1.) They are all odd (so $\gcd(2, C) = 1$).

2.) There are infinitely many of them.

3.) They have at least three different prime factors.

In your proof set $n = 3 C$ with Carmichael number $C = 561, 1105, 1729, ...$ done!

Of course, that's overkill...

If $F$ is a Fermat pseudoprime to base 2, which has three distinct prime factors, you can set $n = 3 F$ and $n$ has the desired properties. But there are many more numbers... like $195 = 3\cdot 5\cdot 13$ with $2^n - 8 = 0\bmod{n}$...