邮资问题

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

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

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

1. 首先由裴蜀定理知，gcd(𝑎,𝑏)∣𝑚．也就是说，如果gcd(𝑎,𝑏)≠1，那么有无数个自然数𝑚不能被gcd(𝑎,𝑏)整除，此时𝑎𝑥+𝑏𝑦=𝑚均无自然数解．于是必有gcd(𝑎,𝑏)=1．

2. 证明如下结论：𝑚≥𝑎𝑏时，𝑎𝑥+𝑏𝑦=𝑚一定有自然数解．
   证明： 由gcd(𝑎,𝑏)=1知，𝑚，𝑚−𝑎，𝑚−2𝑎，⋯，𝑚−(𝑏−1)𝑎构成一个模𝑏的完全剩余系（即模𝑏两两不相等）．于是其中必有一个为𝑏的倍数，设为𝑚−𝑥⋅𝑎（0≤𝑥≤𝑏−1且𝑥为整数），再设𝑚−𝑎𝑥=𝑏𝑦，由整除知𝑦也为整数，只需证𝑦≥0．事实上，𝑏𝑦=𝑚−𝑎𝑥≥𝑎𝑏−𝑎(𝑏−1)=𝑎>0，故𝑏>0，证毕．

3. 证明如下结论：0≤𝑚<𝑎𝑏时，𝑎𝑥+𝑏𝑦=𝑚至多只有一组自然数解．
   证明： 否则，假设存在(𝑥_(1),𝑦_(1))，(𝑥_(2),𝑦_(2))，使得𝑎𝑥_(1)+𝑏𝑦_(1)=𝑎𝑥_(2)+𝑏𝑦_(2)=𝑚，即𝑎(𝑥_(1)−𝑎_(2))=𝑏(𝑦_(1)−𝑦_(2))．于是𝑎∣𝑏(𝑦_(1)−𝑦_(2))，又gcd(𝑎,𝑏)=1，故𝑎∣𝑦_(1)−𝑦_(2)．由𝑏𝑦≤𝑚<𝑎𝑏得𝑦<𝑎，即0≤𝑦_(1),𝑦_(2)<𝑎，于是|𝑦_(1)−𝑦_(2)|≤𝑎−1，只能有𝑦_(1)−𝑦_(2)=0，即𝑦_(1)=𝑦_(2)．同理𝑥_(1)=𝑥_(2)，因此𝑎𝑥+𝑏𝑦=𝑚至多只有一组自然数解．

4. 由上知，0≤𝑚<𝑎𝑏时，能取得的𝑚和满足0≤𝑎𝑥+𝑏𝑦<𝑎𝑏的自然数组(𝑥,𝑦)一一对应，故只需求三角形区域⎧⎩⎨⎪⎪0≤𝑎𝑥+𝑏𝑦<𝑎𝑏;𝑥≥0;𝑦≥0;内的整点个数．它的两倍等于矩形区域{0≤𝑥≤𝑏;0≤𝑦≤𝑎;内的整点个数减去其中在直线𝑎𝑥+𝑏𝑦=𝑎𝑏上的整点个数（只有(𝑏,0)和(0,𝑎)两个）．如图所示：于是不能取得的𝑚有公式：ab-\dfrac{(a+1)(b+1)-2}{2}=\dfrac{(a-1)(b-1)}{2}个．

5. 令((𝑎−1)(𝑏−1))/(2)=35，得{𝑎−1=70;𝑏−1=1;或{𝑎−1=35;𝑏−1=2;或{𝑎−1=14;𝑏−1=5;或{𝑎−1=10;𝑏−1=7;．排除gcd(𝑎,𝑏)≠1的情况可得：𝑎=71，𝑏=2或𝑎=11，𝑏=8．其中第二组解即为本题第一问．

上题证明了𝑚≥𝑎𝑏时，𝑎𝑥+𝑏𝑦=𝑚一定有自然数解．事实上，𝑎𝑏并不是一个最佳值．我们有如下结论：

例2． 𝑎和𝑏为正整数，且gcd(𝑎,𝑏)=1．试证：当𝑚>𝑎𝑏−𝑎−𝑏时，二元一次不定方程𝑎𝑥+𝑏𝑦=𝑚有自然数解；𝑚=𝑎𝑏−𝑎−𝑏时，则不然．

证明： 首先，证方程𝑎𝑥+𝑏𝑦=𝑚当𝑚>𝑎𝑏−𝑎−𝑏时有非负整数解．

方程的一切整数解为

取整数𝑡，使0≤𝑦=𝑦_(0)−𝑎𝑡<𝑎（这样的𝑡一定存在，因为𝑎𝑡≤𝑦_(0)<(𝑎+1)𝑡），即0≤𝑦=𝑦_(0)−𝑎𝑡≤𝑎−1．对此𝑡，将相应的𝑥代入𝑎𝑥+𝑏𝑦=𝑚中，有

公式：\begin{align*} ax=&a\left(x_{0}+b t\right)=m-b\left(y_{0}-a t\right)\\ >&a b-a-b-b(a-1)=-a． \end{align*}

而𝑎>0，故𝑥=𝑥_(0)+𝑏𝑡>−1，即𝑥≥0．这就证明了当𝑚>𝑎𝑏−𝑎−𝑏时，方程𝑎𝑥+𝑏𝑦=𝑚有自然解．

其次，证𝑚=𝑎𝑏−𝑎−𝑏时方程𝑎𝑥+𝑏𝑦=𝑚无自然数解．

若不然，即方程𝑎𝑥+𝑏𝑦=𝑚有解𝑥≥0，𝑦≥0，则由𝑎𝑥+𝑏𝑦=𝑎𝑏−𝑎−𝑏，得𝑎(𝑥+1)+𝑏(𝑦+1)=𝑎𝑏．因gcd(𝑎,𝑏)=1，故𝑎∣𝑦+1，𝑏∣𝑥+1，从而𝑦+1≥𝑎，𝑥+1≥𝑏．从而𝑎𝑏=𝑎(𝑥+1)+𝑏(𝑦+1)≥2𝑎𝑏．这和𝑎，𝑏为正整数矛盾，所以结论成立．

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

例3． 设𝑎，𝑏，𝑐是正整数，gcd(𝑎,𝑏,𝑐)=1，又设gcd(𝑎,𝑏)=𝑑．证明：当𝑛>(𝑎𝑏)/(𝑑)+𝑐𝑑−𝑎−𝑏−𝑐时，方程𝑎𝑥+𝑏𝑦+𝑐𝑧=𝑛有自然数解．

更一般的情况如下题：

例4． 设𝑝_(1)，𝑝_(2)，⋯，𝑝_(𝑛)是 𝑛(≥2)个两两互素的正整数，记𝜋_(𝑖)=(𝑝_(1)𝑝_(2)⋯𝑝_(𝑛))/(𝑝_(𝑖))，𝑖=1,2,⋯,𝑛．求最大的正整数𝑚，使得不定方程

𝜋_(1)𝑥_(1)+𝜋_(2)𝑥_(2)+⋯+𝜋_(𝑛)𝑥_(𝑛)=𝑚

没有非负整数解．

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