Maths Olympiad Prep

Library / /66 of 348

Number theory Difficulty 4.7 AIME Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Since 91=7×1391=7 \times 13, we see that the possible values of \operatorname{gcd}(n, 91) are 1, 7, 13, 91. For 1n911 \leq n \leq 91, there is only one value of nn such that \operatorname{gcd}(n, 91)=91. Then, we see that there are 12 values of nn for which \operatorname{gcd}(n, 91)=7 (namely, multiples of 7 other than 91 ), 6 values of nn for which \operatorname{gcd}(n, 91)=13 (the multiples of 13 other than 91 ), and 911612=7291-1-6-12=72 values of nn for which \operatorname{gcd}(n, 91)=1. Hence, our answer is 1×91+12×7+6×13+72×1=3251 \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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.