Cancer,how did you get this problem. Is this your own or... I think that I saw it somewhere Maybe it was in some national TST or... I can't remember

check the PEN website, I have seen it there I think

What is the PEN website?

The statement can be proved using induction on $n$. (the stronger form) Let the statement be $T(n)$ : there exist a natural no. $m(n)$ such that $n |$ $(2^{m}+m)$ clearly $T(1)$ is true. assume that $T(k)$ is true for all $1 \leq k < n$. Now we have to prove truth of $T(n)$ suppose $m = kn-2^{x}$ for some integers(positive) $k$ and $x$ then $(2^{m}+m)$ $=$ $kn+2^{x}(2^{kn-(2^{x}+x)}-1)$ Now we are done if there exist a positive integer $l$ such that $kn-(2^{x}+x)$ $=$ $l \phi (n)$ because then $n |$ $(2^{l \phi (n)}-1)$ implies $n |$ $(kn+2^{x}(2^{kn-(2^{x}+x)}-1))$ $=$ $(2^{m}+m)$. i.e, there must exist solutions in positive integers of the equation $kn-l \phi (n)$ $=$ $2^{x}+x$ using euclid's algorithm we can find integral solutions for $(k,l)$ on generalising, $k$ and $l$ can be made sufficiently large(positive) by varying the parameter given that $gcd(n, \phi (n)) |$ $2^{x}+x$ but since $gcd(n, \phi (n)) < n$ therefore by assumption there must exist such $x$ and hence $T(n)$ is true given truth of $T(k)$ for all $1 \leq k < n$. hence, $T(n)$ is true for all natural no.s $n$.

rohitsingh0812 wrote: $n |$ $(2^{l \phi (n)}-1)$ I think it is not true for even $n$? I solved it with induction on number of odd prime divisors of $n$.Try it. P.S.It is from ISL2006-N7

i am sorry for the mistake....but now i think its corrected... The statement can be proved using induction on $n$. (the stronger form) Let the statement be $T(n)$ : there exist a natural no. $m(n)$ such that $n |$ $(2^{m}+m)$ and $m > s$ where $s$ is the largest natural no. such that $2^{s}| n$ clearly $T(1)$ is true.$(m>0,s=0)$ assume that $T(k)$ is true for all $1 \leq k < n$. Now we have to prove truth of $T(n)$ suppose $m = kn-2^{x}$ for some integers(positive) $k$ and $x$ then $(2^{m}+m)$ $=$ $kn+2^{x}(2^{kn-(2^{x}+x)}-1)$ Now we are done if there exist a positive integer $l$ such that $kn-(2^{x}+x)$ $=$ $l \phi (n)$ because then $\frac{n}{2^{s}}|$ $(2^{l \phi (n)}-1)$ implies $n |$ $(kn+2^{x}(2^{kn-(2^{x}+x)}-1))$ $=$ $(2^{m}+m)$. for $x \geq s$ i.e, there must exist solutions in positive integers of the equation $kn-l \phi (n)$ $=$ $2^{x}+x$ with $x \geq s$ using euclid's algorithm we can find integral solutions for $(k,l)$ on generalising, $k$ and $l$ can be made sufficiently large(positive) by varying the parameter given that $gcd(n, \phi (n)) |$ $2^{x}+x$ and $x \geq s$ but since $gcd(n, \phi (n)) < n$ therefore by assumption there must exist such $x$ with $x > s-1$ i.e $x \geq s$ because $2^{s-1}\parallel gcd(n, \phi (n))$(for $s \geq 1$, $s=0$ does not require this bound) and hence $T(n)$ is true given truth of $T(k)$ for all $1 \leq k < n$. hence, $T(n)$ is true for all natural no.s $n$.

baz wrote: Could you supply a link? I am not sure where this is. Thanks. See here //http://www.problem-solving.be/pen/

Please give the link of the problem .

I think that it is impossible that this problem can be found on PEN project page becouse Quote: P.S.It is from ISL2006-N7 Or it appeared in ISL as copied problem :

Also, note that this problem is a special case of http://www.mathlinks.ro/Forum/viewtopic.php?p=354533#p354533 (it's strange to put such a well-known result into an ISL)

The Brazilian leader at this IMO vetoed this problem rightaway, because of its appearance in the Brazilian Math Olympiad.

Hi ; Lemma : For every natural $n$ there is a $m$ such that $n$ divide $a^m+m$, where $a$ and $m$ are both natural . Best Regard

