Extend triple of coprime numbers to summation of coprime numbers

53 Views Asked by At

I apologize if this has already been answered or is common knowledge. If either of these is the case a reference will suffice.

Given $a, b, c$ positive integers which are pairwise relatively prime, do there exist positive integers $x,y,z$ such that $$a x + b y = cz$$ and $ax, by, cz$ are pairwise relatively prime?

1

There are 1 best solutions below

0
On

Yes. In fact, we can always do this with $x = 1$.

We start by just finding an arbitrary solution to the identity. Choose $y_0$ such that $by_0 \equiv -a \pmod c$; this is possible because $b$ has an inverse modulo $c$. Then we have $a + by_0 = cz_0$, and all is right with the world, except that these might not be relatively prime.

We can generate an infinite family of these solutions of the form $$a + b(y_0 + ck) = c(z_0 + bk)$$ where $k$ can be any natural number. It suffices to choose $k$ to avoid any common factors between the three terms.

(Note that if two of $ax, by, cz$ have a common divisor, the third is divisible by it as well. So it suffices to only check that $\gcd(ax, by) = 1$, which is what we do.)

We know that $\gcd(a, y) = 1$ if $y \equiv 1 \pmod a$. So choose $k$ to solve the equation $ck \equiv 1-y_0 \pmod a$; this is possible because $c$ has an inverse modulo $a$. Then $\gcd(a, y_0 + ck) = 1$, so $\gcd(a, b(y_0+ck)) = 1$: we already knew that $\gcd(a,b)=1$.

So we've found a solution where the first two terms are relatively prime, and therefore all three terms are pairwise relatively prime.