Suppose $\gcd(2^5\times3^4 \times5^4 \times7 \times11, x) = d$ where $x$ and $d$ are integers. How many possible values of $d$ are there?

Question

Originally I thought that $d$ could be any of the prime factors listed, or $1$ when $x$ is a prime number not listed on the left. But obviously if $x$ is an integer that decomposes to several of the factors on the left, there are far more possibilities. I do not believe they are infinite, there must be some upper limit. How do I find $d$ mathematically?

Answer 1

Let $X = \{$ possible values of $d\}$.

If $d = \gcd(2^5*3^4 *5^4 *7 *11, x)\in X$ and $\gcd(2^5*3^4 *5^4 *7 *11,x)|2^5*3^4 *5^4 *7 *11$ so $d|2^5*3^4 *5^4 *7 *11$

$X \subset \{$ factors of $2^5*3^4 *5^4 *7 *11\}$.

Now if $k$ is a factor of $2^5*3^4 *5^4 *7 *11$ then $\gcd(2^5*3^4 *5^4 *7 *11, k) = k$.

So $\{$ factors of $2^5*3^4 *5^4 *7 *11\} \subset X$.

$X = \{$ factors of $2^5*3^4 *5^4 *7 *11\}$

And do you know how many factors $2^5*3^4 *5^4 *7 *11$ has? (If not... think about and research it).

....

$= \{2^a*3^b*5^c*7^d*11^e|0\le a \le 5; 0\le b\le 4;0\le c\le 4;0\le d\le 1; 0\le e \le 1\}$

So $|X| = $

$|\{2^a*3^b*5^c*7^d*11^e:0\le a \le 5; 0\le b\le 4;0\le c\le 4;0\le d\le 1; 0\le e \le 1\}| =$

$ |\{(a,b,c,d,e):0\le a \le 5; 0\le b\le 4;0\le c\le 4;0\le d\le 1; 0\le e \le 1\}|=$

$.... ????....$

Answer 2

Hint. Consider any possible value of $d$. How many factors of $2$ does $d$ have? How many factors of $3$ does $d$ have? Etc.

Answer 3

Well, if $x=2^a3^b5^c7^d11^e$, where $0\leq a\leq 5$ and $0\leq b\leq 4$... then $d=x$ so we have $$(5+1)(4+1)(4+1)(1+1)(1+1)$$ possibilities.