4
$\begingroup$

These two exercises I encountered recently seem to develop some type of connection between GCD and LCM I can't quite figure out.

Exercise 1:

Find all the numbers $x$ and $y$ such that:

$a) \ GCD(x,y)=15, \ LCM(x,y)=150$ $b) \ GCD(x,y)=120 \ LCM(x,y)=1320$ $c) \ GCD(x,y)=100 \ LCM(x,y)=990$

Exercise 2:

Find all the numbers $m,n$ such that $GCD(m,n)=pq , \ LCM(m,n)=p^2qs$

where $p,q,s$ are prime

The first thing that is known to me is that $GCD(x,y) \cdot LCM(x,y)= x \cdot y$

Also $LCM(x,y)$ is at most $x \cdot y$ while $GCD(x,y)$ is at most $\max \{x,y\}$. Last thing is that $GCD(x,y)|LCM(x,y)$.

Using all this I tried to solve the first exercise:

$a)$ First two obvious pairs are $x=15, y=150$ and $y=15, x=150$. Now neither of the numbers can be bigger than $150$ or smaller than $15$. So we are looking for numbers in the range $15-150$ that satisfy $x \cdot y = 15 \cdot 150$ Another such pair is $(x,y)=(30,75), \ (x,y)=(75,30)$.

Similarly for $b)$ we find that the only possible values are permutations of the set {$120,1320$} and in $c)$ since $100$ does not divide $990$ no such numbers exist.

Now exercise 2 is what made me think there is actually another connection I'm not quite aware of since now it's about arbitrary prime numbers and the previous method doesn't work anymore. My intuition is that it has something to do with $GCD$ or $LCM$ of the $GCD(x,y), \ LCM(x,y)$

$\endgroup$
  • 1
    $\begingroup$ Do you mean $lcm(m,n)=p^2qs$ and $gcd(m,n)=pq$? $\endgroup$ – tarit goswami Nov 21 '18 at 16:35
2
$\begingroup$

If you have two numbers with prime factorizations

$$x = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_n^{a_n}$$ $$y = p_1^{b_1}p_2^{b_2}p_3^{b_3}\cdots p_n^{b_n}$$

then

$$GCD(x,y) = p_1^{min(a_1, b_1)}p_2^{min(a_2, b_2)}p_3^{min(a_3, b_3)}\cdots p_n^{min(a_n, b_n)}$$

and

$$LCM(x,y) = p_1^{max(a_1, b_1)}p_2^{max(a_2, b_2)}p_3^{max(a_3, b_3)}\cdots p_n^{max(a_n, b_n)}$$

where $min(a,b)$ and $max(a,b)$ are the minimum and maximum of $a$ and $b$, respectively.

Does this help?

$\endgroup$
  • 1
    $\begingroup$ That is same as lhf saying $\endgroup$ – tarit goswami Nov 21 '18 at 16:40
3
$\begingroup$

$\begin{align}{\bf Hint}\ \ &\gcd(X,Y) = d,\ \ \ {\rm lcm}(X,Y) = m \ \ \ \text{yields by cancelling $\,d\neq 0$}\\[.3em] \iff\ &\gcd(x,\,y)\ \ = 1,\qquad\ \ \, x\cdot y\ =\, m/d,\ \ {\rm for}\ \ x = X/d,\,\ y = Y/d \end{align}$

$\begin{align}{\rm e.g.}\ \ \ &\gcd(X,Y) = 15,\ \, {\rm lcm}(X,Y) = 150\\[.3em] \iff\ &\gcd(x,\,y)\ \ =\ 1,\qquad\ \ \, x\cdot y\,\ =\,\ 10 \end{align}$

This method quickly and simply solves all of them. Cancelling to reduce to the coprime case is a common way to simplify homogeneous divisibility problems.

$\endgroup$
2
$\begingroup$

Here is the relevant fact:

Let $d=gcd(a,b)$ and $m=lcm(a,b)$. Then $v_p(d)=\min(v_p(a),v_p(b))$ and $v_p(m)=\max(v_p(a),v_p(b))$.

Here, $v_p(n)$ is the exponent of the prime $p$ in the factorization of $n$.

$\endgroup$
  • $\begingroup$ Somehow completely forgot about prime factorisation and how it relates to everything I wrote. $\endgroup$ – DreaDk Nov 21 '18 at 16:43
  • 1
    $\begingroup$ In other words, $\gcd(a,b)\cdot\text{lcm}(a,b)=a\cdot b$. $\endgroup$ – vrugtehagel Nov 21 '18 at 16:44

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.