A little bit complicated for P1, im probably missing an easier solution.. FTSOC, suppose that the set of prime divisors of $S'$ is finite. Denote by $P$ the set of prime divisors of the elements of $S'.$ Let $p\in P.$ If there exist infinitely many elements in $S$ which are not divisible by $p,$ then remove all the elements in $S$ that are divisible by $p,$ and remove all the elements in $S$ which are not divisible by $p$ otherwise. So we can suppose WLOG that there is a partition of $P=A\cup B,$ for which any $p\in A$ we have that $p\mid x$ for any $x\in S$ and any $p\in B$ is relatively prime with any $x\in S.$ Let $B=\{ p_1, p_2, \cdots p_k \}$ and $z=p_1p_2\cdots p_k \phi(p_1p_2\cdots p_k).$ By PHP there exists an infinite subset $T$ of $S$ for which any $x,y\in T$ are congruent modulo $z.$ Let $x,y \in T,$ then $x^y+y^x \equiv 2a^b \pmod{p_1\cdots p_k}$ for some $a$ and $b,$ thus the only prime divisors of the elements of $T$ are either those from set $A$ or $2.$ There is an infinite $T'$ of $T$ for which any two elements of $T'$ are congurent modulo $4.$ Thus suppose that $2\in A$ or $x^y+y^x$ is not divisible with $4$ for any $x,y\in T'.$ Now fix an $y\in T'$ and pick an $x\in T'$ big enough such that $x/v_q(x) >y$ for any $q\in A,$ then $x^y+y^x$ clearly has a prime divisor different from those from $A$ or $2.$ Contradiction.

Here is another solution: Assume the contrary, and let $p_1,...,p_k$ be the set of the prime divisors of $S'$. Let $a_1,...,a_k$ be arbitrary natural numbers and let $N=(p_1)^{a_1}...(p_k)^{a_k}(p_1-1)...(p_k-1)$. By Pigeonhole Principle, there exists an infinite subset $T$ of $S$ such that for all $x\in T$ we have: $x \equiv a \pmod N$ for some $0 \le a < N$. Then, we have: $(p_1)^{b_1}...(p_k)^{b_k}=(Nr+a)^{Ns+a}+(Ns+a)^{Nr+a} \equiv 2a^a \pmod (p_1)^{a_1}...(p_k)^{a_k}$ where $x=Nr+a , y=Ns+a$ so we conclude that $a$ is divisible by some $p_i$ , assume that it is divisible by $p_1,...,p_m$ and not divisible by $p_{m+1},...,p_k$ , now fix $s$ and let $r$ be large, then for all $ 1 \le t \le m$ we have that: $ v_{p_t}((Ns+a)^{Nr+a})\ge (Nr+a) > (Ns+a)\log_{2}{Nr+a} \ge (Ns+a). v_{p_t}(Nr+a) = v_{p_t}((Nr+a)^{Ns+a}) $ because the function $ f(x) = x/ log_{2}{x} $ is increasing for large $x$ and this means that: $ b_t=v_{p_t}((Nr+a)^{Ns+a}) $ thus $ (Ns+a)^{Nr+a}+(Nr+a)^{Ns+a} = (p_1)^{b_1}...(p_k)^{b_k} \mid (Nr+a)^{Ns+a} $. Pay attention that the mentioned divisibility relation is true if we are sure that $ b_{m+1}=b_{m+2}=...=b_k=0 $ , but this always happens unless $p_z=2$ for some $m+1 \le z \le k$ , the reason is because if $ p_z \mid (Nr+a)^{Ns+a} + (Ns+a)^{Nr+a} $ then $ p_z \mid 2a^a $ so $ p_z=2 $ but then by assuming $ a_z=2 $ instead of letting it be an arbitrary natural number, we find that $ b_z=1 $ otherwise taking the relation modulo $4$ we reach a contradiction. In the case of $b_z=1$ pay attention that in the relation $ (p_1)^{b_1}...(p_m)^{b_m} \mid (Nr+a)^{Ns+a} $ if we have $ (p_1)^{b_1}...(p_m)^{b_m} \le (Nr+a)^{Ns+a} . 1/2 $ then using inequalities, we reach a contradiction but if $ (p_1)^{b_1}...(p_m)^{b_m}=(Nr+a)^{Ns+a} $ putting this in our original relation yields that $ (Nr+a)^{Ns+a}=(Ns+a)^{Nr+a} $ and this is obviously not true.

