Maths Olympiad Prep

Library / /4 of 12

Number theory Difficulty 7.6 National olympiad, round 2 Prove it Saudi Arabia

Let x,yx, y be two integers. Prove that if 20132013 divides x1433+y1433x^{1433} + y^{1433} then 20132013 divides x7+y7x^{7} + y^{7}.

Solution

Since 2013=3×11×612013 = 3 \times 11 \times 61, we will prove that for p=3,11,61p = 3, 11, 61, if pp divides x1433+y1433x^{1433} + y^{1433} then pp divides x7+y7x^{7} + y^{7}.

Let p=3,11,61p = 3, 11, 61, and assume that pp divides x1433+y1433x^{1433} + y^{1433}.

If pp divides xx, then it divides x7x^{7} and x1433x^{1433}. But pp divides x1433+y1433x^{1433} + y^{1433}. Then it divides y1433y^{1433}. Since pp is a prime number, we deduce that it divides yy and y7y^{7}. Therefore, it divides x7+y7x^{7} + y^{7}. In a similar way we prove that if pp divides yy, then it divides x7+y7x^{7} + y^{7}.

Assume now that pp is relatively prime with x,yx, y. Then, using Fermat,
xp1yp11modp x^{p-1} \equiv y^{p-1} \equiv 1 \quad \bmod p
But p1p-1 divides 14401440 for p=3,11,61p = 3, 11, 61. We deduce that
x1440y14401modp. x^{1440} \equiv y^{1440} \equiv 1 \quad \bmod p .
Hence
x7+y7x7y1440+y7x1440x7y7(y1433+x1433)0modp. x^{7} + y^{7} \equiv x^{7} y^{1440} + y^{7} x^{1440} \equiv x^{7} y^{7} (y^{1433} + x^{1433}) \equiv 0 \quad \bmod p .
This proves that pp divides x7+y7x^{7} + y^{7}.

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.