Non-coprime pairs with coprime $\gcd$'s.

Question

Given $m,n,k,l\in\mathbb Z$ such that $a = \gcd(m,n)\neq 1$ and $b = \gcd(k,l)\neq 1$, but $\gcd(a,b)=1$, are there $c,d\in\mathbb Z$ such that $$ \gcd(cm+dn,\,ck+dl) = 1\,? $$ I have already tried a lot, but I cannot seem to figure this out. When I denote $m' = m/a$, $n' = n/a$, $k' = k/b$ and $l' = l/b$, then $$ \gcd(cm+dn,\,ck+dl) = \gcd\big(a(cm'+dn'),\,b(ck'+dl')\big). $$ Clearly, I can find $c,d$ such that $cm'+dn' = 1$, but then it is not clear whether $a|(ck'+dl')$. Any help is appreciated.

Answer 1

You're on the right track. As you already basically stated,

$$a = \gcd(m, n) \implies m = am', \, n = an', \, \gcd(m', n') = 1 \tag{1}\label{eq1A}$$

$$b = \gcd(k, l) \implies k = bk', \, l = bl', \, \gcd(k', l') = 1 \tag{2}\label{eq2A}$$

With $a \neq 1$, $b \neq 1$ and $\gcd(a, b) = 1$, then there exist integers $c$ and $d$ such that

$$\gcd(cm + dn, \, ck + dl) = 1 \tag{3}\label{eq3A}$$

As you've already done, the left side is equivalent to

$$\gcd(cm + dn, \, ck + dl) = \gcd(a(cm' + dn'), \, b(ck' + dl')) \tag{4}\label{eq4A}$$

If $m' = n' = 0$, then $\gcd(m, n) = \gcd(0, 0) = a$ is not well defined but, if it's to be anything, it should be considered be $0$. However, using the third bullet point in the Properties section of Wikipedia's "Greatest common divisor" article, $1 = \gcd(a, b) = \gcd(0, b) = |b|$, so $b = 1$, but this is not allowed (this may be why this condition was specified in the question). This means $a$ and $b$ are non-zero, plus at least one of $m'$ and $n'$ is non-zero (and, similarly, at least one of $k'$ and $l'$ is non-zero). As such, using Bézout's identity, as you've already stated, there exist integers $c$ and $d$ such that

$$cm' + dn' = 1 \implies \gcd(a(cm' + dn'), \, b(ck' + dl')) = \gcd(a, \, b(ck' + dl')) \tag{5}\label{eq5A}$$

For any particular solution $c = c_{1}$ and $d = d_{1}$, the general solution is, for any integer $e$,

$$c = c_{1} - e(n'), \; d = d_{1} + e(m') \tag{6}\label{eq6A}$$

Using this gives

$$\begin{equation}\begin{aligned} ck' + dl' & = (c_{1} - e(n'))k' + (d_{1} + e(m'))l' \\ & = c_{1}k' + d_{1}l' + e(m'l' - n'k') \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

Let

$$f = \gcd(c_{1}k' + d_{1}l', m'l' - n'k') \tag{8}\label{eq8A}$$

If $f \neq 1$, then there's a prime $p \mid f$. Thus, if $l' \neq 0$, then

$$c_{1}k' \equiv -d_{1}l' \pmod{p} \implies c_{1}k'\color{blue}{m'} \equiv -d_{1}l'\color{blue}{m'} \pmod{p} \tag{9}\label{eq9A}$$

$$n'k' \equiv m'l' \pmod{p} \implies \color{red}{d_{1}}n'k' \equiv \color{red}{d_{1}}m'l' \pmod{p} \tag{10}\label{eq10A}$$

Adding \eqref{eq9A} and \eqref{eq10A} gives

$$c_{1}k'm' + d_{1}n'k' \equiv 0 \pmod{p} \implies k'(c_{1}m' + d_{1}n') \equiv 0 \pmod{p} \tag{11}\label{eq11A}$$

Since $c = c_{1}$ and $d = d_{1}$ is a particular solution to \eqref{eq5A}, this means $c_{1}m' + d_{1}n' = 1$, so \eqref{eq11A} becomes

$$k' \equiv 0 \pmod{p} \tag{12}\label{eq12A}$$

The first part of \eqref{eq10A} gives $m'l' \equiv 0 \pmod{p}$, but since \eqref{eq2A} gives $\gcd(k', l') = 1$, this means $p \mid \color{blue}{m'}$. Also, the first part of \eqref{eq9A} gives $d_{1}l' \equiv 0 \pmod{p} \implies p \mid \color{red}{d_{1}}$. Thus, $p \mid c_{1}\color{blue}{m'} + \color{red}{d_{1}}n' = 1$, which is not possible. Note if $l' = 0$, then $k' \neq 0$, so you can use a similar procedure to that above to eliminate $k'$ from \eqref{eq9A} and \eqref{eq10A} instead to get $l' \equiv 0 \pmod{p}$, and then continue to end up with the same contradiction.

This means the assumption $f \neq 1$ must be false, so $f = 1$. For simpler algebra, let

$$g = c_{1}k' + d_{1}l', \; h = m'l' - n'k' \tag{13}\label{eq13A}$$

From $f = \gcd(g, h) = 1$, we get

$$j = \gcd(g, a) \implies \gcd(j, h) = 1 \tag{14}\label{eq14A}$$

Using that $g$ and $h$ are coprime, or by doing direct calculations (note I'm not providing the details as this answer is already quite long), then if $g = 0$ then $h = \pm 1$ (so can choose $e = 1$), and if $h = 0$ then $g = \pm 1$. In either case, \eqref{eq3A} is then true.

Otherwise, for $g \neq 0$ and $h \neq 0$, have all of the prime factors of $a$ which divide $j$ be combined into $q$, i.e., have

$$a = qr, \; \gcd(q, j) = j, \; \gcd(q, r) = 1 \implies \gcd(q, h) = 1 \tag{15}\label{eq15A}$$

Thus, $h$ has a multiplicative inverse modulo $q$. Let

$$e \equiv h^{-1}(1 - g) \pmod{q} \implies g + eh \equiv g + h^{-1}(1 - g)h \equiv 1 \pmod{q} \tag{16}\label{eq16A}$$

Due to how $r$ is defined in \eqref{eq15A}, we also have $\gcd(r, g) = 1$ (if not, then any $p \mid r$ means $p \mid a$, so with $p \mid g$ this means $p \mid \gcd(a, g) = j$, so $p \mid q$, which is not allowed). Thus, set

$$e \equiv 0 \pmod{r} \implies \gcd(g + eh, r) = 1 \tag{17}\label{eq17A}$$

Since $\gcd(q, r) = 1$, the Chinese remainder theorem guarantees there's a solution for $e$ using the left sides of \eqref{eq16A} and \eqref{eq17A}. Also, those $2$ equations combined shows (using $a = qr$ from \eqref{eq15A}) that $\gcd(g + eh, q) = \gcd(g + eh, r) = 1 \implies \gcd(g + eh, a) = 1$. Thus, using \eqref{eq13A}, then \eqref{eq7A} becomes $\gcd(ck' + dl', a) = 1$. This means the $\gcd$ in \eqref{eq5A} is $1$, so \eqref{eq3A} is true.