邮资问题

今天上课给六年级的学生讲了一道邮资问题，涉及到的知识点有裴蜀等式、完全剩余系、整点问题，这里做个简单的记录．

例1． (1)用面值分与分的邮票（不限数量），有多少种资费支付不了?
(2)用面值为，()两种邮票 (不限数量) ，有种资费支付不了，求和．

解： 直接做第二问，设面值为的有张，面值为的有张，总资费，其中和为正整数，，，为自然数．即考虑为何值时，方程无自然数解．

1. 首先由裴蜀定理知，．也就是说，如果，那么有无数个自然数不能被整除，此时均无自然数解．于是必有．

2. 证明如下结论：时，一定有自然数解．
   证明： 由知，，，，，构成一个模的完全剩余系（即模两两不相等）．于是其中必有一个为的倍数，设为（且为整数），再设，由整除知也为整数，只需证．事实上，，故，证毕．

3. 证明如下结论：时，至多只有一组自然数解．
   证明： 否则，假设存在，，使得，即．于是，又，故．由得，即，于是，只能有，即．同理，因此至多只有一组自然数解．

4. 由上知，时，能取得的和满足的自然数组一一对应，故只需求三角形区域内的整点个数．它的两倍等于矩形区域内的整点个数减去其中在直线上的整点个数（只有和两个）．如图所示：于是不能取得的有个．

5. 令，得或或或．排除的情况可得：，或，．其中第二组解即为本题第一问．

上题证明了时，一定有自然数解．事实上，并不是一个最佳值．我们有如下结论：

例2． 和为正整数，且．试证：当时，二元一次不定方程有自然数解；时，则不然．

证明： 首先，证方程当时有非负整数解．

方程的一切整数解为

取整数，使（这样的一定存在，因为），即．对此，将相应的代入中，有

而，故，即．这就证明了当时，方程有自然解．

其次，证时方程无自然数解．

若不然，即方程有解，，则由，得．因，故，，从而，．从而．这和，为正整数矛盾，所以结论成立．

对于三元一次不定方程，也有类似的结论：

例3． 设，，是正整数，，又设．证明：当时，方程有自然数解．

更一般的情况如下题：

例4． 设，，，是 个两两互素的正整数，记，．求最大的正整数，使得不定方程

没有非负整数解．

以上题目来源：《命题人讲座——初等数论》冯志刚，第四讲．