Maths Olympiad Prep

Library / IRL ABooklet /142 of 191

IRL ABooklet

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)2023∣ab−cd (ii) 2023 \mid ab - cd
(iii)2023∣a2+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=7⋅1722023 = 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)172∣wx−yz (ii) 17^2 \mid wx - yz
(iii)172∣w2+x2+y2+z2. (iii) 17^2 \mid w^2 + x^2 + y^2 + z^2.
Multiplying (i) by xx and using (ii), we obtain
0≡wx+x2+xy+xz≡yz+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 y≡z≡−w(mod17)y \equiv z \equiv -w \pmod{17} and x≡−y(mod17)x \equiv -y \pmod{17}, hence w2≡x2≡y2≡z2(mod17)w^2 \equiv x^2 \equiv y^2 \equiv z^2 \pmod{17}. Using (iii) we now see that
0≡w2+x2+y2+z2≡4w2(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 w≡x≡y≡z≡0(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=7d′a = 7a', b = 7b', c = 7c', d = 7d'. Dropping the primes, and noting 2023=7⋅1722023 = 7 \cdot 17^2 the problem requires us to investigate solutions to:
(i) a+b+c+d=172a + b + c + d = 17^2
(ii) 172∣ab−cd17^2 \mid ab - cd
(iii) 172∣a2+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) p2∣ab−cdp^2 \mid ab - cd
(iii) p2∣a2+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+(c−d)2≡0(modp2)(a−b)2+(c+d)2≡0(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 −c−d-c-d, and c+dc+d by −a−b-a-b in the second gives
c2+d2≡a2+b2≡0(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 b≡ai(modp2)b \equiv ai \pmod{p^2} and we have
a2+b2≡a2(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 i≠0(modp)i \neq 0 \pmod{p} and i≠−1(modp)i \neq -1 \pmod{p} so that ai≠0(modp)ai \neq 0 \pmod{p} and (1+i)a≠0(modp)(1+i)a \neq 0 \pmod{p}. Since b≡ai(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)(d−ic)≡0(modp2)c^2 + d^2 \equiv (d+ic)(d-ic) \equiv 0 \pmod{p^2}. We cannot have both p∣d+icp \mid d+ic and p∣d−icp \mid d-ic as that would imply p∣dp \mid d and hence p∣c+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 p2∣d−icp^2 \mid d-ic. Then we have 0≡a+b+c+d≡(1+i)(a+c)(modp2)0 \equiv a+b+c+d \equiv (1+i)(a+c) \pmod{p^2}.
As i≠−1(modp)i \neq -1 \pmod{p}, we can deduce that a+c≡0(modp2)a+c \equiv 0 \pmod{p^2}. Now a,ca, c are both positive integers so a+c≥p2a+c \ge p^2. But then we have 0<b+d=p2−a−c≤00 < 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,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.