Library / National Math Olympiad - Final Round /1 of 9

National Math Olympiad - Final Round, 2013

Number theory Difficulty 5.1 AIME, harder Prove it Slovenia

What is the greatest common divisor of the numbers $11n + 4$ and $7n + 2$ , where $n$ is a positive integer?

Solution

The greatest common divisor of $11n+4$ and $7n+2$ also divides $7(11n+4) - 11(7n+2) = 6$ , so it can be at most $6$ . If $n=4$ , then $11n+4 = 48$ and $7n+2 = 30$ , and the greatest common divisor of these two numbers is $6$ . Hence, the answer is $6$ .

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.