Library / Saudi Arabian Mathematical Competitions /16 of 395

Saudi Arabian Mathematical Competitions

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 $0$ , $1$ or $6$ modulo $7$ and it is congruent to either $0$ , $1$ , $5$ , $8$ , or $12$ modulo $13$ . Because $7$ and $13$ are relatively prime numbers, by the Chinese Remainder theorem, a perfect cube is congruent to precisely one of $15 = 3 \times 5$ different residues modulo $91 = 7 \times 13$ . Therefore, by the Pigeonhole principle, we can always find among any $16$ perfect cubes, two cubes which are congruent modulo $91$ .

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.