Let $a$ and $b$ same sign, $a,b\in \mathbb{Z}$ and $n\in\mathbb{N}$. Prove that $\exists c$ that the equation $ax+by=c$ has exactly n different positive solutions, it means $(x,y)$, where $x>0$ and $y>0$.

I have to use theorem:

Let $a,b,c\in\mathbb{Z}$. If at least one of the numbers $a$ and $b$ is not $0$ and $x_0, y_0$ is the equation $ax+by=c$ some solution, then all solutions $x,y$ of this equation is obtained by means of formulas $x=x_0+\frac{b}{gcd(a,b)}t$,
$y=y_0-\frac{a}{gcd(a,b)}t$, giving all integer values to the variable $t$.

First find a solution $x_0,y_0$ and then suitable $c$ value.

How to prove it?

Thank You.

  • $\begingroup$ W.L.O.G we may assume that both $a,b\ge 0$. Then for $n=0$ we can take any $c<0$, so that $ax+by=c$ has exactly $0$ different positive solutions. So the claim is even true for $n=0$. $\endgroup$ – Dietrich Burde Feb 27 '18 at 12:35

Let $d=\gcd(a,b)$ and $a'=a/d$, $b'=b/d$. Then

  • $x = x_0 + b't >0$ iff $t > -x_0/b'$

  • $y = y_0 - a't <0$ iff $t < y_0/a'$.

So, $t \in (-x_0/b', y_0/a')$. The length of this interval is $$ \frac{y_0}{a'}+\frac{x_0}{b'}=\frac{a'x_0+b'y_0}{a'b'}=\frac{c}{a'b'd}=\frac{c}{m} $$ where $m=lcm(a,b)$. Take $c=nm$ and the interval will have length $n$ and so $n$ integers inside it in general. If one or both extremes are integers, you'll have to compensate.


$a x+b y =c$

1- We find gcd of a and b: gcd(a, b)

2- the condition for existence of solution is that : $gcd(a, b) | c$

3- we find the solutions of homogeneous equation $(ax+by=0)$; in case a and b are co-primes then $gcd(a, b)=1$ and we have:

$a x+b y = 0$:

$x= b$ and $y=-a$

So general solutions of homogeneous equation is:

$x = b . t$

$y = -a . t$

Where t can be any arbitrary value in Z. If we sum these solutions with a couple of certain solutions $x_0$,and $y_0$ then we find general solutions of equation $a x+b y =c$ ; we have:

$x = b.t + x_0$

$y = -a.t + y_0$

Hence this equation has infinitely many solutions in Z in general and in N in particular.The values of $x_0$ and $y_0$ depends on the value of c, therefore for n different c there can be n different sets of positive solutions.

Note that if a and b are co primes then their common divisor is $1$.

Geometric interpretation: Equation $ax +by=c$ in fact represent a line which is the locus of infinitely many points, among them many have coordinates in Z in general and in N in particular. With certain values of a and b , which define the slope of the lines c can have various values; each value gives a line parallel to others so that if we have n different c we will have n different equation or line with the same slope, hence we have exactly n solutions(or n lines) for the equation in each there exist many points having coordinates in N.So with n different c we have n different set of point having positive coordinates. c can be any arbitrary integer. in other words multiplying both sides of equation by a common divisor like $d$ we get a new equation( a new line).In this way all equations satisfy the condition that $gcd(ad, bd)=d|cd=c_1$ where $c_1$ is the new c.

  • $\begingroup$ Where do we see that there are, for any given $n$, exactly $n$ different positive solutions? $\endgroup$ – Dietrich Burde Feb 27 '18 at 12:37
  • $\begingroup$ @Anette Uiga please see my edited answer. $\endgroup$ – sirous Feb 27 '18 at 15:42
  • $\begingroup$ @DietrichBurde, for any given n there exists infinitely many positive solutions(not n solutions).So for any given n there are exactly n different sets of positive solutions. $\endgroup$ – sirous Feb 28 '18 at 3:19
  • $\begingroup$ Infinitely many? Certainly not. Take $2x+4y=1$. $\endgroup$ – Dietrich Burde Feb 28 '18 at 9:21
  • $\begingroup$ @DietrichBurde, As I explained in geometric interpretation each n gives a new equation which has at least one positive solution. n can goes to infinity therefore there can be infinitely many positive solutions for this type of equation. $\endgroup$ – sirous Feb 28 '18 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.