Maths Olympiad Prep

Library / /27 of 348

Number theory Difficulty 4.6 AIME Find the answer

Find the number of positive integer divisors of 12 ! that leave a remainder of 1 when divided by 3.

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

Solution

First we factor 12!=21035527111112!=2^{10} 3^{5} 5^{2} 7^{1} 11^{1}, and note that 2,5,111(mod3)2,5,11 \equiv-1(\bmod 3) while 717 \equiv 1 (mod3)(\bmod 3). The desired divisors are precisely 2a5b7c11d2^{a} 5^{b} 7^{c} 11^{d} with 0a10,0b2,0c1,0d10 \leq a \leq 10,0 \leq b \leq 2,0 \leq c \leq 1,0 \leq d \leq 1, and a+b+da+b+d even. But then for any choice of a,ba, b, exactly one d{0,1}d \in\{0,1\} makes a+b+da+b+d even, so we have exactly one 1(mod3)1(\bmod 3)-divisor for every triple (a,b,c)(a, b, c) satisfying the inequality constraints. This gives a total of (10+1)(2+1)(1+1)=66(10+1)(2+1)(1+1)=66.

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.