Find number of common divisors of 463050 and 2425500 I am new to combinatorics (second lesson in the course) and I was wondering how to solve the following problem in the most elegant way:

Find the number of common divisors for 463050 and 2425500?

My intuition tells me to divide both numbers by 10 which will lead me to 5 and 2 but I feel that there is some other way.
Thanks to all the kind helpers. 
p.s I will appreciate straightforward answer, and will appreciate even more a guidance on how to solve this kind of problems in the future.
 A: Among all the common divisors of the two numbers there is a greatest one, and this can be calculated easily:
$$\gcd(463050, 2425500)=22050$$
The prime factorisation of this number is
$$22050=2^13^25^27^2$$
so the number of common divisors is
$$\tau(22050)=(1+1)(2+1)(2+1)(2+1)=54$$
where $\tau(n)$ is the number-of-divisors function.
A: Strategy:  Every common divisor is a divisor of the greatest common divisor, so we must find the greatest common divisor, then determine how many factors it has.


*

*Use the Euclidean Algorithm to find the greatest common divisor.

*Factor the greatest common divisor into primes.  

*If the greatest common divisor has prime factorization 
$$p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_n^{\alpha_n}$$
then a common divisor has factorization
$$p_1^{\beta_1}p_2^{\beta_2} \ldots p_n^{\beta_n}$$
where $0 \leq \beta_k \leq \alpha_k$ for $1 \leq k \leq n$, so the number of divisors of the greatest common divisor is 
$$(\alpha_1 + 1)(\alpha_2 + 1) \ldots (\alpha_n + 1)$$

A: The simple Euclidean algorithm gives you the greatest common divisor (gcd) of the two numbers:
$\begin{array}{r|cc}
n\quad &  q \\ \hline
2425500  &  \\
463050  & 5 \\
110250  & 4 \\
22050  & 5 \\
0 &  \\
\end{array}$
with $q$ being the integer division of the current and previous $n$ values that indicates the multiple of the smaller for subtraction form the larger to get to the next $n$ value, eg. $463050 - 4\times 110250 = 22050$. The last number before reaching $0$ is the greatest common divisor. A number divides this number, $22050$, if and only if that number divides both $2425500$ and $463020$.
Then, fortunately, factorizing $22050$ is easy by trial division, giving $22050 = 2\cdot 3^2\cdot 5^2\cdot 7^2$ and the number of divisors for this number can be obtained in the usual way by the product of one more than each prime exponent, $2\cdot3\cdot 3\cdot 3=54$
In this case, factoring by trial division could have been used on the original numbers too, and the least common prime powers would provide another route to getting the gcd.
