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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Max Alekseyev Mar 24 at 4:23
  • 1
    $\begingroup$ 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. $\endgroup$ – kawa Mar 24 at 14:52
  • $\begingroup$ @MaxAlekseyev: I added a couple of paragraphs which, to some extent, address your concern. $\endgroup$ – W-t-P Mar 24 at 18:31
  • $\begingroup$ @kawa: Thank you, I corrected the reference. $\endgroup$ – W-t-P Mar 24 at 18:31
  • 1
    $\begingroup$ @kawa: The infiniteness property traces back at least to the Sierpinski book of 1970. $\endgroup$ – Max Alekseyev Mar 24 at 18:40

Your Answer

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

Browse other questions tagged or ask your own question.