Hello, I would like a proof for the following algorithm, please.
In order to find the number of pairs with a given GCD (greatest common divisor) and LCM (least common multiple), I find the number n of prime factors in LCM/GCD. The number of pairs is equal to 2^n.
Example: GCD=2 and LCM=120
LCM/GCD = 60 = 2^2 * 5 * 3 therefore we have 2^3 (we have 3 prime factors) pairs.