Number theoryDifficulty 7.0National olympiadProve itIran
Let S be an infinite subset of natural numbers. Define the set S′ as follows: S′={xy+yx∣x,y∈S,x=y}.
Prove that there are infinitely many prime numbers p such that p divides at least one element in S′.
Solution
Let P be the set of all prime divisors of members of S′. Suppose, to the contrary, that P is finite and P={p1,p2,…,pn}. Define N=4i=1∏npi(pi−1). S is infinite, hence there exists an infinite subset S1 of S such that every two members of S1 are congruent to each other modulo N. Let x,y>1 be members of S1 such that y is large enough to satisfy log2yy>x. It's easy to see that x<log2yy≤logxyy⟹y>xlogxy⟹xy>yx Since xy+yx∈S′, it can be written in the form xy+yx=q1α1q2α2…qkαk where q1,q2,…,qk∈P and α1,α2,…,αk∈Z+. For every 1≤i≤k we have qi∣N,x≡y(modN)⟹x≡y(modqi)⟹xy≡yy(modqi)(1) qi−1∣N,x≡y(modN)⟹x≡y(modqi−1)⟹yx≡yx(modqi)(2) According to (1), (2) xy≡yx(modqi)xy+yx≡0(modqi)}⟹2xy≡0(modqi) So for every odd qi we have qi∣x. For qi=2 if at least one of x and y is even, then the other one is even too; And if they both are odd we have 2∣x−y⟹yy≡yx(mod4)y≡x(modN)4∣N⎭⎬⎫⟹xy≡yy≡yx(mod4)⟹xy+yx≡2xy≡2(mod4)⟹αi=1(3) Now let x=q1β1q2β2…qkβkx′,y=q1γ1q2γ2…qkγky′ so that βi,γi∈Z+∪{0},gcd(x′,q1,q2,…,qk)=gcd(y′,q1,q2,…,qk)=1 For every 1≤i≤k if qi=2, it was proven that βi,γi>0. Furthermore, if qi=2 and one of x,y is even, then βi,γi>0. So if these conditions hold, we have βiy≥y. From the definition of y we have βiy≥y>xlog2y≥xlogqiy≥xγi. Also if x,y are odd and qi=2, the inequality 0=βiy≥γix=0 still holds. Now we have q1α1q2α2…qkαk=xy+yx=x′y1≤i≤k∏qiyβi+y′x1≤i≤k∏qixγi=1≤i≤k∏qixγi(y′x+x′y1≤i≤k∏qiyβi−xγi) If qi=2 and x,y are odd, from (3) we have αi=1. Otherwise we have yβi−xγi>0⟹(y′x+x′y1≤i≤k∏qiyβi−xγi,qi)=(y′x,qi)=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 ⟹⟹⟹⟹y′x+x′y1≤i≤k∏qiyβi−xγi2y′x+x′y1≤i≤k∏qiyβi−xγi≤2y′x≤1⟹y′x=1⟹yx=1≤i≤k∏qixγixy+yx=q1α1q2α2…qkαk=yx(y′x+x′y1≤i≤k∏qiyβi−xγi)≤2yxxy≤yx Which contradicts the way y 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.