# The relationship between GCD and LCM

I am completing a problem in hackerrank that counts the number of integers that can be divided by all elements of a set $$A$$ and divide all elements of another set $$B$$.

I completed the problem using a ugly brute force method then found the following solution.

1. Find the LCM of $$A$$
2. Find the GCD of $$B$$
3. Find how many divisors $$GCD(B)/LCM(A)$$ has.

From going through a few examples I can see that it works. I am not sure WHY though.

• it because there a property that say tha for 2 integers number $\text{lcm}(a,b)\text{gcd}(a,b)=ab$ – cand Mar 18 at 18:26

By the universal properties of $$\rm gcd$$ and $$\rm lcm$$ we have
\qquad\begin{align} a_1,\ldots,a_j\mid n &\iff L:= {\rm lcm}(a_1,\ldots,a_j)\mid n\\[.5em] n\mid b_1,\ldots,b_k &\iff n\mid \gcd(b_1,\ldots,b_k) =: G \end{align}
So both hold $$\iff \ L\mid n\mid G\,\iff\, L\mid n,G \$$ & $$\ n/L \mid G/L$$
Therefore your method is correct:  find all divisors $$\,n/L\,$$ of $$\,G/L,\,$$ then scale each by $$L$$ to get $$n$$.
If all elements of $$A$$ divide a number $$c$$, that means there is an integer $$n$$ with $$c = n\cdot\mathrm{LCM}(A)$$. Similarly, if $$c$$ divides every element of $$B$$, then there is an integer $$m$$ with $$mc = \mathrm{GCD}(B)$$. Thus, for each number $$c$$ that has the aforementioned properties, there is a unique pair of integers $$(m,n)$$ such that $$mn\cdot\mathrm{LCM}(A)= \mathrm{GCD}(B)$$, or equivalently that $$mn = \mathrm{GCD}(B)/\mathrm{LCM}(A)$$. Clearly there is one such pair for each divisor of $$\mathrm{GCD}(B)/\mathrm{LCM}(A)$$.