5.2 Nonnegative integer combinations ofaandb 203
5.2 Nonnegative integer combinations ofaandb
Find thelargestpositive integer whichcannotas 7 x+11yfor integers
x, y≥ 0.
LetS:={ 7 x+11y:x, ynonnegative integers}. Arrange the posi-
tive integers in the form
1 8 15 22∗ 29 36 43 50 57 64 71 ...
2 9 16 23 30 37 44∗ 51 58 65 72 ...
3101724 313845 525966∗ 73 ...
411 ∗ 18 25 32 39 46 53 60 67 74 ...
512192633 ∗ 40 47 54 61 68 75 ...
6132027 34414855∗ 62 69 76 ...
7141528 354249 56637077...Observations: (i) Every number in the bottom row, being a positive
multiple of 7, is inS.
(ii) Among the first 11 columns, along each of the first 6 rows, there is
a unique entry (with asterisk) which is a multiple of 11. This entry with
asterisk, and those on its right along the row, are inS.
(iii) None of the entries on the left of an entry with asterisk is inS.
(iv) The entries with asterisks are on different columns.
(v) The rightmost entry with an asterisk is 66. From this, thelargest
integernotinSis 66 −7=59.
Theorem 5.3. Letaandbbe given relatively prime positive integers.
Every integer greater thanab−a−bcan be written asax+byfor
nonnegative integersxandy.
Proof.LetS:={ax+by:x, ynonnegative integers}.
Suppose, for a contradiction,ab−a−b=ax+by,x, y≥ 0. Then
ab=a(x+1)+b(y+1). Note thata|b(y+1). Sincegcd(a, b)=1,we
must havea|y+1. Buty+1is a positive integersmallerthana. This is
clearly a contradiction. From thisab−a−b/∈S.
Every integertin the range 0 <t<acan be written ast=au−bv
for 0 <u<band 0 ≤v<a. (Chooseu∈{ 1 , 2 ,...,b− 1 }such that
au≡t(modb). Then 0 <au−t<ab. It follows thatau−t=bv
for some 1 ≤v<a. Thus, every positive integer<a+bis of the form
au−bv, 0 <u<b, 0 ≤v<a. Suppose(a−1)(b−1)≤n<ab. Then
ab−n<a+b. Writeab−n=au−bvfor 0 <u<band 0 ≤v<a.
From this,n=a(b−u)+bv. This shows thatn∈S.