1
$\begingroup$

Suppose we are given an equation in $ax+(a + 1)y=c$

Now we have to find for how many values of $c$ where $c \in [1,\infty)$ will have no positive integral solution.

I'm new to diophantine equation, so I can't think of any approach. But can it be found mathematically?

Till now my approach is based on programming/brute force

I'm using a small function to check for all possible values.

void bruteforce(int a, int b, int n) 
{ 
    for (int i = 0; i * a <= n; i++) { 

        if ((n - (i * a)) % b == 0) { 
              if((i)>0 && ((n - (i * a)) / b)>0){
                 cout << "x = " << i << ", y = " << ; 
              }
            return; 
        } 
    } 

    cout << "Not Possible"; 
} 

But how can i find it more mathematically?

Example -

$3x+4y$ This equation won't have any positive integer solution for $c∈\{1,2,5\}$

$4x+5y$ this equation won't have any positive integer solution for $c ∈ \{1,2,3,6,7,11\}$ so answer would be $6$

So answer comes as $^3C_2$ in first case and $^4C_2$ in second.

$\endgroup$
9
  • $\begingroup$ Show us your attempts $\endgroup$ – Michael Rozenberg Jun 9 '19 at 5:20
  • $\begingroup$ See math.stackexchange.com/questions/880744/… $\endgroup$ – nmasanta Jun 9 '19 at 5:31
  • $\begingroup$ I've added my attempt. Also the question is for how many values of $c$ there won't be any positive integer solution. $\endgroup$ – user680738 Jun 9 '19 at 5:39
  • $\begingroup$ there are infinite numbers of such $c$ for example any prime numbers $p>\gcd(a,b).$ $\endgroup$ – Leox Jun 9 '19 at 5:54
  • $\begingroup$ Sorry i forgot to add one more point. It's given that $b= a+1$, i.e $a$ and $b$ are consecutive, from my brute force method i find the answer to be coming as aC2 $\endgroup$ – user680738 Jun 9 '19 at 6:14
1
$\begingroup$

The condition for the existence of integral solutions to $ax + by = c$ is $gcd(a, b) \; | \ c$. As the set $\mathbb{N}$ is infinite so we can always find infinite numbers which aren't multiples of $gcd(a, b)$.

$\endgroup$
2
  • $\begingroup$ With the latest edit, $\gcd(a,b)=\gcd(a,a+1)=1$ $\endgroup$ – Shubham Johri Jun 9 '19 at 6:43
  • $\begingroup$ Yes the GCD of consecutive number is 1, please look at the example which i added. There are some values of c such that the equation won't have any positive integer solution like 3x+4y=5 $\endgroup$ – user680738 Jun 9 '19 at 6:58
0
$\begingroup$

My approach solves the equation over the integers, then tries to find a positive solution :

$x=-c$ and $y=c$ is a solution.

as $gcd(a,b)=1$, and $ab-ba=0$, all solutions to the inital equation are of the form $(-c-kb,c+ka)$ for an integer $k$.

assuming $a$ positive, both $x$ and $y$ are positive iff:

$$ \dfrac{-c}{a}< k <\dfrac{-c}{a+1} $$

So a positive solution exists iff there is an integer between $\dfrac{c}{a+1}$ and $\dfrac{c}{a}$

I think your examples allow non-negative solutions (eg $4x+5y=5$ works for $x=0$ and $y=1$), but you might live (like myself) in a country where positive means $\geq 0$ (then change the $<$'s in my solution by $\leq$'s).

$\endgroup$
0
$\begingroup$

The equation is

$$ax+(a+1)y=a(x+y)+y=az+y=c$$ where $z\ge2,y\ge1$.

Assuming $a\ge0$, There are solutions for all $c\ge2a+1$.

$\endgroup$
0
$\begingroup$

If $x \ge 1$ and $y \ge 1$, then $c = ax+(a + 1)y \ge a(1)+(a+1)(1) = 2a+1$ Why does your program include $x=0$ and $y=0$ since $0$ is not a positive integer?

$\endgroup$

Your Answer

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