0
$\begingroup$

Moderator Message: this question is from an ongoing competition.

Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands in its hair? Does there exist an integer $n$ with $2012$ distinct primes' hands in its hair?

Furthermore it would be fantastic if you could show your full logic, thank you.

For example, $3$ has 1 hand in its own hair, and I can't think of any other nice examples.

  • 0
    I rolled back to the original formulation of the question because Robert's answer and most of the comments depend on it. Changing the entire terminology of a question long after it's been answered is a bad idea.2012-12-10

2 Answers 2

2

Can you prove that $3^r\mid2^{3^r}+1$?

  • 1
    It's much better for all of us if you work out the proof than if I show it to you. Can you see that $2^{3^r}+1$ is a sum of two cubes?2012-08-02
2

The integers $n$ such that $n | 2^n + 1$ are sequence A006521 in the OEIS: http://oeis.org/A006521

Note the comments. So for example 19 has $2012$ hands in $n$'s hair where $n = 3^2 \times 19^{2012}$.

EDIT: If $p$ is a prime dividing $2^{3^k}+1$ for some integer $k$, then $3^k p$ is in the sequence A006521. For convenience let $f(j) = 2^{2 \cdot 3^j} - 2^{3^j} + 1$. Now $2^{3^k}+1 = 3 \prod_{j=0}^{k-1} f(j)$ Any prime $p > 3$ dividing $f(j)$ divides $2^{3^{j+1}}+1$ but not $2^{3^j}+1$, and thus not $f(k)$ for any $k < j$. Now $2^{3^k} \equiv -1 \mod 9$ for all $k \ge 1$, so $f(k) \equiv 3 \mod 9$ has only one factor of $3$. Thus each $f(j)$ for $j \ge 1$ must be divisible by some prime $p > 3$, which doesn't divide any other $f(k)$. We conclude that there are infinitely many different primes that divide members of A006521. In particular for any $N$, there is a member of A006521 with $N$ distinct prime factors.

  • 0
    Closure under multiplication is an easy corollary of Proposition 1 of http://www.maths.ed.ac.uk/~chris/n_divides_2to_nplus1.pdf : note that $mn = \gcd(m,n) \text{lcm}(m,n)$ and $\gcd(m,n) | \text{lcm}(m,n)$.2012-08-02