uniolympiads Ελληνικά

IMC 2007, Day 2, Problem 2

Let xx, yy, and zz be integers such that S=x4+y4+z4S = x^4 + y^4 + z^4 is divisible by 2929. Show that SS is divisible by 29429^4.

Original from the official PDFLet x, y, and z be integers such that S = x 4 + y 4 + z 4 is divisible by 29. Show that S is divisible by 29 4 .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. We claim that 29 ∣ x,y,z29\,|\,x,y,z. Then, x4+y4+z4x^4+y^4+z^4 is clearly divisible by 29429^4.

Assume, to the contrary, that 29 does not divide all of the numbers x,y,zx,y,z. Without loss of generality, we can suppose that 29∤x29\nmid x. Since the residue classes modulo 29 form a field, there is some w∈Zw\in\mathbb Z such that xw≡1(mod29)xw\equiv1\pmod{29}. Then, (xw)4+(yw)4+(zw)4(xw)^4+(yw)^4+(zw)^4 is also divisible by 29. So we can assume that x≡1(mod29)x\equiv1\pmod{29}.

Thus, we need to show that y4+z4≡−1(mod29)y^4+z^4\equiv-1\pmod{29}, i.e. y4≡−1−z4(mod29)y^4\equiv-1-z^4\pmod{29}, is impossible. There are only eight fourth powers modulo 29,

0≡04,1≡14≡124≡174≡284(mod29),7≡84≡94≡204≡214(mod29),16≡24≡54≡244≡274(mod29),20≡64≡144≡154≡234(mod29),23≡34≡74≡224≡264(mod29),24≡44≡104≡194≡254(mod29),25≡114≡134≡164≡184(mod29).\begin{aligned}0&\equiv0^4,\\1&\equiv1^4\equiv12^4\equiv17^4\equiv28^4\pmod{29},\\7&\equiv8^4\equiv9^4\equiv20^4\equiv21^4\pmod{29},\\16&\equiv2^4\equiv5^4\equiv24^4\equiv27^4\pmod{29},\\20&\equiv6^4\equiv14^4\equiv15^4\equiv23^4\pmod{29},\\23&\equiv3^4\equiv7^4\equiv22^4\equiv26^4\pmod{29},\\24&\equiv4^4\equiv10^4\equiv19^4\equiv25^4\pmod{29},\\25&\equiv11^4\equiv13^4\equiv16^4\equiv18^4\pmod{29}.\end{aligned}
The differences −1−z4-1-z^4 are congruent to 28, 27, 21, 12, 8, 5, 4, and 3. None of these residue classes is listed among the fourth powers.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?