8
$\begingroup$

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.

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.