Competition problem — Number theory

Library / /12 of 82

Number theory Difficulty 4.4 AIME Find the answer United States

Problem:

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.

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$ .

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 reproduced verbatim; metadata (topic, difficulty) added by this project.