Question

整系数二元一次不定方程有非负解的充分条件

Answer 1

这个问题的研究、证明过程非常有意思，一些关于整数部分、小数部分的小推理并不仅在这里会用到，所以整理一下. 方括号表示整数部分，花括号表示小数部分.

先给出一些可能用到的引理.

考虑 的两种表示即可.

分两种情况讨论即可：1. 不进位；2. 进一位.

对 带余除法即可.

有了这些引理，我们可以证明：

.

保证了方程有解. 假设一组特解为 ，那么方程的通解可以表示为 . 令它们非负，得到：

                                   

因此非负解有 组，由引理1，得：

                   

由引理2，得：

                               

注意到 是方程的解，所以 也可以改写为：

                                               

当 时，一方面可以直接得到 ，另一方面，代入特解可以得到：

                       

                                                               

由 得： ，此即 ，这意味着方程有非负解.

不难发现，研究该问题涉及到的式子大多是取整. 考虑对象限定为整数的时候，一些估算就变得容易许多. 并且可以看到，带余除法在初等数论里随处可见.