rmtf1111 wrote: A little bit complicated for P1, im probably missing an easier solution.. FTSOC, suppose that the set of prime divisors of $S'$ is finite. Denote by $P$ the set of prime divisors of the elements of $S'.$ Let $p\in P.$ If there exist infinitely many elements in $S$ which are not divisible by $p,$ then remove all the elements in $S$ that are divisible by $p,$ and remove all the elements in $S$ which are not divisible by $p$ otherwise. So we can suppose WLOG that there is a partition of $P=A\cup B,$ for which any $p\in A$ we have that $p\mid x$ for any $x\in S$ and any $p\in B$ is relatively prime with any $x\in S.$ Let $B=\{ p_1, p_2, \cdots p_k \}$ and $z=p_1p_2\cdots p_k \phi(p_1p_2\cdots p_k).$ By PHP there exists an infinite subset $T$ of $S$ for which any $x,y\in T$ are congruent modulo $z.$ Let $x,y \in T,$ then $x^y+y^x \equiv 2a^b \pmod{p_1\cdots p_k}$ for some $a$ and $b,$ thus the only prime divisors of the elements of $T$ are either those from set $A$ or $2.$ There is an infinite $T'$ of $T$ for which any two elements of $T'$ are congurent modulo $4.$ Thus suppose that $2\in A$ or $x^y+y^x$ is not divisible with $4$ for any $x,y\in T'.$ Now fix an $y\in T'$ and pick an $x\in T'$ big enough such that $x/v_q(x) >y$ for any $q\in A,$ then $x^y+y^x$ clearly has a prime divisor different from those from $A$ or $2.$ Contradiction. I have two questions for you 1. what does "then remove all the elements in $S$ that are divisible by $p,$ and remove all the elements in $S$ which are not divisible by $p$ otherwise" mean? 2. $p\mid x$ for any $x\in S$, "any" or "some"?

