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

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.

• Show us your attempts – Michael Rozenberg Jun 9 '19 at 5:20
• – nmasanta Jun 9 '19 at 5:31
• I've added my attempt. Also the question is for how many values of $c$ there won't be any positive integer solution. – user680738 Jun 9 '19 at 5:39
• there are infinite numbers of such $c$ for example any prime numbers $p>\gcd(a,b).$ – Leox Jun 9 '19 at 5:54
• 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 – user680738 Jun 9 '19 at 6:14

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

• With the latest edit, $\gcd(a,b)=\gcd(a,a+1)=1$ – Shubham Johri Jun 9 '19 at 6:43
• 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 – user680738 Jun 9 '19 at 6:58

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

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

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?