Maths Olympiad Prep

Library / /6 of 133

Number theory Difficulty 4.5 AIME Prove it Saudi Arabia

Prove that among any 16 perfect cubes we can always find two cubes whose difference is divisible by 91.

Solution

Notice first that any perfect cube is congruent to either 00, 11 or 66 modulo 77 and it is congruent to either 00, 11, 55, 88, or 1212 modulo 1313. Because 77 and 1313 are relatively prime numbers, by the Chinese Remainder theorem, a perfect cube is congruent to precisely one of 15=3×515 = 3 \times 5 different residues modulo 91=7×1391 = 7 \times 13. Therefore, by the Pigeonhole principle, we can always find among any 1616 perfect cubes, two cubes which are congruent modulo 9191.

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.