HMMT November

Number theory Difficulty 4.7 AIME Find the answer

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

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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.