We proceed by induction on $n$. Obviously this statement holds for $n=1$. Now assume $n>1$ and this statement holds for every natural number less than $n$. Consider two cases:

Thus our inductive steps are complete and the statement is true for all natural $n$s.

Well darn it...

Let $a_{m}=2^m$ with $m\ge0$ notice that the primes that divide one term of the sequence is finite $\therefore$ from Kobayashi the sequence $b_{m}=2^m+m$ where $m\ge1$ has infinite number of prime divisors.

Borbas wrote: Let $a_{m}=2^m$ with $m\ge0$ notice that the primes that divide one term of the sequence is finite $\therefore$ from Kobayashi the sequence $b_{m}=2^m+m$ where $m\ge1$ has infinite number of prime divisors. That doesn't give you anything important for this problem...

This problem looks like you have to use Kobayashi in some way.

Borbas wrote: This problem looks like you have to use Kobayashi in some way. But you probably can not... There are many problems of this kind, where you can notice by Kobayashi that there are inf prime divisors, but often not that useful...

We use the technique of ``haha induction go brrr'' except phrase induction as the well ordering principle. Suppose the claim is not true, then there exists some minimal $n$ such that no such $m$ exists. Clearly, $n\ne 1$ and $n\ne p$ for any prime $p\ne 2$; take $m=p-1$. If $n$ is a power of $2$, simply take $m=n$. Now, let $p$ denote the maximal prime divisor of $n$ and write $n=p^k\ell$ with an integer $\ell$ with $p\nmid \ell$. As $n$ is minimal, there exists some $m'$ with $p^{k-1}\ell\mid 2^{m'}+m'$. Now, let $a=\phi(p^k)\ell\phi(\ell)$. It is clear that $p^{k-1}\ell\mid 2^{m'+ba}+m'+ba$ for any nonnegative integer $b$. Moreover, we have $2^{m'+ba}+m'+ba\equiv 2^{m'}+m'+ba\pmod{p^k}$ for all nonnegative integers $b$. As $\nu_p(a) = k-1$ and $p^{k-1}\mid 2^{m'}+m'$, some $b$ must exist with $p^k,p^{k-1}\ell\mid 2^{m'+ba}+m'+ba$, so $m'+ba$ works, a contradiction.

Consider a positive integer $n.$ For the sake of induction assume the statement holds true for all positive integers less than $n.$ If $n$ is prime take $m=n-1.$ Otherwise let $n$'s prime factorization be $p_1^{e_1}p_2^{e_2} \dots p_k^{e_k}.$ If $n$ is a power of two let $m=n.$ Otherwise, define $q = \frac{n}{p_1} > 1.$ Define $m_1$ such that $2^{m_1}+m_1 \equiv rq \pmod{n}$ for a positive integer $r.$ We may define an integer $s$ such that $(p_2-1)(p_3-1) \dots (p_k-1) s \equiv 1 \pmod{p_1}.$ Then $r \times \phi(n) \times s \times p_2p_3 \dots p_k \equiv r \times q \times (p-1) \equiv - rq \pmod{n}.$ Taking $m= r \times \phi(n) \times s \times p_2p_3 \dots p_k +m_1$ works noting that $m$ has at least as many factors of $2$ in its prime factorization as $n$ and so does $2^m.$

