Let N be the number of positive integer divisors of 1701717 that leave a remainder of 5 upon division by 12. Find the remainder when N is divided by 1000.
Announcement
Random Math Together Program - Free for USA(J)MO Qualifiers
Our together program brings together high-achieving students nationwide for team-based problem solving and to prepare for competitions such as HMMT, PUMaC, and more.
Eligibility: USA(J)MO qualifiers • Spots limited
Note that 17017=7×11×13×17. For a number to leave a remainder of 5 upon division by 12, it must leave a remainder of 1 mod 4 and 24 mod 3.
Suppose our divisor was 7a11b13c17d. Taking this modulo 4 gives
3a+b1c+d≡1(mod4)
so a+b is even. Taking this modulo 3 gives
1a+c2b+d≡2(mod4)
so b+d is odd.
Note a,b,c,d are any integer between 0 and 17 (inclusive). Thus, any choice for b results in 9 choices of a and d, and c can be chosen however. Thus, there are a total of
18⋅9⋅9⋅18=26244
divisors that are 5 modulo 12, for an answer of 244.
The problems on this page are the property of the MAA's American Mathematics Competitions