Number of pairs with give GCD and LCM (proof)

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.

2 Attachment(s)

Re: Number of pairs with give GCD and LCM (proof)

Hi,

Your statement is not quite precise. The attachments give a precise statement and proof.

Attachment 29140

Attachment 29139

Re: Number of pairs with give GCD and LCM (proof)

Thanks a lot for your help, I understand it now