Diophantine equation ax-by=c has infinitely many solutions

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the Diophantine equation \( ax - by = c \) where \( a, b > 0 \) and \( (a, b) = 1 \). Participants are exploring whether this equation has infinitely many positive integer solutions for \( x \) and \( y \). The conversation includes attempts to derive general solutions and clarify conditions under which solutions remain positive.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants propose that since \( (a, b) = 1 \), there exist integers \( x_0, y_0 \) such that \( ax_0 + by_0 = 1 \), leading to a potential solution for \( ax - by = c \).
  • Others question the validity of negative solutions derived from the general form, particularly whether \( y_1 = -cy_0 \) can be considered a valid solution.
  • A later reply suggests that the general solution for \( ax + by = 1 \) can be expressed as \( x = x_0 - kb \) and \( y = y_0 + ka \), prompting further discussion on how to adapt this for the equation \( ax - by = c \).
  • Some participants express confusion over the signs in the solutions and whether they satisfy the original equation, particularly under the constraint that \( x, y > 0 \).
  • One participant introduces the Division Algorithm to argue that if \( a = 1 \), the equation simplifies to \( x = by + c \), suggesting that this case leads to infinitely many solutions.
  • Another participant clarifies that \( (a, b) = 1 \) does not imply either \( a \) or \( b \) must be 1, but rather that they are coprime integers.

Areas of Agreement / Disagreement

Participants express differing views on the validity of certain solutions and the conditions required for \( x \) and \( y \) to remain positive. There is no consensus on the best approach to derive the infinite solutions, and multiple competing methods are discussed.

Contextual Notes

Participants note that the additional condition of \( x, y > 0 \) complicates the solutions derived from the general forms. There is also uncertainty regarding the implications of the Division Algorithm in this context.

Who May Find This Useful

This discussion may be of interest to those studying number theory, particularly in the context of Diophantine equations and their solutions. It may also benefit individuals exploring the implications of coprimality in integer equations.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hi! :cool:
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?? :confused:

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)
 
Mathematics news on Phys.org
evinda said:
Hi! :cool:
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?? :confused:

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! :o

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...
 
I like Serena said:
Hey! :o

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?? :confused:
 
evinda said:
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?? :confused:

How so?
The solution does satisfy the equation.
The problem is the additional condition that $x, y > 0$.
 
I like Serena said:
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. :)
I like Serena said:
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? :confused:(Thinking)
 
evinda said:
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? :confused:(Thinking)

That should be $x=cx_0-kb, y=-(cy_0+ka)=-cy_0-ka$...
 
I like Serena said:
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? :confused:
 
evinda said:
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? :confused:

We've been juggling plus and minus signs.
Perhaps start over from the beginning?
 
I like Serena said:
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) :confused:
 
  • #10
evinda said:
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) :confused:

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?
 
  • #11
evinda said:
Hi! :cool:
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.
 
Last edited:
  • #12
DavidCampen said:
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
 
  • #13
Bacterius said:
$(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?
 

Similar threads

Graduate Generalized Diophantine equation and the method of infinite descent
  • · Replies 4 ·
Replies
4
Views
1K
Graduate A global version of the implicit function theorem
  • · Replies 0 ·
Replies
0
Views
643
MHB Are the solutions of the diophantine equations right?
  • · Replies 19 ·
Replies
19
Views
6K
Undergrad Positive solution for linear Diophantine equations
  • · Replies 4 ·
Replies
4
Views
7K
MHB Would the equation have at least one solution?
  • · Replies 4 ·
Replies
4
Views
2K
Graduate Diophantine equation and squares
  • · Replies 1 ·
Replies
1
Views
1K
MHB Prove a quartic equation ax^4+bx^3+cx^2+dx+e=0 has at least one real solution
  • · Replies 2 ·
Replies
2
Views
2K
MHB Show that the diophantine equation has only these solutions
  • · Replies 1 ·
Replies
1
Views
1K
MHB Why Does Checking if 2 Divides z1 Matter in Rational Solutions for X^2+Y^2=n?
  • · Replies 3 ·
Replies
3
Views
2K
High School Line Equations: Rearranging Ax + By + C = 0 to y=mx+b
  • · Replies 4 ·
Replies
4
Views
1K