How many $c$ for which equation $ax+(a + 1)y=c$ will have no positive integer solution?

Question

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.

Answer 1

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)$.

Answer 2

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).

Answer 3

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$.

Answer 4

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?