1
$\begingroup$

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.

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

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$.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.