Maths Olympiad Prep

Library / /15 of 155

Number theory Difficulty 4.9 AIME Prove it Saudi Arabia

Let a>b>c>da > b > c > d be positive integers such that a2+acc2=b2+bdd2a^{2} + a c - c^{2} = b^{2} + b d - d^{2}. Prove that ab+cda b + c d is a composite number.

Solution

By contrary, assume that p=ab+cdp = a b + c d is a prime. In particular (b,c)=(b,d)=1(b, c) = (b, d) = 1, and abcd(modp)a b \equiv -c d \pmod{p}. We get
0=b2(b2+bdd2)b2(a2+acc2)=b2(b2+bdd2)(ab)2(ab)(bc)+b2c2(b2+c2)(b2+bdd2)(modp) \begin{aligned} 0 & = b^{2} (b^{2} + b d - d^{2}) - b^{2} (a^{2} + a c - c^{2}) \\ & = b^{2} (b^{2} + b d - d^{2}) - (a b)^{2} - (a b)(b c) + b^{2} c^{2} \\ & \equiv (b^{2} + c^{2})(b^{2} + b d - d^{2}) \pmod{p} \end{aligned}
Therefore, one of the numbers b2+c2b^{2} + c^{2} and b2+bdd2b^{2} + b d - d^{2} is divisible by pp. If pb2+c2p \mid b^{2} + c^{2}, then b2+c2=pb^{2} + c^{2} = p since 0<b2+c2<2(ab+cd)=2p0 < b^{2} + c^{2} < 2(a b + c d) = 2p. This shows ab+cd=b2+c2a b + c d = b^{2} + c^{2} and then bc(cd)b \mid c(c - d). But b,cb, c are coprime, we get bcdb \mid c - d which is impossible.
If pb2+bdd2p \mid b^{2} + b d - d^{2}, then b2+bdd2=pb^{2} + b d - d^{2} = p since 0<b2+bdd2<2b2<2ab<2p0 < b^{2} + b d - d^{2} < 2 b^{2} < 2 a b < 2p. This shows that ab+cd=b2+bdd2a b + c d = b^{2} + b d - d^{2} and then
b(ab)=bdcdd2=d(bcd) b(a - b) = b d - c d - d^{2} = d(b - c - d)
In particular, bcd>0b - c - d > 0 and bbcdb \mid b - c - d (since bb, dd are coprime) which is impossible, again.
Hence, ab+cda b + c d must be a composite number.

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 and solution reproduced as published; topic and difficulty added by this site.