Maths Olympiad Prep

Library / /7 of 48

Number theory Difficulty 4.5 AIME Prove it Baltic Way

Problem:
Let a,b,c,da, b, c, d be positive integers such that ab=cda b = c d. Prove that a+b+c+da + b + c + d is not prime.

Solutions — 2

Solution 1

Solution:
As ab=cda b = c d, we get a(a+b+c+d)=(a+c)(a+d)a(a + b + c + d) = (a + c)(a + d). If a+b+c+da + b + c + d were a prime, then it would be a factor in either a+ca + c or a+da + d, which are both smaller than a+b+c+da + b + c + d.

Solution 2

Solution:
Let r=gcd(a,c)r = \operatorname{gcd}(a, c) and s=gcd(b,d)s = \operatorname{gcd}(b, d). Let a=ara = a' r, b=bsb = b' s, c=crc = c' r and d=dsd = d' s. Then ab=cda' b' = c' d'. But gcd(a,c)=1\operatorname{gcd}(a', c') = 1 and gcd(b,d)=1\operatorname{gcd}(b', d') = 1, so we must have a=da' = d' and b=cb' = c'. This gives
a+b+c+d=ar+bs+cr+ds=ar+bs+br+as=(a+b)(r+s). a + b + c + d = a' r + b' s + c' r + d' s = a' r + b' s + b' r + a' s = (a' + b')(r + s).
Since aa', bb', rr and ss are positive integers, a+b+c+da + b + c + d is not a prime.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.