Find number of pairs $(i, j)$ such that (gcd(i, j), lcm(i, j)) is the same for all pairs.

Question

Suppose we have a pair (p, q) and a pair (gcd(p, q), lcm(p, q)). I need to find a number of pairs (i, j) such that (gcd(i, j), lcm(i, j)) = (gcd(p, q), lcm(p, q)). How can i do it?

Answer 1

The answer is $2^n$, where $n$ is the number of primes for which the exponents in the prime factorizations of $p$ and $q$ differ. This is because for each pair of distinct exponents, one can either choose to keep them in the same order as in $p$ and $q$ respectively, or reverse their order without changing the gcd and lcm.