Menu Close

For-natural-numbers-x-and-y-let-x-y-denote-the-greatest-common-divisor-of-x-and-y-How-many-pairs-of-natural-numbers-x-and-y-with-x-y-satisfy-the-equation-xy-x-y-x-y-

Tinku Tara 0 Comments
Pin




Question Number 19786 by Tinkutara last updated on 15/Aug/17
For natural numbers x and y, let (x, y) denote the greatest common divisor of x and y. How many pairs of natural numbers x and y with x ≤ y satisfy the equation xy = x + y + (x, y)?
$$\mathrm{For}\:\mathrm{natural}\:\mathrm{numbers}\:{x}\:\mathrm{and}\:{y},\:\mathrm{let}\:\left({x},\:{y}\right) \\ $$$$\mathrm{denote}\:\mathrm{the}\:\mathrm{greatest}\:\mathrm{common}\:\mathrm{divisor}\:\mathrm{of} \\ $$$${x}\:\mathrm{and}\:{y}.\:\mathrm{How}\:\mathrm{many}\:\mathrm{pairs}\:\mathrm{of}\:\mathrm{natural} \\ $$$$\mathrm{numbers}\:{x}\:\mathrm{and}\:{y}\:\mathrm{with}\:{x}\:\leqslant\:{y}\:\mathrm{satisfy}\:\mathrm{the} \\ $$$$\mathrm{equation}\:{xy}\:=\:{x}\:+\:{y}\:+\:\left({x},\:{y}\right)? \\ $$
Answered by mrW1 last updated on 16/Aug/17
let x≤y ...(1) if x=1, y=y+2 ! ⇒x≥2 (x,y)≤x (x,y)≥1 xy=x+y+(x,y)≥x+y+1 (x−1)y≥x+1 y≥((x+1)/(x−1))=1+(2/(x−1)) ...(2) xy=x+y+(x,y)≤2x+y (x−1)y≤2x y≤((2x)/(x−1))=2+(2/(x−1)) ...(3) from (1) to (3), see diagram: 2≤x≤3 3≤y≤4 (x,y)=(2,3) ok (x,y)=(2,4) ok (x,y)=(3,3) ok
$$\mathrm{let}\:\mathrm{x}\leqslant\mathrm{y}\:\:\:…\left(\mathrm{1}\right) \\ $$$$\mathrm{if}\:\mathrm{x}=\mathrm{1},\:\mathrm{y}=\mathrm{y}+\mathrm{2}\:! \\ $$$$\Rightarrow\mathrm{x}\geqslant\mathrm{2} \\ $$$$ \\ $$$$\left(\mathrm{x},\mathrm{y}\right)\leqslant\mathrm{x} \\ $$$$\left(\mathrm{x},\mathrm{y}\right)\geqslant\mathrm{1} \\ $$$$\mathrm{xy}=\mathrm{x}+\mathrm{y}+\left(\mathrm{x},\mathrm{y}\right)\geqslant\mathrm{x}+\mathrm{y}+\mathrm{1} \\ $$$$\left(\mathrm{x}−\mathrm{1}\right)\mathrm{y}\geqslant\mathrm{x}+\mathrm{1} \\ $$$$\mathrm{y}\geqslant\frac{\mathrm{x}+\mathrm{1}}{\mathrm{x}−\mathrm{1}}=\mathrm{1}+\frac{\mathrm{2}}{\mathrm{x}−\mathrm{1}}\:\:\:…\left(\mathrm{2}\right) \\ $$$$ \\ $$$$\mathrm{xy}=\mathrm{x}+\mathrm{y}+\left(\mathrm{x},\mathrm{y}\right)\leqslant\mathrm{2x}+\mathrm{y} \\ $$$$\left(\mathrm{x}−\mathrm{1}\right)\mathrm{y}\leqslant\mathrm{2x} \\ $$$$\mathrm{y}\leqslant\frac{\mathrm{2x}}{\mathrm{x}−\mathrm{1}}=\mathrm{2}+\frac{\mathrm{2}}{\mathrm{x}−\mathrm{1}}\:\:\:…\left(\mathrm{3}\right) \\ $$$$ \\ $$$$\mathrm{from}\:\left(\mathrm{1}\right)\:\mathrm{to}\:\left(\mathrm{3}\right),\:\mathrm{see}\:\mathrm{diagram}: \\ $$$$\mathrm{2}\leqslant\mathrm{x}\leqslant\mathrm{3} \\ $$$$\mathrm{3}\leqslant\mathrm{y}\leqslant\mathrm{4} \\ $$$$ \\ $$$$\left(\mathrm{x},\mathrm{y}\right)=\left(\mathrm{2},\mathrm{3}\right)\:\mathrm{ok} \\ $$$$\left(\mathrm{x},\mathrm{y}\right)=\left(\mathrm{2},\mathrm{4}\right)\:\mathrm{ok} \\ $$$$\left(\mathrm{x},\mathrm{y}\right)=\left(\mathrm{3},\mathrm{3}\right)\:\mathrm{ok} \\ $$
Commented by mrW1 last updated on 16/Aug/17
y≥1+(2/(x−1)) ≥1+(2/(y−1)) (y−1)^2 ≥2 ⇒y≥1+(√2)≈2.41 y≤2+(2/(x−1)) 2≥(y−2)(x−1)≥(x−2)(x−1)=x^2 −3x+2 x^2 −3x+2≤2 x(x−3)≤0 ⇒x≤3 ⇒2≤x≤3
$$\mathrm{y}\geqslant\mathrm{1}+\frac{\mathrm{2}}{\mathrm{x}−\mathrm{1}}\:\geqslant\mathrm{1}+\frac{\mathrm{2}}{\mathrm{y}−\mathrm{1}} \\ $$$$\left(\mathrm{y}−\mathrm{1}\right)^{\mathrm{2}} \geqslant\mathrm{2} \\ $$$$\Rightarrow\mathrm{y}\geqslant\mathrm{1}+\sqrt{\mathrm{2}}\approx\mathrm{2}.\mathrm{41} \\ $$$$ \\ $$$$\mathrm{y}\leqslant\mathrm{2}+\frac{\mathrm{2}}{\mathrm{x}−\mathrm{1}} \\ $$$$\mathrm{2}\geqslant\left(\mathrm{y}−\mathrm{2}\right)\left(\mathrm{x}−\mathrm{1}\right)\geqslant\left(\mathrm{x}−\mathrm{2}\right)\left(\mathrm{x}−\mathrm{1}\right)=\mathrm{x}^{\mathrm{2}} −\mathrm{3x}+\mathrm{2} \\ $$$$\mathrm{x}^{\mathrm{2}} −\mathrm{3x}+\mathrm{2}\leqslant\mathrm{2} \\ $$$$\mathrm{x}\left(\mathrm{x}−\mathrm{3}\right)\leqslant\mathrm{0} \\ $$$$\Rightarrow\mathrm{x}\leqslant\mathrm{3} \\ $$$$ \\ $$$$\Rightarrow\mathrm{2}\leqslant\mathrm{x}\leqslant\mathrm{3} \\ $$
Commented by mrW1 last updated on 16/Aug/17
Commented by Tinkutara last updated on 16/Aug/17
Can′t it be solved without diagram? We have to prove x ≤ 3. Can we, in this question, do this?
$$\mathrm{Can}'\mathrm{t}\:\mathrm{it}\:\mathrm{be}\:\mathrm{solved}\:\mathrm{without}\:\mathrm{diagram}? \\ $$$$\mathrm{We}\:\mathrm{have}\:\mathrm{to}\:\mathrm{prove}\:{x}\:\leqslant\:\mathrm{3}.\:\mathrm{Can}\:\mathrm{we},\:\mathrm{in} \\ $$$$\mathrm{this}\:\mathrm{question},\:\mathrm{do}\:\mathrm{this}? \\ $$
Commented by Tinkutara last updated on 16/Aug/17
Thank you very much Sir!
$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{very}\:\mathrm{much}\:\mathrm{Sir}! \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *