Maths Olympiad Prep

Library / /31 of 42

Number theory Difficulty 6.6 National olympiad Prove it Ireland

The positive integers a,b,c,da, b, c, d satisfy
(i)a+b+c+d=2023 (i) a + b + c + d = 2023
(ii)2023abcd (ii) 2023 \mid ab - cd
(iii)2023a2+b2+c2+d2. (iii) 2023 \mid a^2 + b^2 + c^2 + d^2.
Assuming that each of the numbers a,b,c,da, b, c, d is divisible by 7, prove that each of the numbers a,b,c,da, b, c, d is divisible by 17.

Solution

Solution 1. First note that 2023=71722023 = 7 \cdot 17^2. If a,b,c,da, b, c, d are divisible by 7, there are positive integers w,x,y,zw, x, y, z such that
a=7w,b=7x,c=7y,d=7z a = 7w, \quad b = 7x, \quad c = 7y, \quad d = 7z
and the given conditions on a,b,c,da, b, c, d translate into
(i)w+x+y+z=172 (i) w + x + y + z = 17^2
(ii)172wxyz (ii) 17^2 \mid wx - yz
(iii)172w2+x2+y2+z2. (iii) 17^2 \mid w^2 + x^2 + y^2 + z^2.
Multiplying (i) by xx and using (ii), we obtain
0wx+x2+xy+xzyz+x2+yx+xz(x+y)(x+z)(mod172). 0 \equiv wx + x^2 + xy + xz \equiv yz + x^2 + yx + xz \equiv (x + y)(x + z) \pmod{17^2}.
Because w>0w > 0, (i) implies that 0<x+y<1720 < x + y < 17^2 and 0<x+z<1720 < x + z < 17^2. Since 17 is a prime number, we now see that both, x+yx + y and x+zx + z, must be divisible by 17. Knowing this, we can conclude from (i) that w+zw + z and

w+yw + y must also be divisible by 17. This means that yzw(mod17)y \equiv z \equiv -w \pmod{17} and xy(mod17)x \equiv -y \pmod{17}, hence w2x2y2z2(mod17)w^2 \equiv x^2 \equiv y^2 \equiv z^2 \pmod{17}. Using (iii) we now see that
0w2+x2+y2+z24w2(mod17). 0 \equiv w^2 + x^2 + y^2 + z^2 \equiv 4w^2 \pmod{17}.
This implies that ww is divisible by 17, hence wxyz0(mod17)w \equiv x \equiv y \equiv z \equiv 0 \pmod{17} as required.

Solution 2. As we are allowed to assume a,b,c,da, b, c, d are divisible by 7, then we can write a=7a,b=7b,c=7c,d=7da = 7a', b = 7b', c = 7c', d = 7d'. Dropping the primes, and noting 2023=71722023 = 7 \cdot 17^2 the problem requires us to investigate solutions to:
(i) a+b+c+d=172a + b + c + d = 17^2
(ii) 172abcd17^2 \mid ab - cd
(iii) 172a2+b2+c2+d217^2 \mid a^2 + b^2 + c^2 + d^2.
We are required to show that a,b,c,da, b, c, d are all multiples of 17. It turns out the only relevant special properties of 17 are that it is an odd prime, so we make the following more general claim.
Let pp be an odd prime and let a,b,c,da, b, c, d be positive integers such that
(i) a+b+c+d=p2a + b + c + d = p^2
(ii) p2abcdp^2 \mid ab - cd
(iii) p2a2+b2+c2+d2p^2 \mid a^2 + b^2 + c^2 + d^2.
Then all of a,b,c,da, b, c, d are multiples of pp. If we can prove this claim, the original problem is then solved by writing p=17p = 17.
Adding or subtracting twice criterion (ii) from criterion (iii) gives
(a+b)2+(cd)20(modp2)(ab)2+(c+d)20(modp2). (a + b)^2 + (c - d)^2 \equiv 0 \pmod{p^2} \\ (a - b)^2 + (c + d)^2 \equiv 0 \pmod{p^2}.
Using (i) to replace a+ba+b in the first equation by cd-c-d, and c+dc+d by ab-a-b in the second gives
c2+d2a2+b20(modp2). c^2 + d^2 \equiv a^2 + b^2 \equiv 0 \pmod{p^2}.

Suppose for a contradiction that (without loss of generality given the symmetry of the equations) aa is not a multiple of pp. Then, as aa and p2p^2 are relatively prime, there is a residue ii such that bai(modp2)b \equiv ai \pmod{p^2} and we have
a2+b2a2(1+i2)0(modp2)a^2 + b^2 \equiv a^2(1 + i^2) \equiv 0 \pmod{p^2} whence i2=1(modp2)i^2 = -1 \pmod{p^2}. It is clear that i0(modp)i \neq 0 \pmod{p} and i1(modp)i \neq -1 \pmod{p} so that ai0(modp)ai \neq 0 \pmod{p} and (1+i)a0(modp)(1+i)a \neq 0 \pmod{p}. Since bai(modp2)b \equiv ai \pmod{p^2} and a+b(1+i)a(modp2)a+b \equiv (1+i)a \pmod{p^2}, it follows that neither bb nor a+ba+b are multiples of pp.
Now recall c2+d2(d+ic)(dic)0(modp2)c^2 + d^2 \equiv (d+ic)(d-ic) \equiv 0 \pmod{p^2}. We cannot have both pd+icp \mid d+ic and pdicp \mid d-ic as that would imply pdp \mid d and hence pc+dp \mid c+d, contradicting a+b+c+d=p2a+b+c+d=p^2. So one of the factors must be divisible by p2p^2. By swapping cc and dd if necessary, we may assume p2dicp^2 \mid d-ic. Then we have 0a+b+c+d(1+i)(a+c)(modp2)0 \equiv a+b+c+d \equiv (1+i)(a+c) \pmod{p^2}.
As i1(modp)i \neq -1 \pmod{p}, we can deduce that a+c0(modp2)a+c \equiv 0 \pmod{p^2}. Now a,ca, c are both positive integers so a+cp2a+c \ge p^2. But then we have 0<b+d=p2ac00 < b+d = p^2-a-c \le 0, which is the required 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.