If $a,b,c$ are pairwise relatively prime integers, do there always exist coprime integers $x,y$ such that $ax+by=c$

1k Views Asked by At

Given pairwise relatively prime integers $a$ and $b$, Bezout’s identity guarantees that there exist integers $x$ and $y$ such that $$ax+by=1=\gcd(a,b).$$

Trivially, one can multiply that solution by $c$ to obtain $$a(cx)+b(cy)=c.$$ But I’m wondering if there are always relatively prime solutions.

QUESTION: For every triple of pairwise relatively prime integers $(a,b,c)$, does there exist at least one pair of coprime integers $(x,y)$ such that $$ax+by=c$$

?

1

There are 1 best solutions below

4
On BEST ANSWER

Given $ax+by=1$, let $x_1=cx-b,y_1=cy+a$. Then $ax_1+by_1=c$.

If $p\mid x_1$ and $p\mid y_1$, then $p\mid c=ax_1+by_1$, and thus $p\mid b=cx-x_1$ and $p\mid a=y_1-cy$ and thus, $a,b$ have $p$ as a common factor.

So $x_1$ and $y_1$ is a solution with relatively prime values.

Note, we only needed $(a,b)$ relatively prime - $c$ can be anything.