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

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)

• You are really close. Continue in the same direction, where $p$ instead of being prime, is of the form $p = qrs$ where $q, r$ are prime and $s$ is odd. – Calvin Lin Jan 5 '15 at 6:43
• No,I think only consider this form,maybe not such $n|2^n-8$ – china math Jan 5 '15 at 6:47
• Some toying with Mathematica suggested to me that $n=13(2^{2^k}-1)$ might work ($13$ times the product of Fermat numbers). We easily always get divisibility by $13$, but hand calculations suggest that the rest fails when $k>4$. – Jyrki Lahtonen Jan 5 '15 at 7:24
• @CalvinLin,Haha,This is maybe use open problem? – china math Jan 5 '15 at 7:51

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}$...