# Bezout's Identity in proving a pair of integers satisfies the linear integer combination [closed]

The problem states:

Let $$a,b,c \in \mathbb{Z}$$.

Prove that if a pair of integers $$(x_0,y_0)$$ solves the equation $$ax+by=c$$, then the pair $$(x_0+k \cdot b,y_0-k \cdot a)$$ is also an integer solution of $$ax+by=c$$ (where $$k$$ is an arbitrary integer).

This shows that if $$ax+by=c$$ has an integer solution, then it has infinitely many solutions.

• Recall that the general solution of a linear equation is the sum of any particular solution plus the general solution of the associated homogeneous equation (here $\,ax+by = 0)\ \$ Apr 19, 2020 at 18:16

I guess the straight-forward calculation gives you the desired result easily:

We are given $$ax+by=c$$ where $$a$$, $$b$$ and $$c$$ are integers. Also we know that there exists a pair of integers $$(x_{0},y_{0})$$ which satisfies the equation, i.e $$ax_{0}+by_{0}=c$$. We need to show that $$(x_{0}+k \cdot b, y_{0}-k \cdot a)$$ is also an integer solution of our equation. Thus, we need to show two things:

1- $$x_{0}+k \cdot b$$ and $$y_{0}-k \cdot a$$ are really integers

2- $$a[x_{0}+k \cdot b]+b(y_{0}-k \cdot a]=c$$.

(1) is clear since sum and product of integers are again an integer. For the (2) observe that $$a[x_{0}+k \cdot b]+b(y_{0}-k \cdot a]= ax_{0}+akb+by_{0}-bka=ax_{0}+by_{0}=c$$. Thus, $$(x_{0}+k \cdot b, y_{0}-k \cdot a)$$ is indeed a solution. Since for each integer value of k we have an integer solution to our equation, there are infinitely many solutions!

Let's look at a concrete example as well:

Suppose $$a=2$$, $$b=3$$ and $$c=17$$. Also, somehow, we found $$(4,3)$$ is a solution to our equation, i.e $$x_{0}=4$$ and $$y_{0}=3$$. Then, choosing

$$k=1$$ gives $$(x_{0}+kb, y_{0}-ka= (7,1)$$ is also a solution, surely $$2 \cdot 7 + 3 \cdot 1 =17$$. Thus, it is indeed a solution. $$k=-2$$ gives $$(x_{0}+kb, y_{0}-ka= (-2,7)$$ is another solution, since $$2 \cdot (-2) + 7 \cdot 3 = 17$$. I hope you get the idea.

$$a(x_0+kb)+b(y_0-ka)=ax_0+akb+by_0-bka=ax_0+by_0$$ that is equal to $$c$$ since $$(x_0,y_0)$$ solves the equation. Of course they are all integers.