Maths Olympiad Prep

Library /

Number theory Difficulty 7.9 National olympiad, round 2 Prove it United States

Determine all integers s4s \ge 4 for which there exist positive integers a,b,c,da, b, c, d such that s=a+b+c+ds = a+b+c+d and ss divides abc+abd+acd+bcdabc + abd + acd + bcd.

Solution

The answer is ss composite.

Composite construction Write s=(w+x)(y+z)s = (w+x)(y+z), where w,x,y,zw, x, y, z are positive integers. Let a=wya = wy, b=wzb = wz, c=xyc = xy, d=xzd = xz. Then
abc+abd+acd+bcd=wxyz(w+x)(y+z) abc + abd + acd + bcd = wxyz(w+x)(y+z)
so this works.

Prime proof Choose suitable a,b,c,da, b, c, d. Then
(a+b)(a+c)(a+d)=(abc+abd+acd+bcd)+a2(a+b+c+d)0(mods). (a+b)(a+c)(a+d) = (abc+abd+acd+bcd) + a^2(a+b+c+d) \equiv 0 \pmod{s}.
Hence ss divides a product of positive integers less than ss, so ss is composite.

Remark. Here is another proof that ss is composite.
Suppose that ss is prime. Then the polynomial (xa)(xb)(xc)(xd)Fs[x](x-a)(x-b)(x-c)(x-d) \in \mathbb{F}_s[x] is even, so the roots come in two opposite pairs in Fs\mathbb{F}_s. Thus the sum of each pair is at least ss, so the sum of all four is at least 2s>s2s > s, contradiction.

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.