Krdytkyu

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

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?

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

$begin{align}{bf Hint}
&gcd(X,Y) = d, {rm lcm}(X,Y) = m text{yields by cancelling $,dneq 0$}\[.3em]
iff &gcd(x,,y) = 1,qquad , xcdot 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 , xcdot 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.