Maths Olympiad Prep

Library / Chinese Girls' Mathematical Olympiad /1 of 7

Chinese Girls' Mathematical Olympiad

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 p∤abp \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 p∤x1y1p \nmid x_1y_1. Similarly, p∤x2y2p \nmid x_2y_2. Given
ax12≡−by12(modpr),ax22≡−by22(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 abx12y22≡abx22y12(modpr)abx_1^2y_2^2 \equiv abx_2^2y_1^2 \pmod{p^r}. Since p∤abp \nmid ab, we have pr∣(x12y22−x22y12)p^r \mid (x_1^2y_2^2 - x_2^2y_1^2).
Note that x1y2−x2y1x_1y_2 - x_2y_1 and x1y2+x2y1x_1y_2 + x_2y_1 cannot both be divisible by pp, otherwise p∣2x1y2p \mid 2x_1y_2, which contradicts with pp being an odd prime and p∤x1y1x2y2p \nmid x_1y_1x_2y_2. Hence, pr∣x1y2−x2y1p^r \mid x_1y_2 - x_2y_1, or pr∣x1y2+x2y1p^r \mid x_1y_2 + x_2y_1.
If x1y2−x2y1=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, x1y2−x2y1≠0x_1y_2 - x_2y_1 \neq 0.
If pr∣x1y2+x2y1p^r \mid x_1y_2 + x_2y_1, then x1y2+x2y1≥prx_1y_2 + x_2y_1 \ge p^r.
If pr∣x1y2−x2y1p^r \mid x_1y_2 - x_2y_1, then x1y2+x2y1≥∣x1y2−x2y1∣≥prx_1y_2 + x_2y_1 \ge |x_1y_2 - x_2y_1| \ge p^r. Thus, in all cases,
x1y2+x2y1≥pr.(∗) 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)=(ax1x2−by1y2)2+ab(x1y2+x2y1)2≥ab(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

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.