MHB Diophantine equation ax-by=c has infinitely many solutions

[evinda]

Hi!
I am looking at the following exercise:
Let $a,b>0, (a,b)=1$.Prove that the diophantine equation $ax-by=c$ has infinitely many solutions with $x,y>0$.

As $(a,b)=1$ $\exists x_0,y_0$ such that $ax_0+by_0=1$, so $a(cx_0)-b(-cy_0)=c$.
So, $x_1=c x_0, y_1=-c y_0$ is a solution of $ax-by=c$.
But is it possible that $y_1$ is a solution?Isn't it negative?

Then,using the theorem:
Let $a,b$ not both $0$.If $d:=(a,b) \mid c$ and $a=da_1, b=db_1$ and if $x_1,y_1$ is a solution of the diophantine equation $ax+by=c$,then the solutions of $ax+by=c$ are given from $x=x_1+kb_1 , y=y_1-ka_1, k \in \mathbb{Z}$

we get : $x=cx_0+kb$ and $y=-cy_0-ka, k \in \mathbb{Z}$ but this solution does not satisfy the diophantine equation $ax-by=c$,right?
So,is something wrong??

I saw the solution in my notes and there they take $y=-cy_0+ka$ and this satisfy the diophantine equation..But why do we take this one? (Thinking)

 

[I like Serena]

Hi!
I am looking at the following exercise:
Let $a,b>0, (a,b)=1$.Prove that the diophantine equation $ax-by=c$ has infinitely many solutions with $x,y>0$.

As $(a,b)=1$ $\exists x_0,y_0$ such that $ax_0+by_0=1$, so $a(cx_0)-b(-cy_0)=c$.
So, $x_1=c x_0, y_1=-c y_0$ is a solution of $ax-by=c$.
But is it possible that $y_1$ is a solution?Isn't it negative?

Then,using the theorem:
Let $a,b$ not both $0$.If $d:=(a,b) \mid c$ and $a=da_1, b=db_1$ and if $x_1,y_1$ is a solution of the diophantine equation $ax+by=c$,then the solutions of $ax+by=c$ are given from $x=x_1+kb_1 , y=y_1-ka_1, k \in \mathbb{Z}$

we get : $x=cx_0+kb$ and $y=-cy_0-ka, k \in \mathbb{Z}$ but this solution does not satisfy the diophantine equation $ax-by=c$,right?
So,is something wrong??

I saw the solution in my notes and there they take $y=-cy_0+ka$ and this satisfy the diophantine equation..But why do we take this one? (Thinking)

Hey!

The general solution of
$$ax+by=1, \quad (a,b)=1$$
is $x=x_0-kb, y=y_0+ka$ with $k \in \mathbb Z$.

That is the reason why they take $y=-cy_0+ka$ in the respective equation.

From there you need to figure out which ones - and how many - are actually positive...

 

[evinda]

Hey!

The general solution of
$$ax+by=1, \quad (a,b)=1$$
is $x=x_0-kb, y=y_0+ka$ with $k \in \mathbb Z$.

That is the reason why they take $y=-cy_0+ka$ in the respective equation.

From there you need to figure out which ones - and how many - are actually positive...

But,in the notes of my prof,it is $x=x_1+kb_1 \text{ and } y=y_1-ka_1$..So,is it wrong?? (Thinking)
Also,neither the solution $x=x_0-kb, y=y_0+ka$ does satisfy the diophantine equation..or am I wrong??

 

[I like Serena]

But,in the notes of my prof,it is $x=x_1+kb_1 \text{ and } y=y_1-ka_1$..So,is it wrong?? (Thinking)

That's the same thing! (Nod)
With $k \in \mathbb Z$ we are free to replace $k$ with a $k'=-k$ which effectively swaps the signs.

Also,neither the solution $x=x_0-kb, y=y_0+ka$ does satisfy the diophantine equation..or am I wrong??

How so?
The solution does satisfy the equation.
The problem is the additional condition that $x, y > 0$.

 

[evinda]

That's the same thing! (Nod)
With $k \in \mathbb Z$ we are free to replace $k$ with a $k'=-k$ which effectively swaps the signs.

I understand. :)

How so?
The solution does satisfy the equation.
The problem is the additional condition that $x, y > 0$.

Replacing $x=cx_0-kb, y=-cy_0+ka$ I find:
$ax-by=a(cx_0-kb)-b(-cy_0+ka)=acx_0-akb+bcy_0-bka=c-2kba$..

That is not equal to $c$.So,have I done something wrong? (Thinking)

 

[I like Serena]

