Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$.

Question

Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$.

What I know as of now is that $180\mid 9!$ and that $180\le a\le9!$.

The prime factorization of 180 is $(2^2)(3^2)(5^1)$

and the prime factorization of 9! is $(2^7)(3^4)(5^1)(7^1)$.

So I think I figured it out, there are exactly 7 positive integers for $a$. I'm not sure if this is correct, but this is what I have concluded.

Answer 1

What we know:

• $180 \mid a$
• $a$ and $3600$ share no common factors greater than $180$. In particular, any prime divisor of $3600$ cannot occur more times in $a$ than it does in $180$.
• $a \mid 9!$

So one strategy for counting the number of possible $a$'s can be counting the number of ways to build one, using these facts. First we know that $180 \mid a$, so $a$'s prime factorization must contain $(2^2)(3^2)(5^1)$. Additionally, it cannot contain any more $2$'s or $5$'s, as this would give a larger gcd with $3600$ (however, it can contain more $3$'s).

Considering the factorization of $9! = (2^7)(3^4)(5^1)(7^1)$, and removing the $180$ which is already fixed leaves the factorization $(2^5)(3^2)(7^1)$ to work with. But we can't multiply by $2$, as noted above. So we can really multiply by any factor of $(3^2)(7^1)$. There are $6$ such numbers -- we have $3$ ways to choose a power of $3$ and $2$ ways to choose a power of $7$ to use.

Answer 2

Hint $ $ Let $\,d={\large \frac{a}{180}}\,$ and cancel $180$ to get: $\,(d,20)=1\ $ & $\ d\:{\large\mid\, \frac{9!}{180}}\! = 2^5\cdot 3^2\cdot 7\iff d\mid 3^2\cdot 7$