If $n$ has $k$ distinct prime divisors greater than 3, then $2^n+1$ has at least $2^k$ distinct prime divisors (http://www.artofproblemsolving.com/community/c6h17326p118690). Let $p_1< ... <p_k$ be prime divisors of $n,$ and let $q_1,...,q_{2^k}$ be prime divisors of $2^{p_1 \cdot p_2 \cdot ... \cdot p_k}+1.$ By the way we choose $q_1,...,q_{2^k}$ we have (wlog) $q_i|2^{p_i}+1$ for $1 \le i \le n$ and $q_i > 3.$ Now $2^{2p_i} \equiv 1 (mod q_i)$ so $ord|2p_i$ but $ord \neq 2$ since $q_i > 3.$ Hence $p_i|ord$ hence $p_i|q_i-1$ i.e $q_i > p_i+1$ so we have $C(2^n+1) > C(n).$ Some trivial cases are disregarded here, but it's probably easy to examine them.

Let $n=\prod_{i=1}^{k} p_i^{\alpha_i}$ be odd integer, thus by Zsigmondy's theorem we have that $2^n+1$ has at least $$\sum_{i=1}^{k} \alpha_i\geq k$$distinct prime factors . . . $\bigstar$. But note that if $p|2^n+1\Longrightarrow p|2^{gcd(2n,p-1)}-1$, thus if $gcd(2n,p-1)=2$, then $$p|3\Longrightarrow p=3$$, but if $gcd(2n,p-1)>2$ then for some $i\in (1,...,k)$ holds $$p_i|p-1\Longrightarrow p>p_i\ . \ . \ . \ \bigstar \bigstar$$. Thus let $\textbf{First:}$ $p_1=3\Longrightarrow C(2^n+1)-3=C(n)-3\stackrel{\bigstar\text{ and }\bigstar \bigstar}{\Longrightarrow}\text{contradiction}$ since $2^n+1$ has more prime divisors than $n$ and for every one of $n$ there is bigger in $2^n+1$, but note that this holds only if $n$ has prime divisors different from $3$... Thus we're left here with: if $n=3^r$ for some $r\in \mathbb{N}$. Then $C(n)=3\Longrightarrow C(2^n+1)=3\Longrightarrow 2^n+1=3^x$ for some natural $x$. Now \begin{align*} \begin{rcases} & 2^{3^r}+1=3^x\underset{\textbf{LTE}}{\stackrel{3|2+1}{\Longrightarrow}}x=v_3(3^x)=v_3\left(2^{3^r}+1\right) =v_3(3^r)+1=r+1 \\ & 2^{3^r}=3^x-1\underset{\textbf{LTE}}{\stackrel{2|3-1}{\Longrightarrow}}3^r=v_2\left(2^{3^r} \right)=v_2(3^x-1)=v_2(x)+2 \end{rcases}&\Longrightarrow v_2(r+1)+2=3^r>2r\\ &\Longleftrightarrow 2(r+1)<v_2(r+1)+4=\log_2(16(r+1))\\ &\Longleftrightarrow 2^{2(r+1)}<16(r+1)\\ & \Longrightarrow r=1 \end{align*}Thus $\boxed{n=3}$ $\textbf{Second:}$ $3\nmid n$ But again it's not that different case now, since assume that $n$ is not square free first, then $$\sum_{i=1}^{k} \alpha_i>k\stackrel{\bigstar \bigstar}{\Longrightarrow}\text{contradiction}$$since even if we don't count $3$ in $C(2^n+1)$ we'll get contradiction as in previous case... Thus now $n=\prod_{i=1}^{k}p_i$, thus again contradiction with this, since every $p_i>3$ I could've put case when $n$ is even here, too, but there are few technicalities to adjust, but it's basically the same.

SidVicious wrote: If $n$ has $k$ distinct prime divisors greater than 3, then $2^n+1$ has at least $2^k$ distinct prime divisors (http://www.artofproblemsolving.com/community/c6h17326p118690). I am not convinced: the cited post says that number $2^{p_1p_2...p_k}+1$ has at least $2^{k}$ prime factors, but says nothing about prime factors of $2^n+1$ which may not be divisible by $2^{p_1p_2...p_k}+1$(consider $n=2p_1...p_n$)... Garfield wrote: Firstly easy lemma Lemma for every prime $p>3$ we could choose prime $q$ such that $q|2^{p}+1$ and $q>p$. Proof is easy get some $q<p$ we have $2^{2p}\equiv 1 (mod q)$ so $ord_{q}(2)|2p$ so because $q\neq 3$ it must be greater then $p$ so $q>p$. Now let $n=\prod _{1}^{n} p_{i}$ clearly $2^{p_{i}}+1|2^{n}+1$ and $(2^{p_{i}}+1,2^{p_{j}}+1)=1$ so for every $p_{i}$ we could choose larger $q|2^{n}+1$.Ok now assume $n=3^{k}$ then $2^{3^{k}}+1=3^{l}$ which is true only for $k=1$ (trivial LTE or ovekill Catalan's conjecture) so only solution $n=3$. EDIT:Adding details. Now this one is certainly wrong, for the very same reason:$2^{p_{i}}+1|2^{n}+1$ is surely not true for even $n$! The elementary solution(without invoking Zsigmondy's theorem) uses similar ideas as above but much more technical care is required.

aleksam wrote: SidVicious wrote: If $n$ has $k$ distinct prime divisors greater than 3, then $2^n+1$ has at least $2^k$ distinct prime divisors (http://www.artofproblemsolving.com/community/c6h17326p118690). I am not convinced: the cited post says that number $2^{p_1p_2...p_k}+1$ has at least $2^{k}$ prime factors, but says nothing about prime factors of $2^n+1$ which may not be divisible by $2^{p_1p_2...p_k}+1$(consider $n=2p_1...p_n$)... Garfield wrote: Firstly easy lemma Lemma for every prime $p>3$ we could choose prime $q$ such that $q|2^{p}+1$ and $q>p$. Proof is easy get some $q<p$ we have $2^{2p}\equiv 1 (mod q)$ so $ord_{q}(2)|2p$ so because $q\neq 3$ it must be greater then $p$ so $q>p$. Now let $n=\prod _{1}^{n} p_{i}$ clearly $2^{p_{i}}+1|2^{n}+1$ and $(2^{p_{i}}+1,2^{p_{j}}+1)=1$ so for every $p_{i}$ we could choose larger $q|2^{n}+1$.Ok now assume $n=3^{k}$ then $2^{3^{k}}+1=3^{l}$ which is true only for $k=1$ (trivial LTE or ovekill Catalan's conjecture) so only solution $n=3$. EDIT:Adding details. Now this one is certainly wrong, for the very same reason:$2^{p_{i}}+1|2^{n}+1$ is surely not true for even $n$! The elementary solution(without invoking Zsigmondy's theorem) uses similar ideas as above but much more technical care is required. You are definitely right,I will try to modificate lemma: Lemma: For every prime $p>3$ we could choose prime $q$ such that $q|2^{p\cdot 2^{k}}+1$ and $q>p$. Proof: Asumme that for every prime $q$ such that $q|2^{p\cdot 2^{k}}+1$ we have $ord_{q}(2)=2^{s}$,but then we could use simple claim that $(2^{x}+1,2^{y}+1)=2^{(x,y)}+1$ on numbers $2^{p\cdot 2^{k}}+1$ and $2^{2^{k}}+1$ so we have at least one prime $q$ such that $ord_{q}(2)$ doesn't divide $2^{k}$ because if it does we would have that $q|2^{2^{k}}+1$ so they would have same set of prime divisors but use $LTE$ on $2^{2^{k}\cdot p}+1^{p}$ and we have that $v_{q}(2^{p\cdot 2^{k}}+1)=v_{q}(2^{2^{k}}+1)$ for every $q$ so $2^{p\cdot 2^{k}}+1=2^{2^{k}}+1$ contradiction.So now we have $q$ such that $(ord_{q}(2),p)\neq 1$ so $q>p$. Now because $2^{2^{k}\cdot p}+1|2^{2^{k}\cdot \prod p_{i}}+1$ ,$p_{i}\neq 2$ and using $(2^{x}+1,2^{y}+1)=2^{(x,y)}+1$ rest be should fine,off course if $n=2^{k}$ we're done because $C(2^{k})=2<C(2^{2^{k}}+1)$.

Garfield wrote: You are definitely right,I will try to modificate lemma: Lemma: For every prime $p>3$ we could choose prime $q$ such that $q|2^{p\cdot 2^{k}}+1$ and $q>p$. Proof: Asumme that for every prime $q$ such that $q|2^{p\cdot 2^{k}}+1$ we have $ord_{q}(2)=2^{s}$,but then we could use simple claim that $(2^{x}+1,2^{y}+1)=2^{(x,y)}+1$ ... You meant $(2^{x}-1,2^{y}-1)=2^{(x,y)}-1$? If I am not mistaken, this doesn't hold in general, but in this case, it happens to hold. Garfield wrote: ...on numbers $2^{p\cdot 2^{k}}+1$ and $2^{2^{k}}+1$ so we have at least one prime $q$ such that $ord_{q}(2)$ doesn't divide $2^{k}$ because if it does we would have that $q|2^{2^{k}}+1$ Now again, if $ord_{q}(2)|2^k$, that means $2^{2^k}\equiv 1(\mod q)$, and so $q|2^{2^k}-1$, and from there I don't see how we could proceed...

aleksam wrote: Garfield wrote: You are definitely right,I will try to modificate lemma: Lemma: For every prime $p>3$ we could choose prime $q$ such that $q|2^{p\cdot 2^{k}}+1$ and $q>p$. Proof: Asumme that for every prime $q$ such that $q|2^{p\cdot 2^{k}}+1$ we have $ord_{q}(2)=2^{s}$,but then we could use simple claim that $(2^{x}+1,2^{y}+1)=2^{(x,y)}+1$ ... You meant $(2^{x}-1,2^{y}-1)=2^{(x,y)}-1$? If I am not mistaken, this doesn't hold in general, but in this case, it happens to hold. Garfield wrote: ...on numbers $2^{p\cdot 2^{k}}+1$ and $2^{2^{k}}+1$ so we have at least one prime $q$ such that $ord_{q}(2)$ doesn't divide $2^{k}$ because if it does we would have that $q|2^{2^{k}}+1$ Now again, if $ord_{q}(2)|2^k$, that means $2^{2^k}\equiv 1(\mod q)$, and so $q|2^{2^k}-1$, and from there I don't see how we could proceed... I made few minor mistakes with orders and didn't used $(2^{x}-1,2^{y}-1)=2^{(x,y)}-1$ in solution. So again $q|2^{2^{k}\cdot p}+1$ so we have $2^{2\cdot 2^{k}\cdot p}=2^{2^{k+1}\cdot p}\equiv 1 (mod q)$ so $ord_{q}(2)|2^{k+1}\cdot p$ so because we assumed $(p,ord_{q}(2))=1$ we have $ord_{q}(2)|2^{k+1}$ and $ord_{q}(2)$ doesn't divide $2^{k}$ (if it does divide $2^{2^{k}\cdot p}+1\equiv 2$ but it's$0$).So $2^{2^{k}}\equiv -1 (mod q)$ so every prime which divide $2^{2^{k}\cdot p}+1$ divide $2^{2^{k}}+1$ too ,now use LTE on $2^{2^{k}\cdot p}+1$ so $v_{q}(2^{p\cdot 2^{k}}+1)=v_{q}(2^{2^{k}}+1)$ because $(q,p)=1$ so we have $2^{2^{k}\cdot p}+1=2^{2^{k}}+1$,contradiction! $(ord_{q}(2), p)\neq 1$ so $q>p$.

mihajlon wrote: Let $n=\prod_{i=1}^{k} p_i^{\alpha_i}$ be odd integer, thus by Zsigmondy's theorem we have that $2^n+1$ has at least $$\sum_{i=1}^{k} \alpha_i\geq k$$distinct prime factors . . . $\bigstar$. So how do you get that by Zsigmondy's theorem ?

Is it true?: (Briefly) By Zsigmondy's theorem,we choose such prime $p$ $\Rightarrow$ $2^{2n}-1 \equiv 0 \pmod p$ and $2^k - 1 \not\equiv 0 \pmod p$ for all $2n > k$ Then By Fermat's, we get $2^{p-1} - 1 \equiv 0 \pmod p$ Therefore $2n/p-1$ and $p>2n$ $\Rightarrow$ $C(2^n +1)>C(n)$ Unless the Exception in Zsigmondy's theorem, $2n=6$ $\Rightarrow$ $n=3$ QED

eager wrote: Is it true?: (Briefly) By Zsigmondy's theorem,we choose such prime $p$ $\Rightarrow$ $2^{2n}-1 \equiv 0 \pmod p$ and $2^k - 1 \not\equiv 0 \pmod p$ for all $2n > k$ Then By Fermat's, we get $2^{p-1} - 1 \equiv 0 \pmod p$ Therefore $2n/p-1$ and $p>2n$ $\Rightarrow$ $C(2^n +1)>C(n)$ Unless the Exception in Zsigmondy's theorem, $2n=6$ $\Rightarrow$ $n=3$ QED Very short and nice solution, but I have a question. As I know we can't use Zsigmondy's theorem during IMO due to it's overkilling power. Can't we use it in other contests, too (Like IZhO, BMO and others)?

Jalil_Huseynov wrote: eager wrote: Is it true?: (Briefly) By Zsigmondy's theorem,we choose such prime $p$ $\Rightarrow$ $2^{2n}-1 \equiv 0 \pmod p$ and $2^k - 1 \not\equiv 0 \pmod p$ for all $2n > k$ Then By Fermat's, we get $2^{p-1} - 1 \equiv 0 \pmod p$ Therefore $2n/p-1$ and $p>2n$ $\Rightarrow$ $C(2^n +1)>C(n)$ Unless the Exception in Zsigmondy's theorem, $2n=6$ $\Rightarrow$ $n=3$ QED Very short and nice solution, but I have a question. As I know we can't use Zsigmondy's theorem during IMO due to it's overkilling power. Can't we use it in other contests, too (Like IZhO, BMO and others)? Well actually I’m not sure you can’t use Zsigmondy's theorem on IMO. It’s not just very often.

I know like that since it kills the problem quickly, we can't use it, or if we will use, we should prove it (I mean we should write proof of this theorem completely on our papers). It's something like Fermat's theorem: $a^n+b^n=c^n$ has no non-trivial solution for $n>2$. We can't use this theorem (Fermat's) during contest without proof and it's proof is very hard and long.

nice problem.