WakeUp wrote: Prove that there are infinitely many positive integers $n$ such that $2^{2^n+1}+1$ is divisible by $n$ but $2^n+1$ is not. (Russia) Valery Senderov http://rmm.lbi.ro/index.php?id=solutions_math

There is also a strengthening from the KöMaL contest: A. 562. wrote: Let $f(k)=2^k+1$ for arbitrary positive integer $k$. Is there any positive integer $n$ which divides $f(f(n))$, but does not divide $f(f(f(n)))$? (This is stronger since $n\nmid f^3(n)\implies n\nmid f(n)$, as $a\mid b\Longleftrightarrow f(a)\mid f(b)$ for odd $a,b$. And of course, if $n$ works then so does $f(n)=2^n+1$.) Note that $f(k)=-[(-2)^k-1]$ for odd $k$. Start with some $n_0$ sufficiently large (this is to ensure that Zsigmondy works, even though we only need the weaker form for all large exponents ). By Zsigmondy, we first take a prime $p>3$ such that $\text{ord}{}_p(-2) = 3^{n_0}\equiv1\pmod{2}$ and then a prime $q>3$ such that $\text{ord}{}_q(-2) = 3^{n_0}p\equiv1\pmod{2}$. Since $3^{n_0}\mid f(3^{n_0})$ (e.g. by LTE) and $p\mid f(3^{n_0})$, we have $q\mid f(3^{n_0}p)\mid f^2(3^{n_0})$, whence $3^{n_0}q\mid f^2(3^{n_0}q)$. Now it suffices to find an odd prime $r>3$ such that $r\mid f^2(3^{n_0}qr)$ but $r\nmid f^3(3^{n_0}qr)$, as we can then take $n=3^{n_0}qr$. We show that any prime $r$ such that $\text{ord}{}_r(-2) = f(3^{n_0}q)\equiv1\pmod{2}$ (which exists by Zsigmondy) works. Clearly such $r$ divides $f^2(3^{n_0}q)\mid f^2(3^{n_0}qr)$. Suppose for contradiction that $r\mid f^3(3^{n_0}qr)$; then by the order condition on $r$, \[f(3^{n_0}q)\mid f^2(3^{n_0}qr)\implies 3^{n_0}q\mid f(3^{n_0}qr).\]But $f(3^{n_0}qr) \equiv f(3^{n_0}r)\pmod{q}$ by Fermat's little theorem, so by the order condition on $q$, $3^{n_0}p\mid 3^{n_0}r$, contradiction ($p\ne r$ since $\text{ord}{}_p(-2) \ne \text{ord}{}_r(-2)$ by construction).

Assume that $n$ satisfies the conditions of the problem.We claim that the number $N = 2^n + 1 > n$ also satisfies these conditions Firstly, since $N$ is not divisible by $n$ , $\Rightarrow 2^N+1$ is not divisible by $2^n+1$ $\Rightarrow 2^N+1$ is not divisible by $N$ Next,since $n|2^{2^{n}+1}+1=2^N+1$ thus confirming our claim Sorry I not good english

The Zsigmondy solution is real slick. Using Zsigmondy, $\exists p_n \in \mathbb{P}$ such that $p_n|2^{2^n+1}+1$ but $p_n \nmid 2^a+1 \forall a\le 2^n$. We let $n=3^k.p_{3^k}$. Now, observe that $v_3(2^{2^n+1}+1)=2+v_3(n)=2+k$. Therefore, $3^k|3^{k+2}|2^{2^{3^kp_{3^k}}+1}+1$. And obviously, $p_k|2^{2^{3^k}+1}+1|2^{2^{3^kp_k}+1}+1$. And also, $p_k \nmid 2^{3^k.p_{3^k}}+1$ by definition. Therefore, $n=3^kp_{3^k}$ satisfies the condition.

Multiple ways to finish the problem exist Main idea is $(2^a+1, 2^b+1) = 2^{(a,b)}+1$

Noting that $n=57$ works and that if $m$ works then so does $2^m-1$ we are done.

Not a difficult problem. We prove that if $n$ works, so does $2^n+1$. Lemma. If $a,b$ is odd, $2^a+1|2^b+1 \iff a|b$. Proof. if direction trivial, only if direction Euclidean Algorithm. Since $n|2^{2^n+1}+1$, we have $2^n+1|2^{2^{2^n+1}+1}+1$. Also, since $n$ is not a divisor of $2^n+1$, $2^n+1$ is not a divisor of $2^{2^n+1}+1$. Therefore, $2^n+1$ satisfies our conditions. Since $2^n+1>n$ for all $n$, it suffices to find one $n$ that works. We search for an odd number that is a product of two primes. $n=57$ works well. Done!

