Maths Olympiad Prep

Library / /3 of 84

, 2013

Number theory Difficulty 4.2 AIME Find the answer United States

Problem:
Find the number of positive divisors dd of 15!=15142115! = 15 \cdot 14 \cdots 2 \cdot 1 such that gcd(d,60)=5\operatorname{gcd}(d, 60) = 5.

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

Solution

Solution:
Since gcd(d,60)=5\operatorname{gcd}(d, 60) = 5, we know that d=5idd = 5^{i} d^{\prime} for some integer i>0i > 0 and some integer dd^{\prime} which is relatively prime to 6060. Consequently, dd^{\prime} is a divisor of (15!)/5(15!) / 5; eliminating common factors with 6060 gives that dd^{\prime} is a factor of (72)(11)(13)\left(7^{2}\right)(11)(13), which has (2+1)(1+1)(1+1)=12(2+1)(1+1)(1+1) = 12 factors. Finally, ii can be 1,21, 2, or 33, so there are a total of 312=363 \cdot 12 = 36 possibilities.

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.