Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

Let and whenever is a positive integer. Define to be the greatest common divisor of and . What is the sum of all possible values of ?
Solution
Use the Euclidean algorithm on and . From applying the Euclidean algorithm, we have that the greatest common divisor of and is 11 if and only if is a multiple of 11. For example, note that and , and the greatest common divisor of 55 and 22 turns out to be 11. If is not a multiple of 11, then the greatest common divisor of and must be one, since 11 is prime and therefore has no other factors. It follows that can take on two distinct values; 1 and 11. The sum of all possible values of is therefore .
Final answer
12