Define the sequence $n_0, n_1, \dots$ as follows. Set $n_0 = 3$, and then for $k \ge 1$ we let $n_k = pn_{k-1}$ where $p$ is a primitive prime divisor of $2^{2^{n_{k-1}}+1}+1$ (by Zsigmondy). For example, $n_1 = 57$. This sequence of $n_k$'s works for $k \ge 1$, by construction. It's very similar to IMO 2000 Problem 5.

How would one come up with the sequence $n_0, n_1, ...$ and $n_1=57$? Thanks!

MathPanda1 wrote: How would one come up with the sequence $n_0, n_1, ...$ and $n_1=57$? Thanks! You'll notice I said for example we have $n_1 = 57$: you compute the value of $n_1$ from $n_0$ in my recurrence. As for how to come up with $(n_i)$ in the first place, it is just copying the solution to IMO 2000/5. (The same approach will solve IMO 2000/5 with initial value $9$.)

We construct an infinite sequence of positive integers $n_0\mid n_1\mid n_2\mid\cdots$ that satisfy the condition of the problem. We start by noting that $n_0=57$ satisfies the condition of the problem. To find this, you basically experiment a lot and out $57=3\cdot 19$ pops. I recall restricting my search space to primes $3\pmod{4}$ because of some heuristic, being disappointed that $19$ almost works, and then realizing that I can just multiply it by $3$ to get something that works. We have the following lemma that allows us to generate solutions. Lemma: Suppose $n$ is a positive integer such that $n\nmid 2^n+1$ but $n\mid 2^{2^n+1}+1$. If $p\mid 2^{2^n+1}+1$ is a prime such that $p\nmid n,2^n+1$, then $np$ is also a solution to the given condition. Proof: We first verify that $np\nmid 2^{np}+1$. Indeed, we have that $2^{np}+1\equiv 2^n+1\pmod{p}$ by Fermat's little theorem, but $p\nmid 2^n+1$, so $p\nmid 2^{np}+1$, as desired. Now, we show that $np\mid 2^{2^{np}+1}+1=:x$. We see that $2^{np}+1=(2^n+1)k$ for some positive integer $k$, so $x=2^{k(2^n+1)}+1$, which is also divisible by $2^{2^n+1}+1$, which is divisible by $np$ (since $\gcd(p,n)=1$), so $np\mid 2^{2^{np}+1}+1$, as desired. $\blacksquare$ Note that $n_0\mid 2^9+1$, so we may select a prime $p_1\mid 2^{2^{n_0}+1}+1$ such that $p_1\nmid 2^9+1,2^{n_0}+1$ by Zsigmondy. Thus, $n_1=n_0p_1$ is also a solution. Now, pick a prime $p_2\mid 2^{2^{n_1}+1}+1$ such that $p_2\nmid 2^{n_1}+1,n_1$, which again exists by Zsigmondy because $n_1\mid 2^{2^{n_0}+1}+1$. Thus, $n_2=n_1p_2$ also works. Continuing in this fashion, we can always add a new prime at each step by Zsigmondy, so we have our infinite sequence of solutions, as desired.

Another question:prove that (2^n-1)+1is not divided by n

Let $k\ge2$ be a positive integer. We claim \[n=\frac{2^{3^k}+1}{9}\]works. By LTE, $\nu_3(n)=\nu_3(2^{3^k}+1)-2=1+k-2=k-1>0$. First we check that \[n\nmid 2^n+1.\]By, say, a roots of unity argument with the polynomials $x^{3^k}+1$ and $x^n+1$ and checking the $\nu_3$ values with LTE again, we have \[\gcd(n,2^n+1)=\frac{2^{3^{k-1}}+1}{3}.\]As the ratio between $n$ and $\gcd(n,2^n+1)$ is $\frac{1}{3}\cdot (2^{2\cdot3^{k-1}}-2^{3^{k-1}}+1)\ge \frac{1}{3}\cdot (64-8+1)=19$, we are done with this part. Now, remark that by LTE, $\nu_3(2^n+1)=\nu_3(n)+1=k$ so $2^{3^k}+1$ divides $2^{2^n+1}+1$ and we are done with the second part.

