$n$ with $2000$ divisors divides $2^n+1$ (IMO 2000)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7301 posts

#1 h Oct 24, 2005, 10:23 AM • 16 Y

Y by Amir Hossein, Davi-8191, MarkBcc168, Understandingmathematics, itslumi, Adventure10, megarnie, RedFlame2112, Leo890, clevereagle, Mango247, cookie130, Dansman2838, PikaPika999, and 2 other users

Does there exist a positive integer $n$ such that $n$ has exactly 2000 prime divisors and $n$ divides $2^n + 1$ ?

This post has been edited 1 time. Last edited by Amir Hossein, Mar 21, 2016, 7:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

grobber

7849 posts

grobber

#2 h Oct 24, 2005, 12:41 PM • 15 Y

Y by viperstrike, laegolas, Wizard_32, to_chicken, Adventure10, DCMaths, Mango247, cookie130, MS_asdfgzxcvb, PikaPika999, and 5 other users

For any $k\ge 1$ there is such an $n$ with exactly $k$ prime factors.

For $k=1,\ n=3^t$ works for every $t\ge 1$ . Take $t$ s.t. for $n_1=3^t,\ 2^{n_1}+1$ has a prime factor $p_2$ larger than $3$ . Now take $n_2=n_1p_2$ . Then $n_2|2^{n_1}+1|2^{n_2}+1$ , and $2^{p_2}+1$ has a prime factor $p_3\not|n_2$ . This is because $(2^{n_1}+1,2^{p_2}+1)=3,\ p_2\not|2^{p_2}+1$ , and $2^{p_2}+1$ cannot be a power of $3$ , since $p_2>3$ (I'm using the well known and easy to prove fact that the only positive integer solution $(a,b),a>1$ to $3^a=2^b+1$ is $(a,b)=(2,3)$ ). Then take $n_3=n_2p_3$ . Just like above, we deduce that $2^{p_3}+1$ has a prime factor $p_4$ which is coprime to $n_3$ , and take $n_4=n_3p_4$ , and so on. $n_k$ will have exactly $k$ prime factors and will satisfy $n_k|2^{n_k}+1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pluricomplex

390 posts

pluricomplex

#3 h Oct 25, 2005, 10:24 AM • 3 Y

Y by Adventure10, Mango247, cookie130

Valentin Vornicu wrote:

Does there exist a positive integer $n$ such that $n$ has exactly 2000 prime divisors and $n$ divides $2^n + 1$ ?

You can find my paper for a general problem of this problem in This file

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Philip_Leszczynski

327 posts

Philip_Leszczynski

#4 h Dec 17, 2005, 10:19 PM • 3 Y

Y by Adventure10, Mango247, cookie130

Let $N=2^n+1$ . We will assume for the sake of contradiction that $n|N$ .

$2^n+1 \equiv 0$ (mod $n$ ) $\Rightarrow 2^n \equiv -1$ (mod $n$ ). So 2 does not divide $n$ , and so $n$ is odd.

Select an arbitrary prime factor of $n$ and call it $p$ . Let's represent $n$ in the form $p^am$ , where $m$ is not divisible by $p$ .

Note that $p$ and $m$ are both odd since $n$ is odd. By repeated applications of Fermat's Little Theorem:

$N = 2^n+1 = 2^{p^am} + 1 = (2^{p^{a-1}m})^p + 1 \equiv 2^{p^{a-1}m} + 1$ (mod $p$ )

Continuing in this manner, and inducting on k from 1 to $a$ ,

$2^{p^{a-k}m}+1 \equiv (2^{p^{a-k-1}m})^p + 1$ (mod $p$ ) $\equiv 2^{p^{a-k-1}m} + 1$ (mod $p$ )

So we have $N \equiv 2^m+1$ (mod $p$ )

Since $p$ is relatively prime to $m$ , $N \equiv 1+1$ (mod $p$ ) $\equiv 2$ (mod $p$ )

Since $p$ is odd, $N$ is not divisible by $p$ . Hence $N$ is not divisible by $n$ . So we have a contradiction, and our original assumption was false, and therefore $N$ is still not divisible by $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Philip_Leszczynski

327 posts

Philip_Leszczynski

#5 h Dec 17, 2005, 10:24 PM • 3 Y

Y by Adventure10, Mango247, cookie130

Hmmm... I made a mistake here somewhere but I do not see it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Arne

3660 posts

Arne

#6 h Dec 17, 2005, 10:26 PM • 4 Y

Y by The_fandangos, Adventure10, Mango247, cookie130

Yes, since there are lots of integers $n$ such that $n$ divides $2^n + 1$ , and the statement is true!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Johann Peter Dirichlet

376 posts

Johann Peter Dirichlet

#7 h Feb 27, 2006, 2:29 PM • 3 Y

Y by Adventure10, Mango247, cookie130

There exists a pretty beautiful generalization:

"
Let $s, a, b$ positive integers, such that $GCD(a,b) = 1$ and $a+b$ is not a 2-power.
Show that there exists infinitely many $n \in N$ such that

--- $n=p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_s^{e_s} \cdot$ is the canonical factoring of $n$ .

--- $n|(a^n+b^n)$
"

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

The QuattoMaster 6000

1184 posts

The QuattoMaster 6000

#8 h Oct 22, 2008, 1:24 AM • 3 Y

Y by Adventure10, Mango247, cookie130

Valentin Vornicu wrote:

Does there exist a positive integer $n$ such that $n$ has exactly 2000 prime divisors and $n$ divides $2^n + 1$ ?

Here is a solution that I don't think has been mentioned yet:
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Arquimedes

8 posts

Arquimedes

#9 h Jun 6, 2009, 2:10 PM • 3 Y

Y by Adventure10, Mango247, cookie130

For any i,

2^3^i+1

is divisible by

3^i

(the proof is easy with euler`s theorem+induction and maybe with primitive roots (2 is primitive root modulo 3^i for any i)). Hence, for i=1999,

3^1999

has 2000 divisors and it satisfies the asked in the problem.

it is correct??

please , answer me.

bye

sorry for my english.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L-b

11 posts

L-b

#10 h Nov 29, 2009, 9:06 PM • 3 Y

Y by Adventure10, Mango247, cookie130

Well, the point is to find a number which has exactly $2000$ prime divisiors, whereas $3^{1999}$ has only one ( $3$ ).

But it is a very nice thought to look at powers of $3$ , when the problem considers powers of $2$ (vide grobber's solution, which I do not completely understand yet, but it seems very nice and simple)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Binomial-theorem

3982 posts

Binomial-theorem

#11 h Sep 15, 2013, 7:24 AM • 5 Y

Y by JasperL, Anar24, Adventure10, Mango247, cookie130

Solution overkilling with Zsigmondy's

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#12 h Sep 16, 2013, 3:51 AM • 18 Y

Y by Binomial-theorem, WL0410, e_plus_pi, Omeredip, Not_real_name, Takeya.O, TheHerculean11, ZHEKSHEN, Quidditch, HamstPan38825, Msn05, samrocksnature, joseph02, aidan0626, Adventure10, Mango247, MarioLuigi8972, cookie130

Answer: Yes.

We say that $n$ is Korean if $n \mid 2^n+1$ . First, observe that $n=9$ is Korean. Now, the problem is solved upon the following claim:

Claim: If $n > 3$ is Korean, there exists a prime $p$ not dividing $n$ such that $np$ is Korean too.

Proof. I claim that one can take any primitive prime divisor $p$ of $2^{2n}-1$ , which exists by Zsigmondy theorem. Obviously $p \neq 2$ . Then:

Since $p \nmid 2^{\varphi(n)}-1$ it follows then that $p \nmid n$ .
Moreover, $p \mid 2^n+1$ since $p \nmid 2^n-1$ ;

Hence $np \mid 2^{np} + 1$ by Chinese Theorem, since $\gcd(n,p) = 1$ . $\blacksquare$

EDIT: The version of the proof I posted four years ago was incorrect. This one should work.

This post has been edited 1 time. Last edited by v_Enhance, May 3, 2017, 1:08 AM
Reason: Wanlin Li pointed out a mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lfetahu

134 posts

lfetahu

#13 h May 12, 2014, 8:21 PM • 6 Y

Y by Takeya.O, gghx, Adventure10, Mango247, cookie130, and 1 other user

I feel like it isn't interesting to make any new remark on this problem, but anyway I'm posting my approach too.

If we show that for any positive integer k, there exists a positive integer n with exactly k distinct prime divisors such that n | 2^n + 1, then we are done, since the problem asks us to examine a special case, more exactly k = 2000. Furthermore, we can even show that we can find these n's divisible by a power of 3, which will help us on our proof.

We use induction on k. k = 1, we can choose n(1) = 3, which clearly satisfies the conditions. Assume that k >= 1, and there exists n(k) = 3^t * m, where gcd(3, m) = 1, and m has exactly (k - 1) distinct prime divisors. So, we have n(k) | 2^(n(k)) + 1.
Before generating n(k+1) from n(k), let us look at the number 3n(k), which clearly has k distinct prime divisors. 2^(3n(k)) + 1 = (2^(n(k)) + 1)(2^(2n(k)) - 2^(n(k)) + 1). Since we must have n(k) always odd because of the fact that n(k) = 1 (mod 2), we deduce that 3 | (2^(2n(k)) - 2^(n(k)) + 1), so we have that 3n(k) | 2^(3n(k)) + 1. It is enough to find a prime p, such that p | 2^(3n(k)) + 1 and p doesn't divide (2^(n(k)) + 1), which could guarantee us that p doesn't divide n(k) and consequently, we could generate n(k + 1) = 3n(k)*p, which could clearly work by observing that 2^(3n(k)*p) + 1 = (2^(n(k)) + 1)(2^(2n(k)) - 2^(n(k)) + 1)*A. But, since we can pick up this prime p by Zsigmondy, we are done.

Note that in case of not using Zsigmondy, we can observe that gcd(a^2 - a + 1, a + 1) = gcd(3, a + 1) = 1 if a is not 2 mod 3 and 3 if a = 3k + 2. But if a = 3k + 2, then a^2 - a + 1 is divisible by 3 but not by 9, so we could pick up any prime p that divides (a^2 - a + 1) / 3.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sayantanchakraborty

505 posts

sayantanchakraborty

#14 h May 20, 2014, 6:56 PM • 3 Y

Y by Adventure10, Mango247, cookie130

Let $n=\prod_{i=1}^{2000}{p_i}$ and wlog let $p_1<p_2<\dots<p_{2000}$ .I dscribe a process on how to construct such an $n$ .By the problem we have $2^{2n} \equiv 1\pmod{p_1} \Rightarrow ord_{p_1}{2} |2n$ and so by the minimality of $p_1$ we get that $ord_{p_1}=1$ or $ord_{p_1}=2$ .In the first case we get $p_1|1$ which is absurd while in the second case we get $p_1|2^2-1=3 \Rightarrow \boxed{p_1=3}$ .Similarly it is easy to note that $ord_{p_2}{2}|2n$ and so by the choice of $p_2$ we get $ord_{p_2}{2}|2*3=6$ .Clearly there exists such a prime such that $ord_{p_2}{2}=6$ (By Zsigmondy!!)In general we have $2^{2n} \equiv 1\pmod{p_k} \Rightarrow ord_{p_k}2|p_1p_2\dots p_{k-1}$ .Clearly there exists a prime such that $ord_{p_k}2=p_1p_2\dots p_{k-1}$ (Again Zsigmondy!!).So we are done!!!(In fact by this procedure we may fix any number of primes).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

junioragd

314 posts

junioragd

#15 h Jan 7, 2015, 6:59 PM • 3 Y

Y by Adventure10, Mango247, cookie130

Since $N=3^k$ all satisfay the condition.Now,it is enough to prove that numbers of the form $N=2{}^3{}^k+1$ have infinitely many primes dividing them,but this is easy to prove,since we have for $n<m$ $2{}^3{}^n+1$ divides $2{}^3{}^m+1$ so suppose opposite.Now,we just need to prove that $a+1$ and $a^3+1$ can't have identical sets of primes for $a>2$ ,and this is true because $GCD(a+1,a^2-a+1)$ is at most $3$ and $a^2-a+1>3$ for $a>2$ so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2534 posts

joshualiu315

#55 h Feb 12, 2024, 8:29 PM

Y by

The answer is $\boxed{\text{yes}}$ .

Let $p_x$ be a prime that divides $2^{3^x}+1$ but not $2^{3^{i}}+1$ for $i<x$ . This prime will always exist by Zsigmondy, meaning our desired number is

$n=3^{2000}p_2p_3\cdots p_{2000}.$
Seeing that this works is trivial, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

795 posts

shendrew7

#56 h Mar 1, 2024, 7:25 AM

Y by

We note $n_1=3^2$ satisfies the condition. We aim to find a prime $p$ such that $pn_i$ satisfies the condition and $\gcd(p,n_i)=1$ , so it suffices to have
$2^{pn} \equiv -1 \pmod{p} \implies 2^{2n} \equiv 1, 2^n \not\equiv 1 \pmod{p}.$
This primitive root of 2 modulo $p$ exists by Zsigmondy, as desired. Hence we can induct to find $n_{2000}$ with the desired 2000 prime divisors. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

281 posts

peppapig_

#57 h Mar 14, 2024, 3:18 PM

Y by

Overkill?

In general, I claim that there exists a positive integer $n$ such that $n\mid 2^n+1$ with exactly $k$ distinct prime divisors for all positive integers $k$ .

I prove this by claiming that if there exists a positive integer $n$ with $k$ distinct integer divisors in the form of
$n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k},$ such that $p_1<p_2\dots<p_k$ , then there exists a prime $p_{k+1}>p_k$ such that for all positive integers $e_{k+1}$ , it is true that $np_k^mp_{k+1}^{e_{k+1}}$ satisfies the problem condition, where we can make $m$ any positive integer we want.

C1: First, before we begin, I claim that if any prime $q\mid n$ , then $nq$ also satisfies problem conditions. This will then prove the part where we can make $m$ whatever we want. This is because
$n\mid 2^n+1 \iff \nu_q(n)\leq \nu_q(2^n+1),$ and by LTE (which we can use, since $n\mid 2^n+1$ implies that $q\mid 2^n+1$ ), this gives us that
$\nu_q(nq)=1+\nu_q(n)\leq 1+\nu_q(2^n+1)=\nu_q(2^{nq}+1),$ which means that $nq$ also satisfies the problem conditions, as desired. Therefore, by induction, we also get that $nq^m$ also satisfies problem conditions.

C2: Now, I claim that there exists a prime $p_{k+1}$ such that for all positive integers $e_{k+1}$ , $np_k^mp_{k+1}^{e_{k+1}}$ satisfies the conditions. For simplicity, from here on out, I will refer to $p_{k+1}$ as $r$ and $p_k$ as $q$ . Note that this implies that
$r\mid 2^n+1 \iff ord_r(2)\mid 2n,$ and since $ord_r(2)\mid \phi(r)=r-1$ , we get that $ord_r(2)\mid \gcd(2n,r-1)$ . First, I claim that there always exists an $r$ that divides $2^{q^c}+1$ for some $c$ we can choose such that $r>q$ . This is clearly true by Zsigmondy's theorem. I now claim that if we take this $r$ , it is true that $rn$ also satisfies problem conditions. This, combined with (C1), will prove our master claim, which states that $nr^e_{k+1}$ satisfies problem conditions for any $e_{k+1}$ .

To prove this, first make sure that our previous $n$ is divisible by the $q^c$ we chose. We can do this by making another $n$ that satisfies problem conditions by multiplying it by a power of $q$ , which we can do by (C1). Next, by LTE, we have,
$\nu_r(rn)=1\leq \nu_r(2^{rn}+1)=\nu_r(2^n+1)+1,$ which we can do since we know that $q^c \mid n$ and $r\mid 2^{q^c}+1$ , which gives that $r\mid 2^n+1$ . This means that $rn$ satisfies problem conditions, since $rn\mid 2^{rn}+1$ , which combined with (C1), proves our inductive step claim.

Finally, to complete our induction, note that $3\mid 2^3+1$ . Therefore, there exists a positive integer $n$ such that $n\mid 2^n+1$ with exactly $k$ distinct prime divisors for all positive integers $k$ , finishing the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SenorSloth

37 posts

SenorSloth

#58 h Jun 21, 2024, 5:53 PM

Y by

We claim that the answer is yes. We will induct to show that if there exists such an $n$ with $x$ distinct prime factors, then there also exists such an $n$ with $x+1$ distinct prime factors. By repeating this logic we can find an $n$ with exactly $2000$ distinct prime factors.

Our base case is $n=9$ , which works since $9\mid 513$ . By Zsigmondy, for any $n>3$ , there exists a prime $p$ dividing $2^n+1$ that does not divide any $2^k+1$ for smaller $k$ . Since this implies that $2$ has order $2n$ modulo $p$ , the prime is at least $2n+1$ and thus cannot divide $n$ . Thus we know that $pn\mid 2^n+1$ and consequently $pn \mid 2^{pn}+1$ . $pn$ has $1$ more distinct prime factor than $n$ , so the induction is complete.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Niku

120 posts

Niku

#59 h Jun 21, 2024, 6:05 PM

Y by

Do you realise that this post was made 20 years ago.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BestAOPS

707 posts

BestAOPS

#60 h Jul 4, 2024, 10:10 PM

Y by

Overkill proof while forgetting about Zsigmondy:

Define two sequences as follows: $n_0 = 1$ ; $p_i$ is (a) the smallest prime factor of $2^{n_i} + 1$ that is not a factor of $n_i$ , or (b) if that doesn't exist, the smallest prime factor of $2^{n_i} + 1$ ; and $n_{i+1} = n_ip_i.$

Notice that each $n_i$ is divisible by all of the previous ones, and that all $n_i$ and $p_i$ are odd.

First, we show that all $n_i$ satisfy $n_i \mid 2^{n_i} + 1$ . We proceed by induction. We can see that $n_0 = 1$ works, so assume $n_i$ works (and all the ones before it). We want to prove $n_{i+1} \mid 2^{n_{i+1}} + 1$ .

Note that if a prime $p$ divides $n_{i+1}$ , then $p = p_j$ for some $j$ satisfying $0 \leq j \leq i$ .
This also means that $p_j$ is a factor of $2^{n_j} + 1$ .
Then, by LTE, we have
$\nu_{p_j}(2^{n_{i+1}} + 1) = \nu_{p_j}(2^{n_j} + 1) + \nu_{p_j}\left(\frac{n_{i+1}}{n_j}\right) = \nu_{p_j}(n_{i + 1}) + \nu_{p_j}(2^{n_j}+1) - \nu_{p_j}(n_j).$ However, the strong inductive hypothesis implies $\nu_{p_j}(2^{n_j}+1) - \nu_{p_j}(n_j) \geq 0$ , so we have $\nu_{p_j}(2^{n_{i+1}} + 1) \geq \nu_{p_j}(n_{i+1})$ .
As this is true for all $p$ , the inductive step is complete.

Next, we claim that eventually, the number of distinct prime factors of $n_i$ is always one more than the number of distinct prime factors of $n_{i-1}$ . This is equivalent to showing that eventually, there always exists a prime factor of $2^{n_i} + 1$ that is not a factor of $n_i$ .

Suppose, for some $i$ , that every prime factor of $2^{n_i} + 1$ is also a factor of $n_i$ .
Then, let $p$ be a prime factor of $n_i$ , and pick the minimal $j$ such that $p_j = p$ . This minimality implies that $\nu_{p_j}(n_j) = 0$ .
We have
$\nu_{p_j}(2^{n_i} + 1) = \nu_{p_j}(2^{n_j} + 1) + \nu_{p_j}(n_i) - \nu_{p_j}(n_j) = \nu_{p_j}(2^{n_j} + 1) + \nu_{p_j}(n_i).$ We can raise $p_j$ to the power of both sides to get
${p_j}^{\nu_{p_j}(2^{n_i} + 1)} = {p_j}^{\nu_{p_j}(2^{n_j} + 1)} {p_j}^{\nu_{p_j}(n_i)}.$ Doing this for every prime factor $p$ of $n_i$ (notice that $j$ is now a one-to-one function of $p$ ) and multiplying the resulting equations, we get
$2^{n_i} + 1 = n_i \prod_p p^{\nu_p(2^{n_{j(p)}} + 1)}.$ For all $p$ , we have $p^{\nu_p(2^{n_{j(p)}} + 1)} \leq 2^{n_{j(p)}} + 1$ . Thus,
$2^{n_i} + 1 \leq n_i \prod_p (2^{n_{j(p)}} + 1).$ Since $j$ is one-to-one, every $j(p)$ is unique and in the set $\{0, 1, \ldots, i-1\}$ . Therefore, we have the inequality
$2^{n_i} + 1 \leq n_i \prod_{j=0}^{i-1} (2^{n_j} + 1).$ Taking the log base $2$ of both sides, we have
$n_i < \log _2 (2^{n_i} + 1) \leq \log _2 n_i + \sum _{j=0}^{i-1} \log_2(2^{n_j} + 1) < \log_2 n_i + \sum _{j=0}^{i-1} (n_j + 1) = \log_2 n_i + i + \sum_{j=0}^{i-1}n_j.$ Now, in order to achieve a bound on $n_i$ , we notice that $p_i \geq 3$ for all $i$ , so therefore, $n_i \geq 3^i$ . It is then easy to see that $\sum_{j=0}^{i-1}n_j \leq \frac12 n_i$ for all $i \geq 1$ . Then,
$n_i < \log_2 n_i + i + \frac12 n_i \leq \log_2 n_i + \log_3 n_i + \frac12 n_i \iff n_i < 2(\log _2 n_i + \log _3 n_i).$ This inequality obviously cannot be satisfied as $n_i$ grows large. Thus, eventually, we must have that there exists a prime factor of $2^{n_i} + 1$ that is not a factor of $n_i$ . Hence, there must eventually exist an $n$ in our sequence with exactly 2000 distinct prime factors.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

LQFNB

12 posts

LQFNB

#61 h Jul 24, 2024, 11:26 AM

Y by

是否存在一个恰有2000个素因子的正整数 $n$ ，满足 $n \mid 2^n + 1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

LQFNB

12 posts

LQFNB

#62 h Jul 24, 2024, 11:27 AM

Y by

是否存在一个恰有2000个不同素因子的正整数 $n$ ，满足 $n \mid 2^n + 1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eibc

600 posts

eibc

#63 h Jan 2, 2025, 11:01 PM

Y by

The answer is yes. We will construct a positive integer $n = p_1^2 p_2p_3 \cdots p_{2000}$ where $p_1 < p_2 < \cdots < p_{2000}$ are distinct primes such that $n \mid 2^n + 1$ .

First, we set $p_1 = 3$ . For $i \ge 2$ , let $q_i = 3^2 \cdot p_2 \cdots p_3 \cdots p_{i - 1}$ . Then, we shall construct $p_i$ recursively by picking a primitive divisor of $2^{2q_i} - 1$ , which exists by Zsigmondy's theorem.

Now, we show that $n \mid 2^n + 1$ . It suffices to show that for $1 \le i \le 2000$ , we have $\nu_{p_i}(2^n + 1) \ge \nu_{p_i}(n)$ . For $i = 1$ , we note that by LTE,
$\nu_3(2^n + 1) = \nu_3(2 + 1) + \nu_3(n) = 1 + \nu_3(n) > 1.$ For $i > 1$ , we note that by construction, $\text{ord}_{p_i}(2) = 2q_i$ . Thus, $2^{q_i} \equiv -1 \pmod {p_i}$ , so by LTE, we have
$\nu_{p_i}(2^n + 1) = \nu_{p_i}((2^{q_i})^{n/q_i} + 1) = \nu_{p_i}(2^{q_i} + 1) + \nu_{p_i}(n/q_i) \ge 1 + \nu_{p_i}(n) > \nu_{p_i}(n),$ so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Natrium

54 posts

Natrium

#64 h Jan 24, 2025, 11:41 AM

Y by

Lemma. If $a\mid 2^a+1$ and $b\mid 2^b+1$ , where $a=3^\alpha a'$ , $b=3^\beta b'$ , $3 \nmid a', b'$ and $a'$ and $b'$ are coprime, then $ab\mid 2^{ab}+1$ .
Proof. Obviously, $a$ and $b$ are odd.
$2^{ab}\equiv (-1)^b\equiv -1 \pmod{a}$ $2^{ab}\equiv (-1)^a\equiv -1 \pmod{b}$ By LTE, $v_3(2^{ab}+1)=v_3(ab)+1=\alpha + \beta + 1$ . Finally, as $a', b', 3^{\alpha+\beta}\mid 2^{ab}+1$ and all three numbers are pairwise coprime, $ab=a'b'3^{\alpha+\beta}\mid 2^{ab}+1$ . $\square$

We construct a sequence of primes $p_2, p_3, \dots, p_{2000}$ in the following manner. Let $p_2=19$ (so that $p_2\mid 2^{3^2}+1$ ). Inductively assume we have constructed $p_2, p_3, \dots, p_{i}$ , for some $i\ge 2$ , such that:
$\bullet$ all $p_j$ with $2\le j\le i$ are distinct,
$\bullet$ $p_j>3$ and $p_j\mid2^{3^{i}}+1$ for each $2\le j\le i$ .
As $2^{3^{i+1}}+1=(2^{3^i}+1)(4^{3^i}-2^{3^i}+1)$ and the greatest common divisor of the terms in the parenthesis is $3$ , we conclude that $4^{3^i}-2^{3^i}+1$ has all its prime divisors distinct from $p_j$ for $2\le j\le i$ . As $9\mid 2^{3^i}+1$ and $4^{3^i}-2^{3^i}+1>3$ , it has a prime factor $p_{i+1}>3$ , so the inductive claim holds for $i+1$ as well.

Having constructed $p_2, p_3, \dots, p_{2000}$ , let $n_i=3^i p_i$ for each $2\le i\le 2000$ . By LTE, $v_3(2^{n_i}+1)=i+1$ . By Fermat's Little Theorem, $2^{n_i}\equiv 2^{3^i p_i}\equiv 2^{3^i}\equiv -1\pmod{p_i}$ . Therefore, $n_i = 3^i p_i\mid 2^{n_i} + 1$ for each $i$ . Let $n=n_2n_3\dots n_{2000}$ . By repeated application of the lemma, $n\mid 2^n + 1$ , and by construction, $n$ has $2000$ distinct prime divisors.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#65 h Feb 18, 2025, 2:38 AM

Y by

Write $x\sim y$ if $p\mid x$ iff $p\mid y$ .

Let $n$ be some odd integer such that $n>3$ , $n\mid 2^n+1$ , and $n\nsim 2^n+1$ . We claim that there exists a prime $p\nmid n$ for which $np\mid 2^{np+1}$ and $np\nsim 2^{np}+1$ . Indeed, take some $p\nmid n$ and $p\mid 2^n+1$ . Note that $2^{np}+1\equiv 2^n+1\equiv0\pmod p$ , and since $p$ is odd, we also have $n\mid 2^{np}+1$ . Hence $np\mid 2^{np}+1$ . Furthermore, since $n>3$ , there exists some prime $q$ satisfying $q\nmid 2^n+1$ and $q\mid 2^{np}+1$ by Zsigmondy.

Applying the above claim $1999$ times on $n=9$ implies that the answer is $\fbox{\text{yes}}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amapstob

19 posts

amapstob

#66 h Mar 13, 2025, 1:41 PM

Y by

The answer is yes.
Lemma. For all primes $p>3$ , $2^p+1$ has a prime divisor greater than $p$ .
Proof. $2^p\equiv -1\pmod{q}\implies 2^{\gcd(q-1,2p)}\equiv 1\pmod{q}$ . If $\gcd(q-1,2p)=2$ , then $q=3$ , so we have to rule out $2^p+1$ being a power of three, which only happens with $p=3$ by Mihailescu's theorem. Since $p>3$ , there exists $q\neq 3$ dividing $2^p+1$ . Then $p\mid q-1\implies p<q$ , as desired. $\blacksquare$

Claim. If $n\mid 2^{n}+1$ and $n$ is odd and has a prime divisor greater than $3$ , there exists a prime with $p\mid 2^n+1$ and $p\nmid n$ such that $np\mid 2^{np}+1$ .
Proof. Let $q$ be the greatest prime divisor of $n$ . Then $2^q+1\mid 2^n+1$ . But $2^q+1$ has a prime divisor $p$ greater than $q$ by the above lemma. So $p\nmid n$ and $p\mid 2^n+1$ . Then since $p\mid 2^n+1$ and $n\mid 2^n+1$ and $n,p$ are coprime, $np\mid 2^n+1$ . But $2^n+1\mid 2^{np}+1$ , so we're done. $\blacksquare$

Now observe that $3^2\cdot 19 \mid 2^{3^2\cdot 19}+1$ , so applying the lemma above $1998$ times finishes. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

623 posts

cursed_tangent1434

#67 h Apr 9, 2025, 4:00 PM

Y by

We claim that the answer is yes. In fact we can show the more general statement that for any positive integer $d$ there exists some positive integer $n$ for which $n$ has exactly $d$ distinct prime divisors and $n \mid 2^n+1$ . To do this, we employ induction.

First note that $3 \mid 2^3+1$ . Now, say there exists a positive integer $n_r = 3^{r}\cdot p_1p_2 \dots p_r$ for which $n_r \mid 2^{n_r}+1$ . Consider
$2^{3n_r}+1=2^{3^{r+1}\cdot p_1p_2\dots p_{r}} +1$ Now, by Zsigmondy's Theorem there exists a prime $p_{r+1} \mid 2^{3^{r+1}\cdot p_1p_2\dots p_{r}} +1$ but $p_{r+1} \nmid 2^{3^r \dot p_1p_2\dots p_r}$ . Thus, this prime factor $p_{r+1} \not \in \{p_1,p_2,\dots , p_r\}$ . Further,
$3n_r \mid 2^{n_r}+1 \mid 2^{3n_r\cdot p_{r+1}}+1$ since by Lifting the Exponent Lemma, $\nu_3(2^{n_r}+1)= \nu_3(3)+\nu_3(n_r) = \nu_3(3n_r)$ . Finally,
$2^{3n_r\cdot p_{r+1}}+1 \equiv 2^{3n_r}+1 \equiv 0 \pmod{p_{r+1}}$ by construction. Thus, $3n_r\cdot p_{r+1} \mid 2^{3n_r\cdot p_{r+1}}+1$ so we can let $n_{r+1}=3n_r\cdot p_{r+1}$ which completes the induction and proves the result.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ray66

35 posts

ray66

#68 h Apr 24, 2025, 3:38 AM

Y by

We will prove the result by induction.

First take the base case $n_1=9$ so that $9$ divides $513$ . Now consider the number $n_2=n_1p_2$ where $p_2$ is a unique prime number dividing $2^{n_1}+1$ . We know that such a $p$ exists by Zsigmondy. Therefore $2^{n_2}+1$ is also divisible by $p_2$ , so we finish the induction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

619 posts

Ilikeminecraft

#69 h Apr 25, 2025, 11:59 PM

Y by

I claim that there \boxed{\text{exists}} a number that has $n$ distinct prime numbers that satisfies our conditions.

Let $k_n = 9 \cdot \prod\limits_{i = 1}^{n - 1} p_i$ be a construction for $n$ . I will prove this with induction.

Clearly, $k_1 = 9$ is a construction for $n = 1.$

Now, assume that $n = l$ has a valid construction. Let $p_{l}$ be a prime dividing $2^{k_l} + 1$ such that $(p_l, k_l).$ I will prove the existence of such a $p_l:$

Notice that $k$ is not even. We have that $\nu_3(2^{k_l} + 1) = \nu_3(k_l) + \nu_3(3) = 1 + 2 = 3,$ and $\nu_{p_i}(2^{k_l} + 1) = \nu_{p_i}\left(\left(2^{k_{i + 1}}\right)^{\frac{k_l}{k_{i + 1}}} + 1\right) = \nu_{p_i}(2^{k_{i + 1}} + 1) + \nu_{p_i}\left(\prod_{j = i + 1}^{l - 1}p_j\right) = 1$ Thus, since $3k_{l} < 2^{k_l} + 1,$ there must exist a non-3 value greater than 1 that divides $\frac{2^{k_l} + 1}{k_l}.$ By picking a $p_i$ that divides that, we can gaurantee $p_i$ exists and is relatively prime to all other primes in $k_l.$

Finally, I claim that $k_{l + 1} = k_lp_{l}$ is a valid construction for $n = l + 1.$ We have that $k_l \mid 2^{k_l} + 1 \mid 2^{k_l p_l} + 1,$ and $p_l \mid 2^{k_lp_l} + 1\implies k_{l + 1} = k_lp_l \mid 2^{k_l p_l} + 1 = 2^{k_{l + 1}} + 1.$

Thus, we are done.

Z K Y