《怎样解题:数学竞赛攻关宝典(第3版)》第 36 页:

题2.2.19 湾区快餐店出售炸鸡块,并将这些鸡块打包出售, 一包中包含 7 块或 11 块鸡块。 求最大正整数 n, 使得你无论鸡块包怎么组合都不能恰好得到 n 块炸鸡块。 你能将此推广吗?


此题等价于:令 x 和 y 是非负整数,z = 7x + 11y 不能表达的最大正整数是多少?我们有:

  • 7·(-3) + 11·2 = 1
  • 7·8 + 11·(-5) = 1

第一个等式是利用扩展欧几里得算法在线计算器计算出来的。第二个等式是利用:

  • 7x + 11y = 7(x+11) + 11(y-7)

因此:

易知,本题的答案是 59。


本题的一种推广是假设一包中包含 a 块或 b 块鸡块,其中 a 和 b 互素。

例如,假设 a = 5, b = 21,则:

  • 5·(-4) + 21·1 = 1
  • 5·17 + 21·(-4) = 1

因此:

易知答案是 79。


例如,假设 a = 105, b = 2048,则:

  • 105·(-39) + 2048·2 = 1
  • 105·2009 + 2048·(-103) = 1

因此:

易知答案是 212887。


根据小学徒的评论,从 The Frobenius Coin Problem Upper Bounds on The Frobenius Number 可知,有以下定理:

给定大于 1 的互素的整数 a 和 b,令 x 和 y 是非负整数,则 ax + by 不能表达的最大正整数是 ab - a - b。