Here's my solution. Suppose that set of primes $P = \left\{ p\;\vert\; \exists_{x \in \mathbb{S'}} , p \;\vert \;x \right\}$ is an finite set. Let $P = \left\{p_1 , p_2 , \cdots\ , p_k\right\}$ (let's exclude 2) for each prime $p_i$ , There exists $0 \leq a_i \leq p_i - 1$ which there are infinite many elements in $S$ with $x \equiv a \;(mod\;p_i)$. if $\exists_i , \;a_i \neq 0$ Take 3 of them ($let \;x < y < z$) $\Rightarrow$ $a_i ^y +a_i ^x \equiv 0\;(mod\; p_i)$ $\Rightarrow$ $a_i ^{y-x} \equiv -1\;(mod\; p_i) $ $\Rightarrow$ $a_i ^{z-y} \equiv -1\;(mod\;p_i)$ $\Rightarrow$ $-1 \equiv a_i ^{z-x} \equiv a_i ^{z-y} \times a_i ^{y-x} \equiv (-1) \times (-1) \equiv 1$ , contradiction. So, we can know that $\forall_i , a_i = 0$. Let's Make $S_1 = \left\{x\;\vert\;x \in \mathbb{S} , p_1 p_2 \cdots p_k \vert x\right\}$ , which has infinite elements. fix n which is an element of $S_1$ , $n = p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a \; , \; gcd(a , p_1 p_2 \cdots p_k) = 1$ Take an element of $S_1$ (let $m$) , $m = p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \; , \; gcd(b , p_1 p_2 \cdots p_k) = 1$ if there exists infinite many $m$ s.t. $\forall_i , e_i p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \neq f_i p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a$ $\Rightarrow$ let $N = m^n + n^m $ if we pull out all of the $p_i ^{min\left\{ e_i p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b , f_i p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a\right\}}$'s , a number bigger than 1 is left . The only way is the number left is an exponential number with base 2. but, there are finite numbers that can satisfy ${n \over v_2 (n)} = {m \over v_2 (m)}$ because the case $v_2 (m) < v_2 (n)$ $\rightarrow$ $m<n$ which has finite m 's able, and the case $v_2 (m)>v_2 (n)$ leads to $xv_2 (y) = yv_2 (x) \rightarrow$ $2^{v_2 (y) - v_2 (x)} \vert v_2(y)$ which has finite m 's able. Also , we can know $e_i p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b = f_i p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a$ $\Leftrightarrow$ $ {p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \over f_i}\neq { p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a \over e_i}$ $\cdots (*)$ , which is each a function of $m$ and $n$. To prevent the contradiction above, every elements of $S_1$ should satisfy $(*)$ for some $i$. However, if the value ${p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \over f_i}$ is fixed , m gets the upper bound because ${p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \over f_i} = {m \over f_i} \geq {m \over log_{p_i}(m)}$. But, $S_1$ has infinite elements, and it makes contradiction.

Pooya2002 wrote: Here is another solution: Assume the contrary, and let $p_1,...,p_k$ be the set of the prime divisors of $S'$. Let $a_1,...,a_k$ be arbitrary natural numbers and let $N=(p_1)^{a_1}...(p_k)^{a_k}(p_1-1)...(p_k-1)$. By Pigeonhole Principle, there exists an infinite subset $T$ of $S$ such that for all $x\in T$ we have: $x \equiv a \pmod N$ for some $0 \le a < N$. Then, we have: $(p_1)^{b_1}...(p_k)^{b_k}=(Nr+a)^{Ns+a}+(Ns+a)^{Nr+a} \equiv 2a^a \pmod (p_1)^{a_1}...(p_k)^{a_k}$ where $x=Nr+a , y=Ns+a$ so we conclude that $a$ is divisible by some $p_i$ , assume that it is divisible by $p_1,...,p_m$ and not divisible by $p_{m+1},...,p_k$ , now fix $s$ and let $r$ be large, then for all $ 1 \le t \le m$ we have that: $ v_{p_t}((Ns+a)^{Nr+a})\ge (Nr+a) > (Ns+a)\log_{2}{Nr+a} \ge (Ns+a). v_{p_t}(Nr+a) = v_{p_t}((Nr+a)^{Ns+a}) $ because the function $ f(x) = x/ log_{2}{x} $ is increasing for large $x$ and this means that: $ b_t=v_{p_t}((Nr+a)^{Ns+a}) $ thus $ (Ns+a)^{Nr+a}+(Nr+a)^{Ns+a} = (p_1)^{b_1}...(p_k)^{b_k} \mid (Nr+a)^{Ns+a} $. Pay attention that the mentioned divisibility relation is true if we are sure that $ b_{m+1}=b_{m+2}=...=b_k=0 $ , but this always happens unless $p_z=2$ for some $m+1 \le z \le k$ , the reason is because if $ p_z \mid (Nr+a)^{Ns+a} + (Ns+a)^{Nr+a} $ then $ p_z \mid 2a^a $ so $ p_z=2 $ but then by assuming $ a_z=2 $ instead of letting it be an arbitrary natural number, we find that $ b_z=1 $ otherwise taking the relation modulo $4$ we reach a contradiction. In the case of $b_z=1$ pay attention that in the relation $ (p_1)^{b_1}...(p_m)^{b_m} \mid (Nr+a)^{Ns+a} $ if we have $ (p_1)^{b_1}...(p_m)^{b_m} \le (Nr+a)^{Ns+a} . 1/2 $ then using inequalities, we reach a contradiction but if $ (p_1)^{b_1}...(p_m)^{b_m}=(Nr+a)^{Ns+a} $ putting this in our original relation yields that $ (Nr+a)^{Ns+a}=(Ns+a)^{Nr+a} $ and this is obviously not true. I have a question for you why $(Nr+a)^{Ns+a}+(Ns+a)^{Nr+a} \equiv 2a^a \pmod{ p_1^{a_1}\cdots p_k^{a_k}}$ ?

Mathhunter1 wrote: Here's my solution. Suppose that set of primes $P = \left\{ p\;\vert\; \exists_{x \in \mathbb{S'}} , p \;\vert \;x \right\}$ is an finite set. Let $P = \left\{p_1 , p_2 , \cdots\ , p_k\right\}$ (let's exclude 2) for each prime $p_i$ , There exists $0 \leq a_i \leq p_i - 1$ which there are infinite many elements in $S$ with $x \equiv a \;(mod\;p_i)$. if $\exists_i , \;a_i \neq 0$ Take 3 of them ($let \;x < y < z$) $\Rightarrow$ $a_i ^y +a_i ^x \equiv 0\;(mod\; p_i)$ $\Rightarrow$ $a_i ^{y-x} \equiv -1\;(mod\; p_i) $ $\Rightarrow$ $a_i ^{z-y} \equiv -1\;(mod\;p_i)$ $\Rightarrow$ $-1 \equiv a_i ^{z-x} \equiv a_i ^{z-y} \times a_i ^{y-x} \equiv (-1) \times (-1) \equiv 1$ , contradiction. So, we can know that $\forall_i , a_i = 0$. Let's Make $S_1 = \left\{x\;\vert\;x \in \mathbb{S} , p_1 p_2 \cdots p_k \vert x\right\}$ , which has infinite elements. fix n which is an element of $S_1$ , $n = p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a \; , \; gcd(a , p_1 p_2 \cdots p_k) = 1$ Take an element of $S_1$ (let $m$) , $m = p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \; , \; gcd(b , p_1 p_2 \cdots p_k) = 1$ if there exists infinite many $m$ s.t. $\forall_i , e_i p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \neq f_i p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a$ $\Rightarrow$ let $N = m^n + n^m $ if we pull out all of the $p_i ^{min\left\{ e_i p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b , f_i p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a\right\}}$'s , a number bigger than 1 is left . The only way is the number left is an exponential number with base 2. but, there are finite numbers that can satisfy ${n \over v_2 (n)} = {m \over v_2 (m)}$ because the case $v_2 (m) < v_2 (n)$ $\rightarrow$ $m<n$ which has finite m 's able, and the case $v_2 (m)>v_2 (n)$ leads to $xv_2 (y) = yv_2 (x) \rightarrow$ $2^{v_2 (y) - v_2 (x)} \vert v_2(y)$ which has finite m 's able. Also , we can know $e_i p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b = f_i p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a$ $\Leftrightarrow$ $ {p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \over f_i}\neq { p_1 ^{e_1} p_2 ^{e_2} \cdots p_k ^{e_k} a \over e_i}$ $\cdots (*)$ , which is each a function of $m$ and $n$. To prevent the contradiction above, every elements of $S_1$ should satisfy $(*)$ for some $i$. However, if the value ${p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \over f_i}$ is fixed , m gets the upper bound because ${p_1 ^{f_1} p_2 ^{f_2} \cdots p_k ^{f_k} b \over f_i} = {m \over f_i} \geq {m \over log_{p_i}(m)}$. But, $S_1$ has infinite elements, and it makes contradiction. I have a question for you Take 3 of them ($let \;x < y < z$) $\Rightarrow$ $a_i ^y +a_i ^x \equiv 0\;(mod\; p_i)$ why $a_i ^y +a_i ^x \equiv 0\;(mod\; p_i)$?

Basically same as all above. Hope this is readable. "Note really needed step" Assume such $S$ exists. Take $S$ with minimal number of prime dividing elements of $S^\prime$. [Claim] For any $p>2$, only finitely many element of $S$ is not divisible by $p$.

Therefore, for some $M$, every element $x>M$ should be divided by any $p>2$. [Case1] There exists an even $a>M$. Fix $a$ and consider $a^y + y^a$ with sufficiently large $y$. Then, $v _2 (a^y+y^a)=v_2(y^a)$ and $v_p(a^y +y^a)=v_p(y^a)$. This is impossible since $p$s and $2$ are the only prime divisor that $a^y +y^a$ can have. [Case2] Every $x>M$ is odd. Then either $x \equiv 1$ or $\equiv 3 \pmod 4$ is infinite. For each case, do exactly same as Case1 and we get $v_2 (a^y + y^a) = 1$, $v_p (a^y+.y^a)=v_p(y^a)$. Therefore, $a^y +y^a \le 2y^a$ which is not true for large $y$. Therefore, prime divisor of $S^\prime$ is infinite. $\blacksquare$ Rmk) You may directly take some remainder $a$ of $4 \prod p(p-1)$ that infinitely arise in $S$. Again fix some $x \equiv a$ and take sufficiently large $y \equiv a$. For $p>2$, $v_p(x^y+y^x) = v_p(y^x)$. (It can also be zero.) When $a$ divides 2, $v_2(x^y+y^x)=v_2(y^x)$ again. If not $v_2(x^y+y^x)=1$ and again $x^y +y^x \le 2y^x$ which is impossible.

