8
$\begingroup$

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)

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Calvin Lin Jan 5 '15 at 6:43
  • $\begingroup$ No,I think only consider this form,maybe not such $n|2^n-8$ $\endgroup$ – china math Jan 5 '15 at 6:47
  • $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Jan 5 '15 at 7:24
  • $\begingroup$ @CalvinLin,Haha,This is maybe use open problem? $\endgroup$ – china math Jan 5 '15 at 7:51
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.