Observe that $57 \nmid 2^{57}+1$ (just analyze $\pmod{3}$). Furthermore, $ord_{57}2=18,ord_{19}2=18$, so since $18|2^{58}+2$, $57|2^{2^{58}+2}-1$, but since $3,19 \nmid 2^{2^{57}+1}-1$, we have that $57|2^{2^{57}+1}+1$, so $57$ satisfies the condition of the problem. Now, notice that if $n$ is a solution, so does, $2^n+1$, because $n \nmid 2^n+1 \implies 2^n+1 \nmid 2^{2^n+1}+1$ (otherwise we would have $n|2^n+1$) and $2^n+1|2^{2^{2^n+1}+1}+1$. Hence, since we found an initial solution, by the previous observation, we have infinitely solutions, as desired. $\blacksquare$

mahanmath wrote:

How you can come up with such sequence like (an) and (bn)

Fake sol

laikhanhhoang_3011 wrote:

God

Here's the Zsigmondy solution. Pick a primitive $p_k \mid a_{k+1} = 2^{3^k} + 1$ for each $k$. We will construct an infinite sequence $\{n_k\}$ of integers that work. Set $n_k = 3^k \cdot p_k$ for each $k$. Notice that $$a_{k+1} \mid 2^{2^n_k + 1} + 1 \iff 3^{k+1} \mid 2^{n_k} +1,$$which is true for $\nu_p$ reasons. Thus $p_k$ divides the expression and obviously so does $3^k$. On the other hand, $2^{n_k} + 1 \equiv a_k \pmod p^k$, so the sequence $\{n_k\}$ satisfies both conditions.

Let $k$ be a positive integer. Now, let $p$ be a prime such that $p$ divides $$2^{2^{3^k}+1}+1$$but not $2^{3^k}+1$ (such a $p$ exists by Zsigmondy). Note that $p>3$. Then, we claim that $n=p\cdot 3^k$ works. We will first show that $$p\cdot 3^k\mid 2^{2^{3^k\cdot p}+1}+1.$$Now, note that $$2^{2^{3^k}+1}+1|2^{2^{3^k\cdot p}+1}+1,$$since $2^{3^k}+1\mid 2^{3^k\cdot p}+1$ as $p$ is odd, so $$p\mid 2^{2^{3^k\cdot p}+1}+1.$$Then, $$v_3(2^{2^{3^k\cdot p}+1}+1)=1+v_3(2^{3^k\cdot p}+1)=2+v_3(3^k\cdot p)=k+2,$$so it is divisible by $3^k$. Since $p>3$, divisible by $p$ and $3^k$ implies divisible by $p\cdot 3^k$. Then, we will show that $p$ does not divide $2^{3^k\cdot p}+1.$ We have $$2^{3^k\cdot p}+1\equiv (2^p)^{3^k}+1\equiv 2^{3^k}+1\pmod p.$$However, since $p$ is defined in a way so that $p$ does not divide $2^{3^k}+1$, so $p$ also does not divide $2^{3^k\cdot p}+1.$ Thus, this construction works for all positive integers $k$, so we have an infinite number of solutions.

We call the number $n>1$ Romanian if $n \nmid 2^n+1$ and $n \mid 2^{2^n+1}+1.$ First of all, notice that $57$ is Romanian. Suppose $p$ is a primitive prime dividing $(2^{2^n+1})^2-1$. I claim that $np$ is also Romanian. Since $p\mid(2^{2^n+1})^2-1 = (2^{2^n+1}+1)(2^{2^n+1}-1)$ and $p\nmid 2^{2^n+1}-1$, we get $p\mid 2^{2^n+1}+1.$ Similarly, since $p\nmid2^n-1$ and $p\nmid2^{2n}-1=(2^n-1)(2^n+1)$, we get $p\nmid 2^n+1.$ Moreover, from $p\nmid 2^{\varphi(n)}-1$ and $n\mid2^{\varphi(n)}-1$ from Euler (here we use the fact that $n$ is odd), we get that $(n,p)=1$. Now we show that $np\nmid2^{np}+1$. Suppose the contrary, i.e. $p\mid np\mid 2^{np}+1$. However, $(2^n)^p+1\equiv2^n+1\not\equiv0 \pmod{p}$, so we are done. Now we show that $np\mid2^{2^{np}+1}+1$. Since $(n,p)=1$, it is enough to show that $n\mid2^{2^{np}+1}+1$ and $p\mid2^{2^{np}+1}+1$. Claim $1$: $2^{2^n+1}+1\mid2^{2^{np}+1}+1$. Proof: Indeed, notice that $2^{np}+1=(2^n+1)K$, where $K=(2^n)^{p-1}-(2^n)^{p-2}+\dots-2^n+1$ is odd. Thus, $$2^{2^{np}+1}+1\equiv2^{(2^n+1)K}+1\equiv(-1)^K+1\equiv0 \pmod{2^{2^n+1}+1},$$so we are done. Now since $p\mid2^{2^n+1}+1$ and $n\mid2^{2^n+1}+1$, we are done.

