Olympiad Maths Prep

Library / /16 of 22

Number theory Difficulty 5.8 AIME, harder Prove it Ukraine

Natural numbers a,b,c,da, b, c, d satisfy
0<adbc<min{c,d}. 0 < |ad - bc| < \min\{c, d\}.
Prove that for any coprime natural numbers x,y>1x, y > 1 the number xa+ybx^a + y^b is not divisible by xc+ydx^c + y^d.

Solution

We will prove this by contradiction. Denote the sum xc+ydx^c + y^d by ss. Then, obviously, xc=yd(mods)x^c = -y^d \pmod{s} and also if (xa+yb):s(x^a + y^b):s, then xa=yb(mods)x^a = -y^b \pmod{s}. This implies that xad=(1)dybd(mods)x^{ad} = (-1)^d y^{bd} \pmod{s} and xbc=(1)bybd(mods)x^{bc} = (-1)^b y^{bd} \pmod{s}, hence (1)dxad=ybd=(1)bxbc(mods)xad=(1)bdxbc(mods)(-1)^d x^{ad} = y^{bd} = (-1)^b x^{bc} \pmod{s} \Rightarrow x^{ad} = (-1)^{b-d} x^{bc} \pmod{s}. It is clear that xx and ss are coprime, so we can divide the last congruence by xx raised to the power min{ad,bc}\min\{ad, bc\}, and obtain xmax{ad,bc}=(1)bd(mods)x^{\max\{ad, bc\}} = (-1)^{b-d} \pmod{s}. Similarly, we get ymax{ad,bc}=(1)ac(mods)y^{\max\{ad, bc\}} = (-1)^{a-c} \pmod{s}. Therefore, ymax{adbc}xmax{adbc}:sy^{\max\{ad-bc\}} - x^{\max\{ad-bc\}}:s or ymax{adbc}+xmax{adbc}:sy^{\max\{ad-bc\}} + x^{\max\{ad-bc\}}:s. By the statement of the problem, we have 0<adbc<min{c,d}0 < |ad-bc| < \min\{c, d\}. But then
ymax{adbc}xmax{adbc}<ymax{adbc}+xmax{adbc}<yd+xc=s. |y^{\max\{ad-bc\}} - x^{\max\{ad-bc\}}| < y^{\max\{ad-bc\}} + x^{\max\{ad-bc\}} < y^d + x^c = s.
So, the expression ymax{adbc}±xmax{adbc}|y^{\max\{ad-bc\}} \pm x^{\max\{ad-bc\}}| can be divisible by ss only if it is equal to zero. But this contradicts the fact that xx and yy are coprime, and we are done.

Looking for a route rather than 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.