Exercise 1.3.45* (Count the pairs $(x,y)$ with given gcd and lcm.)

Question

Let positive integers $g$ and $l$ be given with $g\mid l$. Prove that the number of pairs of positive integers $x,y$ satisfying $(x,y) = g$ and $[x,y] = l$ is $2^k$, where $k$ is the number of distinct prime factors of $l/g$.(Count $x_1,y_1$ and $x_2,y_2$ as different pairs if $x_1 
e x_2$ or $y_1 
e y_2$.)

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

Notations: 
\begin{itemize}
\item $(x,y)$ denotes an ordered pair, so that $(x,y) = (x',y') \iff x= x'$ and $y=y'$ (universal notation).
\item $\{x,y\}$ unordered pair : $ t \in \{x,y\} \iff t = x 	ext{ or } t = y\}$.
\item $x\wedge y = \mathrm{gcd}(x,y)$.
\item $x \vee y = \mathrm{lcm}(x,y)$.
\end{itemize}

We begin with an example. Take 
\begin{align*}
g &= 3\cdot 5^2,\
l &= 3 \cdot 5^3\cdot 11^2.
\end{align*}
Then the ordered pairs $(x,y)$ such that $x\wedge y = g, x \vee y = l$ are
$$
\begin{array}{|c|c|}
x & y\
\hline
3 \cdot 5^2 & 3 \cdot 5^3 \cdot 11^2\
3 \cdot 5^3 & 3 \cdot 5^2 \cdot 11^2\
3 \cdot 5^2  \cdot 11^2 & 3 \cdot 5^3\
3 \cdot 5^3 \cdot 11^2 & 3 \cdot 5^2\
\hline
\end{array}
$$
We have no choice for the common factor $3$, but we can take $5^2$ to the left and $5^3$ to the right, or the inverse. Idem with $11^2,11^0=1$.

Now we give a proof for the general case.
\begin{proof}

Let $p_1^{a_1},\ldots,p_l^{a_l}$ the powers of primes common to $g$ and $l$, and $q_1,\ldots,q_k$ the primes whose powers are distinct in the decompositions of $g$ and $l$ in prime factors:
\begin{align*}
g &= p_1^{a_1}\cdots p_l^{a_l} q_1^{b_1} \cdots q_k^{b_k},\qquad a_i>0\quad  (1 \leq i \leq l), \
l&=p_1^{a_1}\cdots p_l^{a_l} q_1^{c_1} \cdots q_k^{c_k},\qquad 0\leq b_i < c_i\quad  (1\leq j \leq k).
\end{align*}
Then $l/g = q_1^{c_1 - b_1}\cdots q_k^{c_k -b_k}$, where $c_j - b_j>0$ for $j = 1,\ldots k$, so that the prime factors of $l/g$ are $q_1,\ldots,q_k$.

The prime factors of $x, y$ are in $\{p_1,\ldots, p_l, q_1,\ldots,q_k\}$ (the prime factors of $x \vee y$).

Write
\begin{align*}
x &= p_1^{u_1}\cdots p_l^{u_l} q_1^{v_1} \cdots q_k^{v_k},\
y &= p_1^{u'_1}\cdots p_l^{u'_l} q_1^{v'_1} \cdots q_k^{v'_k}.
\end{align*}
Hence, for every $i =1,\ldots,l$,
$$a_i = \min(u_i,u'_i) = \max(u_i,u'_i),$$
therefore $a_i = u_i = u'_i$.

For every $j = 1,\ldots,k$,
$$b_j= \min(v_j,v'_j),\qquad c_j = \max(v_j,v'_j).$$
Hence
\begin{align*}
v_j = b_j &	ext{ and } v'_j = c_j,\quad \
&	ext{ or }\
v_j = c_j &	ext{ and } v'_j = b_j.
\end{align*}

There are two ways to choose $v_j, v'_j$ to build a solution $(x,y)$, for every $j =1,\ldots, k$. This gives $2^k$ solutions.

\bigskip
More formally, note that we can write in both cases
\begin{align*}
v_j &= \varepsilon_j b_j + (1 -\varepsilon_j)c_j,\
 v'_j &= (1-\varepsilon_j )b_j + \varepsilon_j c_j,
 \end{align*}
 where $\varepsilon_j \in \{0,1\}$.

Let $S$ be the set of solutions $(x,y)$:
$$S = \{(x,y)\in \N^2 \mid x\wedge y = g,\  x \vee y = l\},$$
 and consider the map $\varphi$
$$
\left\{
\begin{array}{ccl}
\{0,1\}^k & 	o & S,\
(\varepsilon_1,\ldots,\varepsilon_k) & \mapsto &( p_1^{a_1}\cdots p_l^{a_l} q_1^{\varepsilon_1 b_1 + (1 -\varepsilon_1)c_1} \cdots q_k^{\varepsilon_k b_k + (1 -\varepsilon_k)c_k},\  p_1^{a_1}\cdots p_l^{a_l} q_1^{(1-\varepsilon_1)b_1 + \varepsilon_1 c_1} \cdots q_k^{(1-\varepsilon_k)b_k + \varepsilon_k c_k})
\end{array}
ight.
$$
Then $\varphi$ is a bijection, and $|S| = |\{0,1\}^k| = 2^k.$

\bigskip
To conclude, if $l,g \in \N^*$ are such that $g\mid l$, the number of $(x,y) \in \N^2$ satisfying $x \wedge y = g$ and $x \vee y= l$ is $2^k$, where $k$ is the number of distinct prime factors of $l/g$.
\end{proof}

Exercise 1.3.45* (Count the pairs $(x,y)$ with given gcd and lcm.)

Answers

Comments

Exercise 1.3.45* (Count the pairs $(x,y)$ with given gcd and lcm.)

Answers

Comments

Add answer