Maths Olympiad Prep

Library / /70 of 92

Number theory Difficulty 7.0 National olympiad Prove it Iran

Let SS be an infinite subset of natural numbers. Define the set SS' as follows:
S={xy+yxx,yS,xy}. S' = \{x^y + y^x \mid x, y \in S, x \ne y\}.

Prove that there are infinitely many prime numbers pp such that pp divides at least one element in SS'.

Solution

Let PP be the set of all prime divisors of members of SS'. Suppose, to the contrary, that PP is finite and P={p1,p2,,pn}P = \{p_1, p_2, \dots, p_n\}. Define
N=4i=1npi(pi1). N = 4 \prod_{i=1}^{n} p_i(p_i - 1).
SS is infinite, hence there exists an infinite subset S1S_1 of SS such that every two members of S1S_1 are congruent to each other modulo NN. Let x,y>1x, y > 1 be members of S1S_1 such that yy is large enough to satisfy ylog2y>x\frac{y}{\log_2 y} > x. It's easy to see that
x<ylog2yylogxy    y>xlogxy    xy>yx x < \frac{y}{\log_2 y} \le \frac{y}{\log_x y} \implies y > x \log_x y \implies x^y > y^x
Since xy+yxSx^y + y^x \in S', it can be written in the form xy+yx=q1α1q2α2qkαkx^y + y^x = q_1^{\alpha_1} q_2^{\alpha_2} \dots q_k^{\alpha_k} where q1,q2,,qkPq_1, q_2, \dots, q_k \in \mathbb{P} and α1,α2,,αkZ+\alpha_1, \alpha_2, \dots, \alpha_k \in \mathbb{Z}^+. For every 1ik1 \le i \le k we have
qiN,xy(modN)    xy(modqi)    xyyy(modqi)(1) \begin{aligned} q_i \mid N, x \equiv y \pmod{N} &\implies x \equiv y \pmod{q_i} \\ &\implies x^y \equiv y^y \pmod{q_i} \end{aligned} \qquad (1)
qi1N,xy(modN)    xy(modqi1)    yxyx(modqi)(2) \begin{aligned} q_i - 1 \mid N, x \equiv y \pmod{N} &\implies x \equiv y \pmod{q_i - 1} \\ &\implies y^x \equiv y^{x} \pmod{q_i} \end{aligned} \qquad (2)
According to (1), (2)
xyyx(modqi)xy+yx0(modqi)}    2xy0(modqi) \left. \begin{array}{l} x^y \equiv y^x \pmod{q_i} \\ x^y + y^x \equiv 0 \pmod{q_i} \end{array} \right\} \implies 2x^y \equiv 0 \pmod{q_i}
So for every odd qiq_i we have qixq_i \mid x. For qi=2q_i = 2 if at least one of xx and yy is even, then the other one is even too; And if they both are odd we have
2xy    yyyx(mod4)yx(modN)4N}    xyyyyx(mod4)    xy+yx2xy2(mod4)    αi=1(3) \left. \begin{array}{l} 2 \mid x-y \implies y^y \equiv y^x \pmod{4} \\ y \equiv x \pmod{N} \\ 4 \mid N \end{array} \right\} \implies x^y \equiv y^y \equiv y^x \pmod{4} \\ \implies x^y + y^x \equiv 2x^y \equiv 2 \pmod{4} \implies \alpha_i = 1 \qquad (3)
Now let
x=q1β1q2β2qkβkx,y=q1γ1q2γ2qkγky x = q_1^{\beta_1} q_2^{\beta_2} \dots q_k^{\beta_k} x', \quad y = q_1^{\gamma_1} q_2^{\gamma_2} \dots q_k^{\gamma_k} y'
so that
βi,γiZ+{0},gcd(x,q1,q2,,qk)=gcd(y,q1,q2,,qk)=1 \beta_i, \gamma_i \in \mathbb{Z}^+ \cup \{0\}, \text{gcd}(x', q_1, q_2, \dots, q_k) = \text{gcd}(y', q_1, q_2, \dots, q_k) = 1
For every 1ik1 \le i \le k if qi2q_i \ne 2, it was proven that βi,γi>0\beta_i, \gamma_i > 0. Furthermore, if qi=2q_i = 2 and one of x,yx, y is even, then βi,γi>0\beta_i, \gamma_i > 0. So if these conditions hold, we have βiyy\beta_i y \ge y. From the definition of yy we have
βiyy>xlog2yxlogqiyxγi. \beta_i y \ge y > x \log_2 y \ge x \log_{q_i} y \ge x \gamma_i.
Also if x,yx, y are odd and qi=2q_i = 2, the inequality 0=βiyγix=00 = \beta_i y \ge \gamma_i x = 0 still holds. Now we have
q1α1q2α2qkαk=xy+yx=xy1ikqiyβi+yx1ikqixγi=1ikqixγi(yx+xy1ikqiyβixγi) \begin{aligned} q_1^{\alpha_1} q_2^{\alpha_2} \dots q_k^{\alpha_k} &= x^y + y^x \\ &= x'^y \prod_{1 \le i \le k} q_i^{y\beta_i} + y'^x \prod_{1 \le i \le k} q_i^{x\gamma_i} \\ &= \prod_{1 \le i \le k} q_i^{x\gamma_i} \left( y'^x + x'^y \prod_{1 \le i \le k} q_i^{y\beta_i - x\gamma_i} \right) \end{aligned}
If qi=2q_i = 2 and x,yx, y are odd, from (3) we have αi=1\alpha_i = 1. Otherwise we have
yβixγi>0    (yx+xy1ikqiyβixγi,qi)=(yx,qi)=1 y\beta_i - x\gamma_i > 0 \implies \left( y'^x + x'^y \prod_{1\le i\le k} q_i^{y\beta_i - x\gamma_i}, q_i \right) = (y'^x, q_i) = 1
But we also have
y'^x + x'^y \prod_{1\le i\le k} q_i^{y\beta_i - x\gamma_i} \quad \left| \quad x^y + y^x = q_1^{\alpha_1} q_2^{\alpha_2} \dots q_k^{\alpha_k}
So
yx+xy1ikqiyβixγi2    yx+xy1ikqiyβixγi2    yx1    yx=1    yx=1ikqixγi    xy+yx=q1α1q2α2qkαk=yx(yx+xy1ikqiyβixγi)2yx    xyyx \begin{align*} & y'^x + x'^y \prod_{1\le i\le k} q_i^{y\beta_i - x\gamma_i} \quad \Big| \quad 2 \\ \implies \quad & y'^x + x'^y \prod_{1\le i\le k} q_i^{y\beta_i - x\gamma_i} \le 2 \\ \implies \quad & y'^x \le 1 \implies y'^x = 1 \implies y^x = \prod_{1\le i\le k} q_i^{x\gamma_i} \\ \implies \quad & x^y + y^x = q_1^{\alpha_1} q_2^{\alpha_2} \dots q_k^{\alpha_k} = y^x \left( y'^x + x'^y \prod_{1\le i\le k} q_i^{y\beta_i - x\gamma_i} \right) \le 2y^x \\ \implies \quad & x^y \le y^x \end{align*}
Which contradicts the way yy was chosen, and completes our proof. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.