# A006517: Numbers with $n\mid 2^n+2$

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)

• A not squarefree example must exceed $\large 10^{15}$ – Peter Mar 14 at 20:26
• Still no not squarefree solution upto $\large 10^{16}$ – Peter Mar 15 at 8:42
• @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}$. – W-t-P Mar 15 at 15:13
• Good observation ! – Peter Mar 16 at 8:11
• Now posted also on MO: A006517: Integers with $n\mid 2^n+2$. – Martin Sleziak Mar 23 at 8:01

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).
• 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$ – Peter Mar 14 at 18:18