Olympiad Maths Prep

Library / /1 of 7

Number theory Difficulty 5.7 AIME, harder Prove it China

Let pp be an odd prime number, and aa, bb, mm, rr be positive integers, such that pabp \nmid ab and ab>m2ab > m^2. Prove that there exists at most one pair of positive integers (x,y)(x, y) satisfying the following conditions: xx and yy are coprime, and ax2+by2=mprax^2 + by^2 = mp^r.

Solution

Proof: By contradiction, suppose there exist two different pairs of positive integer solutions (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2). Since x1x_1 and y1y_1 are coprime, it follows that px1y1p \nmid x_1y_1. Similarly, px2y2p \nmid x_2y_2. Given
ax12by12(modpr),ax22by22(modpr), ax_1^2 \equiv -by_1^2 \pmod{p^r}, \quad ax_2^2 \equiv -by_2^2 \pmod{p^r},
it is known that abx12y22abx22y12(modpr)abx_1^2y_2^2 \equiv abx_2^2y_1^2 \pmod{p^r}. Since pabp \nmid ab, we have pr(x12y22x22y12)p^r \mid (x_1^2y_2^2 - x_2^2y_1^2).
Note that x1y2x2y1x_1y_2 - x_2y_1 and x1y2+x2y1x_1y_2 + x_2y_1 cannot both be divisible by pp, otherwise p2x1y2p \mid 2x_1y_2, which contradicts with pp being an odd prime and px1y1x2y2p \nmid x_1y_1x_2y_2. Hence, prx1y2x2y1p^r \mid x_1y_2 - x_2y_1, or prx1y2+x2y1p^r \mid x_1y_2 + x_2y_1.
If x1y2x2y1=0x_1y_2 - x_2y_1 = 0, then x1x2=y1y2\frac{x_1}{x_2} = \frac{y_1}{y_2}, combined with ax12+by12=ax22+by22ax_1^2 + by_1^2 = ax_2^2 + by_2^2, implies x1=x2x_1 = x_2, y1=y2y_1 = y_2, contradicting with (x1,y1)(x2,y2)(x_1, y_1) \neq (x_2, y_2). Therefore, x1y2x2y10x_1y_2 - x_2y_1 \neq 0.
If prx1y2+x2y1p^r \mid x_1y_2 + x_2y_1, then x1y2+x2y1prx_1y_2 + x_2y_1 \ge p^r.
If prx1y2x2y1p^r \mid x_1y_2 - x_2y_1, then x1y2+x2y1x1y2x2y1prx_1y_2 + x_2y_1 \ge |x_1y_2 - x_2y_1| \ge p^r. Thus, in all cases,
x1y2+x2y1pr.() x_1y_2 + x_2y_1 \ge p^r. \quad (*)
Using the condition ab>m2ab > m^2 and ()(*), we get
m2p2r=(ax12+by12)(ax22+by22)=(ax1x2by1y2)2+ab(x1y2+x2y1)2ab(x1y2+x2y1)2>m2p2r, \begin{aligned} m^2p^{2r} &= (ax_1^2 + by_1^2)(ax_2^2 + by_2^2) \\ &= (ax_1x_2 - by_1y_2)^2 + ab(x_1y_2 + x_2y_1)^2 \\ &\ge ab(x_1y_2 + x_2y_1)^2 \\ &> m^2p^{2r}, \end{aligned}
a contradiction. Therefore, the assumption by contradiction is false, and the original statement holds. \Box

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.