# Showing the existence of an integral number

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.

• Note: The case of distinct factors is IMO 2000 shortlist, Number Theory qn 3. Nov 8, 2019 at 20:11

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.

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