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

The following question was asked at Math StackExchange but, having attracted some attention, didn't get solved.

Problem 323 from the Mathematical Excalibur Vol. 14, No. 2, May-Sep. 09, linked here (see page 3, where also a solution is given), reads:

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

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. Indeed, Max Alekseyev has shown (see COMMENTS section) 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?

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

As observed by the Math StackExchange user rtybase, if $$p^2\mid n$$, then $$p$$ must be a Wieferich prime. The only two Wieferich primes presently known are $$1093$$ and $$3511$$; none of them can divide $$n$$ as $$n\mid 2^n+2$$, along with evenness of $$n$$, imply that $$-2$$ is a quadratic residue modulo any odd prime divisor of $$n$$. Since there are no other Wieferich primes up to $$10^{17}$$, any non-squarefree $$n$$ with $$n\mid 2^n+2$$ must satisfy $$n>2\cdot 10^{34}$$.

The argument of rtybase can in fact be pushed a little further. Suppose that $$n\mid 2^n+2$$ with $$n=2mp^2$$, where $$m$$ is a positive integer and $$p$$ is an odd prime. Then $$2^{2mp^2}\equiv -2\pmod{2mp^2}$$ whence $$2^{2mp}\equiv -2\pmod{p^2}$$, showing that $$(-2)^{\frac{p-1}2}\equiv 1\pmod{p^2}$$ and, on the other hand, $$(-2)^{2mp-1}\equiv 1\pmod{p^2}.$$ Consequently, the order of $$-2$$ modulo $$p^2$$ is an odd divisor of $$p-1$$. This leads to the following question:

Are there any primes of the form $$p=2^ck+1$$, with $$c,k\ge 1$$ and $$k$$ odd, such that $$(-2)^{k}\equiv1\pmod{p^2}$$?

Notice that this requirement is stronger than that in the definiton of a Wieferich prime; thus, can be more tractable.

• I see little hope for answering this. A negative answer would imply existence of a new Wieferich prime, while it's unclear how one can approach a positive answer. – Max Alekseyev Mar 24 at 4:23
• Just to note: This problem is NOT from IMO 2009. The magazine you've published has IMO 2009 on that current version, and this is just their problem corner question. – kawa Mar 24 at 14:52
• @MaxAlekseyev: I added a couple of paragraphs which, to some extent, address your concern. – W-t-P Mar 24 at 18:31
• @kawa: Thank you, I corrected the reference. – W-t-P Mar 24 at 18:31
• @kawa: The infiniteness property traces back at least to the Sierpinski book of 1970. – Max Alekseyev Mar 24 at 18:40