Maths Olympiad Prep

Library / HMMT November /64 of 672

HMMT November

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,11≡−1( mod 3)2,5,11 \equiv-1(\bmod 3) while 7≡17 \equiv 1 ( mod 3)(\bmod 3). The desired divisors are precisely 2a5b7c11d2^{a} 5^{b} 7^{c} 11^{d} with 0≤a≤10,0≤b≤2,0≤c≤1,0≤d≤10 \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( mod 3)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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.