什么情况下不定方程ax+by=c没有非负整数解？

manthanein

a、b、c均为整数，且gcd(a,b)=1.

hujunhua

当c=0时，方程有(0,0)解，所以c≠0. 那么不妨假定c>0. 则方程无非负整数解的必要条件是0<a, 0<b.在此基础上再来讨论充分条件。

为了简化讨论，可以假定gcd(a, c)=gcd(b,c)=1，一般情况不难从此推导。
直线ax+by=c上的相邻整点的间距`\sqrt {a^2+b^2}`应大于直线在第一象限内的长度`\sqrt {(c/a)^2+(c/b)^2}`，由此可得 c<ab。这又是一个必要条件。

mathe

c>=ab才保证有解

对于给定的 `a,b,c` 让计算机判断方程 `ax+by=c` 是否有非负整数解还是非常高效的，只是通用的判别式$f(a,b,c)$不一定有
由于$(a,b)=1$,那么对于任意c,必然存在整数$x_c,y_c$使得$ax_c+by_c=c$,这个计算机可以通过辗转相除法计算出来
于是方程的整数解的通解形式为$a(x_c-kb)+b(y_c+ka)=c$
也就是方程存在非负整数解的充分必要条件是存在整数k使得$x_c>=kb,y_c>=-ka$同时成立
也就是要求存在整数k使得$-{y_c}/a<=k<={x_c}/b$，这个就是充分必要条件。
比如方程$7x+13y=25$是否非负解，我们先任意找到一组整数解$7*(-2)+13*3=25$,于是整数解通解形式为$7*(-2-13k)+13*(3+7k)=25$
于是要求$-3/7<=k<=-2/13$,由于不存在满足条件的整数k,所以无非负整数解

只是呼吸

a、b、c均为整数，且gcd(a,b)=1.

这个条件过于宽泛，楼主应该自己确定好 \(a、b、c\) 的符号。

hejoseph

$a$、$b$、$c$ 都为正整数时，这是二元 Frobenius 问题，结论是 $c\leq ab-a-b$。


也可以就此问题给一个特殊的证明。首先，在2#的基础上，可以进一步确定`a>1,b>1`.
因 `a=1` 时，方程有非负解 `(c, 0)`, 同样 `b=1` 时，方程有非负解 `(0, c)`. 故可排除 `a` 或者 `b=1`.

当 `c=ab-a-b` 时，方程有两个相邻解 `(b-1, -1), (-1, a-1)`, 这两解正好跨越第1象限，故方程无非负解。
剩下只要证明当 `c>ab-a-b` 时，方程有非负解。
即 `r>0` 时方程\[ax+by=ab-a-b+r\]有非负解。
证：在`\gcd(a,b)=1`时，方程 `ax+by=r` 存在解 `(0<x_r\le b, -a<y_r)`. 将 `r=ax_r+by_r` 代入上面的方程即\[ax+by=ab-a-b+ax_r+by_r\]它显然有非负解`(x_r-1,a+y_r-1)`。证毕

gxqcn

楼主问题等价于问何时“不定方程 \(ax+by=c+a+b\) 没有正整数解”，将\(c+a+b\)代换为`c`, 根据楼上结论当有`c≤ab`

只是呼吸

多年前，我对这个问题是有兴趣的，有自己的心得体会。manthanein给的题目条件可以用“几乎没有”来形容。
我可以这样答：
        当 \(a<0，b<0 ，c>0 \)  时，程 \(ax+by=c\)  没有非负整数解