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.

  • 6
    Interesting terminology.2012-08-02
  • 0
    When you say "with $2012$ hands in its hair", do you mean $2012$ hands of the same prime, or the sum of all hand counts of all primes? I. e., does there have to be a factor $p^{2012}$ in $n$, or does $n$ just have to have at least $2012$ prime factors, not necessarily the same?2012-08-02
  • 0
    For the first question all hands could be from the same prime, and for the second no. In general it is the sum of hands from all primes.2012-08-02
  • 0
    In general I am hypothesizing that p has to be 3 and k has to be a power of 3.2012-08-02
  • 0
    Can we prove that it works whenever that's the case?2012-08-02
  • 0
    That's quite a bit of hands in hair, someone must not be too happy about it!2012-08-02
  • 0
    Proposition: If $n$ is bald, then $n=0$.2012-08-02
  • 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$?

  • 0
    That is precisely what I am trying and failing to prove.2012-08-02
  • 0
    Do you have a proof.2012-08-02
  • 0
    Yes. Use induction on $r$, and $a^3+b^3=(a+b)(a^2-ab+b^2)$, and the behavior of $2^s$ modulo 3.2012-08-02
  • 0
    What is the behavior of 2^s mod3?2012-08-02
  • 0
    Never mind. But I don't get what a^3+b^3 has to do with it2012-08-02
  • 0
    Could you show the full proof2012-08-02
  • 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
    There's some interesting information about factors in these numbers in that entry, but I don't see anything that decides whether there can be $2012$ distinct prime factors.2012-08-02
  • 0
    In case the edit was in response to my comment: Do we agree that that answers the first question (which Gerry also answered), but not the second question?2012-08-02
  • 0
    Can we prove this is closed under multiplication?2012-08-02
  • 0
    Danielle, have you followed up the references at the OEIS page to see if there's a proof of closure under multiplication?2012-08-02
  • 0
    Yes- there isnt2012-08-02
  • 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