For positive integers , let \operatorname{gcd}(m, n) denote the largest positive integer that is a factor of both and . Compute
Solution
Since , we see that the possible values of \operatorname{gcd}(n, 91) are 1, 7, 13, 91. For , there is only one value of such that \operatorname{gcd}(n, 91)=91. Then, we see that there are 12 values of for which \operatorname{gcd}(n, 91)=7 (namely, multiples of 7 other than 91 ), 6 values of for which \operatorname{gcd}(n, 91)=13 (the multiples of 13 other than 91 ), and values of for which \operatorname{gcd}(n, 91)=1. Hence, our answer is .
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.