Track / Stage 4 / 60 of 340 #800 of 2444

Problem 800

AMC 12 late, AIME early

Number theory Difficulty 4.4 Find the answer Harvard-MIT November Tournament · United States

For positive integers $m, n$ , let $\operatorname{gcd}(m, n)$ denote the largest positive integer that is a factor of both $m$ and $n$ . Compute
$\sum_{n=1}^{91} \operatorname{gcd}(n, 91) .$

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

Solution:

Answer: 325

Since $91 = 7 \times 13$ , we see that the possible values of $\operatorname{gcd}(n, 91)$ are $1, 7, 13, 91$ .

For $1 \leq n \leq 91$ , there is only one value of $n$ such that $\operatorname{gcd}(n, 91) = 91$ .

Then, we see that there are 12 values of $n$ for which $\operatorname{gcd}(n, 91) = 7$ (namely, multiples of 7 other than 91), 6 values of $n$ for which $\operatorname{gcd}(n, 91) = 13$ (the multiples of 13 other than 91), and $91 - 1 - 6 - 12 = 72$ values of $n$ for which $\operatorname{gcd}(n, 91) = 1$ .

Hence, our answer is $1 \times 91 + 12 \times 7 + 6 \times 13 + 72 \times 1 = 325$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.