9
$\begingroup$

Problem 323 from the IMO 2009 reads:

Prove that there are infinitely many positive integers n such that $2^n+2$ is divisible by $n$.

An amazingly nice (and short) solution can be found here (see page 3).

OEIS sequence A006517 lists the 27 smallest integers $n$ with $n\mid 2^n+2$: $$ 1, 2, 6, 66, 946, 8646, 180246, 199606, 265826, 383846, 1234806, 3757426, 9880278, 14304466, 23612226, 27052806, 43091686, 63265474, 66154726, 69410706, 81517766, 106047766, 129773526, 130520566, 149497986, 184416166, 279383126. $$

All these numbers, with the exception of $1$, are even, and Max Alekseyev has shown that this keeps to hold for larger terms, too: if $n\mid 2^n+2$ and $n>1$, then $n$ is even.

Yet another observation is that all numbers listed above are square-free. Does this hold in general?

Is it true that if $n\mid 2^n+2$, then $n$ is square-free?


(Also posted on MathOverflow: https://mathoverflow.net/q/326123/9924)

$\endgroup$
  • 1
    $\begingroup$ A not squarefree example must exceed $\large 10^{15}$ $\endgroup$ – Peter Mar 14 at 20:26
  • 1
    $\begingroup$ Still no not squarefree solution upto $\large 10^{16}$ $\endgroup$ – Peter Mar 15 at 8:42
  • $\begingroup$ @Peter: We know that a counterexample must be divisible by $2p^2$, where $p$ is a Wieferich prime. On the other hand, $2^n\equiv -2\pmod p$, along with the fact that $n$ is even, shows that any odd prime $p$ dividing $n$ satisfies $(-2/p)=1$. Since there are only two Wieferich primes below $10^{17}$, and none of them satisfies this condition, any counterexample must exceed $2\cdot 10^{34}$. $\endgroup$ – W-t-P Mar 15 at 15:13
  • $\begingroup$ Good observation ! $\endgroup$ – Peter Mar 16 at 8:11
  • 1
    $\begingroup$ Now posted also on MO: A006517: Integers with $n\mid 2^n+2$. $\endgroup$ – Martin Sleziak Mar 23 at 8:01
3
$\begingroup$

Just an observation. If we assume $n=q\cdot p^2$ where $p$ is an odd prime number, then $$2^{n} \equiv -2 \pmod{p^2} \tag{1}$$ and from Euler's theorem $$2^{\varphi\left(p^2\right)} \equiv 1 \pmod{p^2} \iff 2^{p(p-1)} \equiv 1 \pmod{p^2} \tag{2}$$ Expanding $(2)$ we have $$2^{p^2(p-1)} \equiv 1^p \pmod{p^2} \Rightarrow 2^{q\cdot p^2 \cdot (p-1)} \equiv 1^q \pmod{p^2} \Rightarrow \\ 2^{n \cdot (p-1)} \equiv 1 \pmod{p^2} \tag{3}$$ but, from $(1)$ and given $p-1$ is even $$2^{n\cdot(p-1)} \equiv (-2)^{p-1} \equiv 2^{p-1} \pmod{p^2} \tag{4}$$ combining $(3)$ and $(4)$ $$2^{p-1} \equiv 1 \pmod{p^2}$$ which makes $p$ a Wieferich prime (also here), of which only two are known so far, $1093$ and $3511$ (A001220).

$\endgroup$
  • 1
    $\begingroup$ I found that out independent from your post (+1). I did not find a squarefree example yet, but it must be greater than $10^{13}$. One slight remark : $n$ cannot be divisible by $4$, so we actually can conclude that $p^2\mid n$ is only possible for odd prime $p$ $\endgroup$ – Peter Mar 14 at 18:18
  • 1
    $\begingroup$ @rtybase: Good point! $\endgroup$ – W-t-P Mar 15 at 7:18

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.