Exercise 1486Number theory › Diophantine equationsL1Added 2 Nov 2026

Solving $ax+by=c$

#Diophantine equation#Bézout#solvability criterion

Statement

Let $a,b,c$ be integers with $a,b$ not both zero. Show that $ax+by=c$ has integer solutions if and only if $\divisibility(a,b)\mid c$ .

Hint

For the forward direction, note that $\divisibility(a,b)$ divides every linear combination. For the converse, use Bézout.

Show solutionHide solution

Solution

Necessity. If $ax+by=c$ and $d=\divisibility(a,b)$ , then $d\mid a$ and $d\mid b$ , so $d\mid ax+by=c$ .

Sufficiency. Suppose $d\mid c$ , say $c=dq$ . By Bézout, there exist $u,v$ with $au+bv=d$ . Multiplying by $q$ :
$a(uq)+b(vq)=dq=c.$
So $(x,y)=(uq,vq)$ is a solution.

Solving $ax+by=c$

Statement

Solution

More problems in Diophantine equations