Prove that, there are infinitly many integers $n$; such that $n\mid 2^n+1$.

Question

Prove that, there are infinitly many integers $n$; such that $n\mid 2^n+1$.
I have found that $n=1,3$ works as well.
But I can't found any more.

A related question can be found here: (https://math.stackexchange.com/questions/97229/how-many-rationals-of-the-form-large-frac2n1n2-are-integers/424244#424244), which shows that only $n = 1,3$ can satisfy $n^2 | 2^n + 1$. — Toby Mak, Aug 19 '17 at 08:17
It also works for $9$ and $27$ among others. Do you notice something convenient about the pattern $1,3,9,27$? Can you make a conjecture using this pattern so far? Can you prove your conjecture is true? — JMoravitz, Aug 19 '17 at 08:18
https://oeis.org/A006521
Closed under multiplication: if x and y are terms then so is x*y. — Raffaele, Aug 19 '17 at 08:26
I am posting this comment again here in case the other thread that asks this question is deleted. See IMO 2000, Problem 5. You can demand that $n$ has exactly $k$ prime factors for any nonnegative integer $k$. You can prove this by induction (on $k$). Here is one source: https://sms.math.nus.edu.sg/Simo/IMO_Problems/00.pdf. — Batominovski, Oct 13 '19 at 17:40

score 7 · Answer 1 · answered Aug 19 '17 at 08:17

7

Hint: show that if $n$ is odd and $n \mid 2^n + 1$ then $3n \mid 2^{3n} + 1$.

answered Aug 19 '17 at 08:17

Adayah

10,468

1

Thanks; but how did you guess this? – Aug 19 '17 at 08:25
@shabnamjamali I noticed $9 \mid 2^9 + 1$ and thought maybe there was a reason for it. Also $k=3$ is the least number such that $2^n+1$ evidently divides $2^{kn}+1$, so I was trying to check out if it helps. – Adayah Aug 19 '17 at 08:27
n can not be a power of 2 because 2^n +1 becomes a prime. – sirous Aug 20 '17 at 15:16
@sirous First of all, what you're referring to are Fermat numbers, not all of which are prime. Second of all, how is this related to my answer? I'm assuming that $n$ is odd. – Adayah Aug 20 '17 at 16:32
@Adayah for 3n = 21 it doesn't work. n is odd and $3\mid 21$ – Eitank Dec 27 '20 at 09:33
@Eitank What doesn't work? The implication is true for $n=7$ since the assumption $n \mid 2^n+1$, i.e. $7 \mid 129$, is false. – Adayah Dec 30 '20 at 13:11
@Adayah, i have solved the problem with induction. Thank you – Eitank Dec 31 '20 at 11:12

Davood · Accepted Answer · 2017-08-20T05:22:15.443

Lemma : Let $l$ and $k$ be odd natural numbers, such that $l \mid k$. Then we have:

$$ a^l+1 \mid a^k+1 . $$

Let $\color{Green}{n_1=1}$; and let $\color{Green}{n_{j+1}=2^{n_j}+1}$; the first terms are as follows:

$$ n_1=1, \ \ \ \ n_2=3, \ \ \ \ n_3=9, \ \ \ \ n_4=513, \ \ \ \ n_5=2^{513}+1 \ \ ; \ \ \ \ ... $$

We claim that: $\color{Blue}{n_i \mid n_{i+1}}$.
Proof by induction:
$n_1 \mid n_2$.
Suppose that the claim is true for $j=i$; we will show that, this implies the claim for $j=i+1$.

$$ n_i \mid n_{i+1} %\Longrightarrow %n_i \mid 2^{n_{i+1}}+1 \overset { \tiny{\text{by lemma}} } {\Longrightarrow} 2^{n_i}+1 \mid 2^{n_{i+1}}+1 {\Longrightarrow} n_{i+1} \mid n_{i+2} $$

But notice that the statement $\color{Blue}{n_i \mid n_{i+1}}$ is equivalent to $\color{Red}{n_i \mid 2^{n_i}+1}$ .

It looks like very complicated, where this idea comes from? – Aug 19 '17 at 08:27 — , Aug 19 '17 at 08:27

Prove that, there are infinitly many integers $n$; such that $n\mid 2^n+1$.

2 Answers2