Maths Olympiad Prep

Library / /166 of 397

Number theory Difficulty 5.6 AIME, harder Prove it Taiwan

Let x,yx, y be positive integers with x>yx > y and (xy)xy=xyyx(x-y)^{xy} = x^y \cdot y^x, find the pairs (x,y)(x, y).

Solution

Let x=dpx = dp, y=dqy = dq, where d=(x,y)d = (x, y) is the greatest common divisor of x,yx, y, p,qNp, q \in \mathbb{N}, (p,q)=1(p, q) = 1, p>qp > q, then
(d(pq))d2pq=(dp)dq(dq)dp(d(pq))dpq=(dp)q(dq)pddpq(pq)dpq=dp+qpqqp.(d(p-q))^{d^2pq} = (dp)^{dq}(dq)^{dp} \Leftrightarrow (d(p-q))^{dpq} = (dp)^q(dq)^p \Leftrightarrow d^{dpq}(p-q)^{dpq} = d^{p+q}p^q q^p.

We want to prove: p+q<dpqp+q < dpq,
Suppose p+qdpqp+q \ge dpq, then (pq)dpq=dp+qdpqpqqpp(pq)dpq(p-q)^{dpq} = d^{p+q-dpq}p^q q^p \Rightarrow p \mid (p-q)^{dpq} and q(pq)dpqq \mid (p-q)^{dpq}, but (pq,p)=(pq,q)=(p,q)=1p=1,q=1(p-q, p) = (p-q, q) = (p, q) = 1 \Rightarrow p=1, q=1 (contradiction) therefore p+q<dpqp+q < dpq, so ddpqpq(pq)dpq=pqqp(pq)pqqpd^{dpq-p-q}(p-q)^{dpq} = p^q q^p \Rightarrow (p-q) \mid p^q q^p, and also (pq,p)=(pq,q)=(p,q)=1pq=1(p-q, p) = (p-q, q) = (p, q) = 1 \Rightarrow p-q=1, that is p=q+1p=q+1, therefore
ddpqpq=pqqq+1,(1) d^{dpq-p-q} = p^q q^{q+1}, \qquad (1)
so p,qp, q are divisors of dd. Since (p,q)=1(p, q)=1, dd can be written as d=s×td=s \times t, where the prime factors of tt are only pp, the prime factors of ss are only qq, and (s,t)=1(s, t)=1. From equation (1) we get:
tdpqpq=pq=(q+1)q.(2) t^{dpq-p-q} = p^q = (q+1)^q. \qquad (2)
Since dpqpqdpq-p-q is coprime to qq, from (2) we know tt must be a pp-th power of some natural number, let t=t1qt = t_1^q. Then
t1dpqpq=q+1t1dq(q+1)(2q+1)=q+1, since q+1>1, hence t1>1. If q3, thent_1^{dpq-p-q} = q+1 \Leftrightarrow t_1^{dq(q+1)-(2q+1)} = q+1, \text{ since } q+1 > 1, \text{ hence } t_1 > 1. \text{ If } q \ge 3, \text{ then}
dq(q+1)(2q+1)3(q+1)(2q+1)=q+2t1dpqpq2q+2>q+1 (contradiction)dq(q+1)-(2q+1) \ge 3(q+1)-(2q+1) = q+2 \Rightarrow t_1^{dpq-p-q} \ge 2^{q+2} > q+1 \text{ (contradiction)}
If q=2q=2, then t16d5=3t1=3t_1^{6d-5}=3 \Rightarrow t_1=3, d=1d=1 and x=d(q+1)=3x=d(q+1)=3, y=dq=2y=dq=2 (contradiction). Therefore
q=1q=1, then t12d3=2t1=2t_1^{2d-3}=2 \Rightarrow t_1=2, d=2x=4,y=2d=2 \Rightarrow x=4, y=2.

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 translated into English from the original; metadata (topic, difficulty) added by this project.