I understand. :)

Good! (Yes)

Replacing $x=cx_0-kb, y=-cy_0+ka$ I find:
$ax-by=a(cx_0-kb)-b(-cy_0+ka)=acx_0-akb+bcy_0-bka=c-2kba$..

That is not equal to $c$.So,have I done something wrong? (Thinking)

That should be $x=cx_0-kb, y=-(cy_0+ka)=-cy_0-ka$...

 

[evinda]

That should be $x=cx_0-kb, y=-(cy_0+ka)=-cy_0-ka$...

But,if we take $k'=-k$,shouldn't it be $x=cx_0$-$k'b$ and $y=-cy_0$+$k'a$ ,according to the theorem?

 

[I like Serena]

But,if we take $k'=-k$,shouldn't it be $x=cx_0$-$k'b$ and $y=-cy_0$+$k'a$ ,according to the theorem?

We've been juggling plus and minus signs.
Perhaps start over from the beginning?

 

[evinda]

We've been juggling plus and minus signs.
Perhaps start over from the beginning?

We take $x=cx_0-kb, y=-cy_0+ka$ with $k \in \mathbb Z$,right?
So,we get $ax-by=a(cx_0-kb)-b(-cy_0+ka)=acx_0-kab+bcy_0-bka=c-2kab$

Or am I wrong? (Blush)

 

[I like Serena]

We take $x=cx_0-kb, y=-cy_0+ka$ with $k \in \mathbb Z$,right?
So,we get $ax-by=a(cx_0-kb)-b(-cy_0+ka)=acx_0-kab+bcy_0-bka=c-2kab$

Or am I wrong? (Blush)

I'm going a little bit more back to the beginning...

We want to solve:
$$ax-by=c, \quad (a,b)=1, \quad x,y>0 \qquad \qquad (1)$$

Now suppose the solution of:
$$ax' + by' = 1$$
is $x'=x_0-kb, y'=y_0+ka$ with $x', y', k \in \mathbb Z$.

Then we can try:
$$x = cx', y = -cy'$$
The catch is that x and y both have to be positive.

So:
$$x = c(x_0-kb), y = -c(y_0+ka)$$

Substituting in (1) gives:
$$ac(x_0-kb) - b \cdot -c(y_0+ka) = c(ax_0 + by_0) -abck + abck = c\cdot 1 = c$$Now how can we make sure we get infinite positive solutions for x and y?

 

[DavidCampen]

Hi!
I am looking at the following exercise:
Let $a,b>0, (a,b)=1$.Prove that the diophantine equation $ax-by=c$ has infinitely many solutions with $x,y>0$.
(Thinking)

I do not see a constraint preventing either a or b from being 1. If we let a=1 then the constraints on a,b are satisfied: a,b > 0 and (a,b)=1. Then the equation can be written as x=by+c.

By the Division Algorithm (Theorem 2 in "Elementary Number Theory", 2nd Ed, Dudley) we have given positive integers a and b, b not = 0 there exist unique integers q and r, with 0<=r<b such that a = bq + r

So by the Division Algorithm we know that the equation x=by+c has an integer solution for all integer x. Since we know that there are infinitely many positive integers we thus know that the equation x=by+c has infinitely many integer solutions.

 

[Nono713]

I do not see a constraint preventing either a or b from being 1. If we let a=1 then the constraints on a,b are satisfied: a,b > 0 and (a,b)=1. Then the equation can be written as x=by+c.

By the Division Algorithm (Theorem 2 in "Elementary Number Theory", 2nd Ed, Dudley) we have given positive integers a and b, b not = 0 there exist unique integers q and r, with 0<=r<b such that a = bq + r

So by the Division Algorithm we know that the equation x=by+c has an integer solution for all integer x. Since we know that there are infinitely many integers we thus know that the equation x=by+c has infinitely many integer solutions.

$(a, b) = 1$ doesn't mean that either $a$ or $b$ is one, it means they are coprime. So it has to be shown to be true for any two coprime integers, not just in the case where $a$ or $b$ are one ;D

 

[DavidCampen]

$(a, b) = 1$ doesn't mean that either $a$ or $b$ is one

(a,b)=1 means that the greatest common divisor of a and b is 1. I know that it does not _require_ that either a or b be 1 but it allows for that.

I show that when either a or b is 1 then all of the constraints are satisfied and there are infinitely many solutions. It is possible that neither a or b is 1 but still there are infinitely many solutions because I have shown that the special case where a is 1 has infinitely many solutions.

Do you mean to change the problem constraint to (a,b)>1?