We will prove the problem by induction on $n$. If the problem is true for $i = {\kern 1pt} \overline {1,n - 1} $, consider two positive integers a,b satisfying \[\left\{ \begin{gathered} {2^a} + a \vdots d = \gcd \left( {n,\varphi \left( n \right)} \right) \hfill \\ b \equiv \frac{{{2^a} + a}}{d}\,\,\,\,\left( {\bmod \,\,\frac{n}{d}} \right) \hfill \\ \end{gathered} \right.\]Let $t = a - b\left( {n - \varphi \left( n \right)} \right)$ then \[\left\{ \begin{gathered} a - t \vdots \left( {n - \varphi \left( n \right)} \right) \hfill \\ {2^a} + t \vdots n \hfill \\ \end{gathered} \right.\]Now, there exists a positive integer $x$ satisfying \[\left\{ \begin{gathered} x \equiv a\,\,\left( {\bmod \,\,\varphi \left( n \right)} \right) \hfill \\ x \equiv t\,\,\left( {\bmod \,\,n} \right) \hfill \\ \end{gathered} \right.\]

Pick an integer $m$ such that \begin{align*} m &\equiv m_0\pmod{ \varphi(n)} \\ m &\equiv -2^{m_0}\pmod {n}. \end{align*}In order to have solutions to the congruencies $\gcd(\varphi(n),n)|2^{m_0}+m_0$ which can be established by induction.

We will prove a stronger result. Call $n\in\mathbb{N}$ good if for any $c_1,c_2\in\mathbb{N}$ there exist infinitely many $m\in\mathbb{N}$ such that \[n\mid c_1\cdot 2^{m \cdot c_2}+m.\]We will prove that all $n$ are good, which obviously implies our problem. We will do so by induction. Observe that $1,2$ are good and assume that $1,2,...,n-1$ are good. We will then show that $n$ is good. Let $n=2^{b}\cdot a$ with odd $a.$ Let $m=c_1\cdot (n-1)\cdot 2^x$ for some $x>b.$ Then, rewrite $c_1\cdot 2^{m \cdot c_2}+m$ as such: \[c_1\cdot 2^{m \cdot c_2}+m=c_1\cdot 2^{c_1(n-1)2^x c_2}+c_1(n-1)2^x.\]Let $c_1c_2(n-1)=c_3$ for simplicity and using the above formula, observe that \[c_1\cdot 2^{m \cdot c_2}+m\equiv c_12^x\big(2^{c_32^x-x}-1\big)\bmod{n}.\]Recall that $n=2^b\cdot a$ and that $x>b.$ Hence, it is enough for $a$ to divide $2^{c_32^x-x}-1$ for infinitely many $x>b$ for $n$ to be good. But for $a$ to divide $2^{c_32^x-x}-1,$ since $a$ is odd, it is enough for $\varphi(a)$ to divide $c_32^x-x$ (for infinitely many $x>b$). Let $\varphi(a)-1=c_4$ and $x=c_4\cdot y.$ It then finally follows that $\varphi(a)$ must divide $c_3\cdot 2^{y\cdot c_4}+y$ for infinitely many $y>b/c_4.$ However, $\varphi(a)<a\leq a\cdot 2^b=n,$ so $\varphi(a)$ is good so, indeed, our condition is satisfied, so $n$ is also good! This finishes the proof and by letting $c_1=c_2=1$ we get our problem. As a remark, $2$ is completely pointless, since the algorithm works exactly the same for any $c$ (of course, with the adequate changes, such as considering $n=c^b\cdot a$ etc.)

I realized that I had written this solution up, why not post it; solution from a long time ago.

@3below, noted and fixed (the fix is quite quick, I do not know whether if I solved it in this way originally and was too relaxed in writing it up)

We more strongly show for any such $n$, there are arbitrarily large such $m$ satisfying the divisibility condition, using strong induction on $n$. Base case $n=1$ is direct. Assume assertion true for all $n \le k-1$ (where $k \ge 2$). Fix a large constant $C$. By induction hypothesis, pick a $m' > C$ so that $d = \gcd(n,\phi(n))$ divides $2^{m'} + m'$. Pick $m' = m + t \cdot \phi(n)$ (where value of $t \in \mathbb Z_{>0}$ will be decided later). As $m'$ is large, so $2^{m'} \equiv 2^m$ mod $n$. Thus, $$2^m + m \equiv (2^{m'} + m') + t \cdot \phi(n) = d \left (\frac{2^{m'} + m'}{d} + t \cdot \frac{\phi(n)}{d} \right) \pmod{n} $$Since $\gcd \left( \frac{n}{d} , \frac{\phi(n)}{d} \right) = 1$, so a suitable $t$ satisfies $$ \frac{n}{d} \mid \frac{2^{m'} + m'}{d} + t \cdot \frac{\phi(d)}{d} $$which completes the proof. $\blacksquare$

Call a number $n$ good if there exists a positive integer $m$ such that $n$ divides $2^{m}+m$. We wish to show that all positive integers are good. Note that $1$ is trivially good (take any $m$). Now we make use of the following claim. Claim: Every power of a prime is good. Proof: Let $n=p^a$, where $p$ is a prime and $a$ is a positive integer. If $p=2$, then picking $m=2^a$ suffices. Else, notice that $p$ is good as $2^{p-1}+p-1\equiv 0\pmod p$. Now assume that we've shown that $p^b$ is good and $p^b\mid 2^{m}+m$ for some $m$. We'll also show that $p^{b+1}$ is good: Pick $M=m+p^b(p-1)k$. Then notice that \[2^{M}+M = 2^{m+p^b(p-1)k}+m+p^b(p-1)k\equiv 2^{m}+m+p^b(p-1)k\pmod{p^{b+1}}\]We know that $2^{m}+m$ is divisible by $p^{b}$, so $\frac{2^{m}+m+p^b(p-1)k}{p^b}=k(p-1)+C$ for some constant $C$ dependent on $m$. Letting $k\equiv C\pmod p$ completes the proof. Claim: Every integer is good. Proof: Let $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}}$, where $p_{1}<p_{2}<\ldots <p_{s}$ are primes. Following our first claim, assume that we've shown that $N_{t}=\prod\limits_{i=1}^{t}p_{i}^{\alpha_{i}}$ is good. We'll show that $N_{t+1}=N_{t}p_{t+1}^{\alpha_{t+1}}$ is good as well. Let $M_{t}$ be a positive integer such that $N_{t}\mid 2^{M_{t}}+M_{t}$ and let $c=\nu_{p_{t+1}}\left(2^{M_{t}}+M_{t}\right)$. Then notice that for all integers $r$: \[2^{M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})}+M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\equiv 2^{M_{t}}+M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\pmod{N_{t}p_{t+1}^{c+1}}\]Furthermore, $2^{M_{t}}+M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\equiv 2^{M_{t}}+M_{t}\equiv 0\pmod{N_{t}}$. We have that $\varphi(N_{t}p_{t+1}^{c+1})=p_{t+1}^{c}(p_{t+1}-1)\prod\limits_{i=1}^{t} p_{i}^{\alpha_{i}-1}(p_{i}-1)$ and as $p_{i}-1<p_{i}\leq p_{t+1}$ we get that $p_{t+1}^{c} \parallel \varphi(N_{t}p_{t+1}^{c+1})$. Obviously, $p_{t+1}\nmid N_{t}=\prod\limits_{i=1}^{t} p_{i}^{\alpha_{i}}$ which combined with the statement from the last sentence implies that the set$\{rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\}$ for $r=1,2,\ldots ,p$ runs through all residues modulo $p_{t+1}^{c+1}$ divisible by $p_{t+1}^{c}$. Therefore there exists some $1\leq r\leq p$ such that \[rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\equiv -2^{M_{t}}-M_{t}\pmod{p_{t+1}}\Longrightarrow p_{t+1}^{c+1}\mid 2^{M_{t}}+M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\]Now we have that: \[N_{t}\mid 2^{M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})}+M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\text{ and }p_{t+1}\mid 2^{M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})}+M_{t}+rN_{t}\varphi(N_{t}p_{t+1}^{c+1})\]Therefore we've found an integer $M_{t}'$ such that $N_{t}\mid 2^{M_{t}'}+M_{t}'$, but $\nu_{p_{t+1}}(2^{M_{t}'}+M_{t}')>c$ and we can repeat this process until we reach $\alpha_{t+1}$. Hence the proof is complete.

bora_olmez wrote: I realized that I had written this solution up, why not post it; solution from a long time ago.

Well you used Euler’s Theorem in the last line so you have to ensure $n$ is odd.

We'll proceed strong induction on $n$ to prove the following statement: There exists infinitely many positive integers $m$ such that $n \mid 2^m + m$. Base case is clear. By induction hypothesis, there exists a large integer $r$ such that $\gcd(\varphi(n), n) \mid 2^r + r$. Thus there exists infinitely many $m$ such that $m \equiv r (\varphi(n))$ and $m \equiv -2^r (n)$. Since $r$ is large enough, so $2^m \equiv 2^r (n)$. Hence $2^m + m \equiv 2^r - 2^r = 0 (n)$, so we're done. $\blacksquare$

We prove the stronger statement: For all positive integers $n$ and $N$, show that there exists a positive integer $m$ such that $n$ divides $2^{m} + m$ and $\nu_2(m) \ge N$. If $n$ is a power of $2$, choose $m = 2^N$ for any positive integer $N > n$, and we find $\nu_2(2^m + m) = N$ and $n \mid 2^N \mid 2^m + m$. Hence the $\nu_2$ of $m$ satisfying $n\mid 2^m+ m$ is unbounded for $m$ satisfying $n \mid 2^m + m$. Suppose the problem was not true. Let $n$ be the smallest number for which this was not true. Clearly $n$ isn't a power of $2$. Now let $p$ be the largest prime divisor of $n$, $\nu_p(n) = k$, and $x\cdot p^k = n$. Additionally let $v = \frac{x}{2^{\nu_2(x)}}$, or in other words the largest odd divisor of $x$. Let $\alpha = v \cdot \varphi (v) \cdot (p-1)$. Choose $m_1$ such that $\nu_2(m_1) > \nu_2(\alpha )$ and $x$ divides $2^{m_1} + m_1$. This is possible by the inductive hypothesis. Let\[m_2 = m_1 + t \cdot \alpha \]for some positive integer $t$. Since $p$ is the largest prime factor of $m_2$, $p$ cannot divide $v$ or $\phi(v)$, so it is relatively prime to $\alpha$. Hence $m_2$ can be any sufficiently large number that is $m_1 \pmod{\alpha}$. Since $\nu_2(m_1) > \nu_2(\alpha)$ and $\gcd(p, \alpha) = 1$, we can choose any $m_2$ such that $m_2\equiv m_1\pmod{\alpha}$, $m_2 \equiv -2^{m_1} \pmod{p^k}$ by CRT. Now we can add $m_2$ by any multiple of $\alpha \cdot p^k$. Since $\nu_2(m_1) > \nu_2(\alpha)$, $\nu_2(m_2) \ge \nu_2(\alpha)$. Hence if we add $m_2$ by some multiple of $\alpha \cdot p^k$ and yield a result of $m$, we have that $\nu_2(m) \ge \nu_2(\alpha) = \nu_2(\alpha \cdot p^k)$, we can yield a result where $\nu_2(m) = N$ for any $N \ge \nu_2(\alpha)$. Hence we have chosen a value of $m$ such that\[ m \equiv m_1 \pmod{\alpha}, m \equiv -2^{m_1} \pmod{p^k}, \nu_2(m) = N\]for any positive integer $N \ge \alpha $. Now we claim that $n$ divides $2^m + m$ for sufficiently large $N$. Notice that $2^m \equiv 2^{m_1} \pmod p$ because $p-1 \mid \alpha \mid m - m_1$. Hence $2^m + m \equiv 2^{m_1} + m \equiv 0 \pmod{p^k}$, so $p^k$ divides $2^m + m$. Now we prove that $v$ divides $2^m + m$. Notice that since $v\mid \alpha$, $m \equiv m_1 \pmod v$, and since $2^{\phi(v)} \equiv 1\pmod v$ (because $v$ is odd), $2^m \equiv 2^{m_1} \pmod v$. Hence $0 \equiv 2^{m_1} + m_1 \equiv 2^m + m \pmod v$, so $v$ also divides $2^m + m$. Now we have $\frac{n}{p^k v }$ is some power of $2$. However, we can choose $m$ such that $N = \nu_2(m)$ is larger than $\nu_2 \left( \frac{n}{p^k v} \right)$. Hence $\frac{n}{p^k v}, v, p^k$ are pairwise coprime and all divide $2^m + m$, so $n$ divides $2^m + m$. We can choose $\nu_2(m)$ to be any sufficiently large positive integer, so the induction is complete. Hence any positive integer satisfies the stronger statement.

When I look at this problem, all I can think of is USA TST 2007/4.

Very similar to the USA TST 2007 indeed. Nice solution above

MarkBcc168 wrote: Fairly easy if you know generalized CRT. Lemma (Generalized CRT, 2 moduli): Let $a,b,m,n$ be positive integers. Then there exists integer $x$ such that \begin{align*} x &\equiv a\pmod m \\ x &\equiv b\pmod n \end{align*}if and only if $\gcd(m,n)\mid a-b$. With this lemma in hand we induct on $n$ with the trivial base case $n=1$. Let $m_0$ be a positive integer to be picked later. We want to pick $m$ such that \begin{align*} m &\equiv m_0\pmod{\varphi(n)} \\ m &\equiv -2^{m_0}\pmod n. \end{align*}Clearly, we will be done if $m$ exists. It exists if and only if $\gcd(n,\varphi(n))\mid 2^{m_0}+m_0$. Apply induction hypothesis and we are done. I think this does not work directly is $n$ is even, as Euler's theorem with $\varphi(n)$ cannot be applied directly. (Similarly for #47 by Sprites and #54 by thdnder.) A correct version seems to be the (edited) post #50 by bora_olmez.

cool problem but imo okish for n7