We remember the following well-know lemma $\textcolor{blue}{\text{Claim}\hspace{0.1cm} a^u+b^u\mid a^k+b^k \iff u\mid k}$

First notice that $n = 57$ works. The following claim finishes Claim: If $n$ works, then there exists a prime such that $np$ also works. Proof: By Zsigmondy, take $p$ as a primitive prime divisor of $2^{2^n+1}+1$. We must have \[p \nmid 2^{2^n+1 - \varphi(n)}+1\]However, Euler's Theorem combined with the fact that $n$ works implies \[2^{2^n+1-\varphi(n)} +1 \equiv 0 \pmod n \implies p \nmid n\]since $p$ is prime. Thus $\gcd(n,p) = 1$, so \[np \mid 2^{2^n+1}+1 \mid 2^{2^{np}+1}+1\]where the second divisor statement is because \[2^n+1 \mid 2^{np}+1 \implies 2^{(2^n+1) \cdot \text{something}}+1 = 2^{2^{np}+1}+1\]and since the ``something" is odd, it implies that $2^{2^n+1}+1 \mid 2^{2^{np}+1}+1$. Lastly, note that $p \nmid 2^{np}+1$ since if it did, then \[(2^n)^p +1 \equiv 0 \pmod p \implies 2^n +1 \equiv 0 \pmod p\]which contradicts the fact that $p$ is a primitive prime divisor of $2^{2^n+1}+1$. Thus, since $p \nmid 2^{np}+1$, we have $np \nmid 2^{np}+1$. Combining with above implies that $np$ indeed works, so we're done. $\square$

I personally found this problem pretty hard for the Problem 4 spot. We claim that the following recursively defined sequence $(a_n)_{n\ge 1}$ all satisfy the given divisibility conditions, \[a_1 = 57 , a_n = 2^{a_{n-1}}+1 \text{ for all } n >1\]which we shall prove via induction. For the base case note that, \[2^{57} +1 \equiv 2^{54+3}+1 \equiv 2^3 +1 \equiv 9 \not \equiv 0 \pmod{19}\]so $57 \nmid 2^{57+1}$. Also, \[\nu_3(2^{57}+1) = \nu_3(2+1)+\nu_3(57)=2\]by Lifting the Exponent Lemma so $9 \mid 2^{57}+1$. Since this is clearly odd, this means $2^{57}+1 \equiv 9 \pmod{18}$. Thus, \[2^{2^{57}+1}+1 \equiv 2^9 +1 \equiv 0 \pmod{19}\]so $19 \mid 2^{2^{57}+1}+1$, and since it is clearly also divisible by 3, $57 \mid 2^{2^{57}+1}+1$. Thus, $a_1=57$ indeed satisfies the desired conditons. Now, we show that if $a_k$ satisies the given divisibility constraints then so does $a_{k+1}$. It is a well known result that for odd positive integers $a$ and $b$, $2^{a}+1 \mid 2^b +1$ if and only if $a\mid b$. Now, since $a_k \nmid 2^{a_k}+1$, \[a_{k+1}=2^{a_k}+1 \nmid 2^{2^{a_k}+1}+1 = 2^{a_{k+1}}+1\]Further since $a_k \mid 2^{2^{a_k}+1}+1$, \[a_{k+1}=2^{a_k}+1 \mid 2^{2^{2^{a_k}+1}+1}+1=2^{2^{a_{k+1}}+1}+1\]which implies that $a_{k+1}$ also satisfies the given conditions. To finish off, simply note that this sequence is strictly increasing since, \[a_{i+1}=2^{a_i}+1 > 2^{a_i} \ge a_i\]for all positive integers $i$ and this sequence consists of pairwise distinct numbers, which yields an infinite family of solutions to the given problem as desired.

Is there a prime $n$ satisfying the condition?