Suppose otherwise; let $P$ be the finite set of primes that divide some element of $S'$. Take $y,z \in S$ such that $y\equiv z \pmod {\prod_{p_i\in P} p_i(p_i-1)}$ and $z>y>2|P|$. Note that $x^y+y^x \equiv x^z+z^x \pmod p$ for all $x$ and $p\in P$. Then $x^z+z^x-x^y-y^x=x^y(x^{z-y}-1)+z^x-y^x$. Note $v_p(z^x-y^x)=v_p(z-y)+v_p(x)$, while $v_p(x^y(x^{z-y}-1))=v_p(x^y)+v_p(x^{p-1}-1)+v_p(z-y)$ (since $p-1|z-y$), clearly larger than the $v_p$ we obtained above. Hence $$\min(v_p(x^y+y^x), v_p(x^z+z^x)) \le v_p(x)+v_p(z-y). \ldots (\star)$$ Now since infinitely many elements in $S$, we consider some subset $T$ with at least $|P|+1$ elements, where any element is larger than $2|P|$ and any two are congruent $\pmod {\prod_{p_i\in P} p_i(p_i-1)}$. Claim: there must be some $t\in T$, where $v_p(x^t+t^x)\le v_p(x)+\max_{t_i,t_j\in T} v_p(t_i-t_j)$, by the first part. This follows from $(\star)$ that for each $p\in P$ ,there must be at most one $r\in T$ where $v_p(x^r+r^x)\ge v_p(x)+\max_{t_i,t_j\in T} v_p(t_i-t_j).$ Hence our claim is proven since there are $|P|+1$ elements in $T$. Now $x^t+t^x\le \prod p^{v_p(x)+\max_{t_i-t_j\in T} v_p(t_i-t_j)}\le x^{|P|}k$, where $k$ is a constant after we have identified $T$. Hence choose $x$ large enough where $k<x^{|P|}$, then $x^r+r^x\le x^{|P|}k<x^{2|P|}<x^r$, since we chose $r>2|P|$, contradiction.

