1
$\begingroup$

Recently, in high-school competition maths, I came across such a question:

Does there exist an integer $n$, with $2000$ factors, such that $n$ divides $2^n+1$, or:

$$n\mid{2^n+1}?$$ This question is tagged as a practice question for number theory and is part of a lecture on indefinite equations. The solution was not provided, and I could not seem to figure it out.

Any help would be much appreciated.

$\endgroup$
1
  • $\begingroup$ Note: The case of distinct factors is IMO 2000 shortlist, Number Theory qn 3. $\endgroup$
    – Calvin Lin
    Nov 8, 2019 at 20:11

1 Answer 1

3
$\begingroup$

A useful lemma is that for all $k$ we have $$3^k\,|\,2^{3^k}+1$$

The proof is a straight forward induction, and may be found, e.g., here. Indeed, one can show a slightly stronger result than we require.

These are not all the $n$ such that $n\,|\,2^n+1$ but they suffice to answer this question, since $3^k$ has $k+1$ divisors.

Worth remarking: the $n$ for which $n\,|\,2^n+1$ which are not powers of $3$ form a rather erratic list. in OEIS they form sequence A016057.

$\endgroup$
9
  • $\begingroup$ $3^k$ has $k+1$ divisors, not prime divisors right? $\endgroup$
    – AgentS
    Nov 8, 2019 at 13:38
  • 1
    $\begingroup$ @pooja Yes. Clearly $3^k$ has only one prime divisor. $\endgroup$
    – lulu
    Nov 8, 2019 at 13:39
  • $\begingroup$ Ah ok you're right! I was looking at another sol'n where it asked for $n$ to have $2000$ distinct prime factors haha $\endgroup$
    – AgentS
    Nov 8, 2019 at 13:40
  • $\begingroup$ this variation of the problem looks hard. 3rd page last line $\endgroup$
    – AgentS
    Nov 8, 2019 at 13:42
  • $\begingroup$ @pooja Yeah, that's clearly a lot harder. $\endgroup$
    – lulu
    Nov 8, 2019 at 13:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .