Prove: There exists a positive integer $n$ with $2021$ prime divisors, satisfying $n|2^n+1$.
Problem
Source: 2021 IMOC qualification problem, N3
Tags: IMOC, number theory
30.12.2021 12:02
If they don't have to be distinct then $n=3^{2021}$ works.
30.12.2021 12:25
The numbers satisfying the mentioned division property are Novak numbers.
30.12.2021 12:26
If we want distinct primes, then start with the following construction: $a_1=3^2$, which has one prime factor. Now take $p_{n+1}$ be a primitive prime divisor of $2^{a_n}+1$, which exists by Zsigmondy (note that the exception would have been only if $a_1=3$) and simply take $a_{n+1}=p_{n+1}a_n$. Since $p_{n+1}$ is a primitive divisor, it clearly isn't equal to the previous prime, and so $a_{n+1}$ has one more distinct prime factor. Therefore, by induction $a_n$ can have as many distinct prime factors as we want.
30.12.2021 14:36
Related problem https://artofproblemsolving.com/community/c6h57607p354115
30.12.2021 21:20
Zsigmondy theorem
23.05.2023 02:19
CrazyInMath wrote: Prove: There exists a positive integer $n$ with $2021$ prime divisors, satisfying $n|2^n+1$. $n=3^2$ satisfies the condition By Zsigmondy's Theorem: $\exists$ prime $p_1\neq 3/ p|2^9-1$ We will prove that $n=3^2p_1:$ $9|2^9+1|2^{9p_1}$ $p_1|2^9+1|2^{9p_1}$ $\Rightarrow 3^2p_1|2^{9p_1}+1$ By induction, suppose that it satisfies for $n=3^2p_1p_2...p_k:$ By Zsigmondy's Theorem: $\exists$ prime $p_{k+1}\neq 3,p_1,p_2,\ldots ,p_{k+1}/ p|2^{9p_1p_2\ldots p_k}+1$ $9|2^9+1|2^{9p_1p_2...p_k}+1$ $p_1|2^9+1|2^{9p_1p_2...p_k}+1$ $p_2|2^{9p_1}+1|2^{9p_1p_2...p_k}+1$ $\ldots$ $p_{k+1}|2^{9p_1p_2\ldots p_k}+1|2^{9p_1p_2...p_k}+1$ $\Rightarrow 3^2p_1p_2 \ldots p_k|2^{9p_1p_2...p_k}+1 $ the induction is complete. $\Rightarrow$ we simply choose $n=3^2p_1p_2 \ldots {p_{2020}} _\blacksquare$