Similar idea to mofumofu. Let $\mathbb{P}(S')$ denote the set of prime divisors of $S'$. Suppose for the sake of contradiction that $\mathbb{P}(S')$ is finite. Observation: For any positive integer $N$, there exists $0 \leq r < N$ for which $S$ contains infinitely many numbers that are $r \pmod N$. Pick \[N = \prod_{p \in \mathbb{P}(S')}{p^2(p-1)}.\]Let $T$ be the infinite subset of $S$ containing all elements $r \pmod N$. Let $x, y \in T$ and $p \in \mathbb{P}(S')$. If $p \nmid r$, by Fermat's Little Theorem \[x^y \equiv y^x \equiv r^r \pmod p\]if $p > 2$ and $x^y + y^x \equiv 2 \pmod 4$ if $p = 2$. Hence, $v_p(x^y + y^x) = v_p(y^x)$ for $p \geq 3$ and $v_p(x^y + y^x) = v_p(y^x) + 1$ for $p = 2$. If $p \mid r$, for large enough $y$ we find $v_p(x^y) > v_p(y^x)$. Hence $v_p(x^y + y^x) = v_p(y^x)$. Combining these observations, we have $v_p(x^y + y^x) = v_p(y^x)$ for all $p \geq 3$ and $v_p(y^x) \leq v_p(x^y + y^x) \leq v_p(y^x) + 1$ for $p = 2$. Hence, $x^y + y^x \in \{y^x, 2y^x\}$, which fails for large enough $y$.