# Given an integer $n$ and relatively prime positive integer $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$

Given an integer $n$ and relatively prime positive integers $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$ for some non-negative integers $x$ and $y$. Also show that $ab-a-b$ is the largest integer that cannot be expressed in such a form.

I tried this approach for the second problem.

$$ab -a -b = a \cdot (b-1) + b \cdot -1$$

We find that it can be expressed in the form $ax_0 + by_0$ but $y_0$ is negative so this isn't true. Now they can also be expressed in the form

$$ab -a -b = a \cdot (b-1) + b \cdot -1 + ab - ab = a\cdot -1 + b \cdot (-1 + a)$$

So in any case, one of $x_0$ or $y_0$ remains negative and hence it cannot be expressed in such a form.

Now I feel that I can use the proof of the second problem to prove the first problem.

You see, if $n = ax_0 + by_0$ then if $ab - a -b-n$ can be expressed in such a form then $ab-a-b$ can also be. But we have now proved that $ab-a-b$ cannot be expressed thus $ab -a -b-n$ can not be expressed in such a form. This is the proof if $n = ax_0 + by_0$. What if $n \neq ax_0 + by_0$?

How do I proceed with this proof? Is my proof of the second problem correct?

• Hint: prove for any integer there is only one way to express it as $xa+yb$, with $x\in\{0,1,2,3\dots b-1\}$ and $y\in \mathbb Z$. – Jorge Fernández Hidalgo Mar 26 '16 at 5:11
• At the beginning of your approach, you have found two expressions $ax_0+by_0$ where either $x_0$ or $y_0$ is negative. But these two examples do not show that $x_0$ or $y_0$ must be negative. You have not proved the second problem. – Théophile Mar 26 '16 at 5:15
• @TheKindCat Why so? For which problem should I do it? – TheRandomGuy Mar 26 '16 at 5:16
• In this @Théophile? $$ab -a -b = a \cdot (b-1) + b \cdot -1$$ It is clear. You see $y_0 = -1$ is negative. – TheRandomGuy Mar 26 '16 at 5:17
• @Dhruv for both. – Jorge Fernández Hidalgo Mar 26 '16 at 5:19

Lemma $1$: Given $a$ and $b$ coprime and $n$ any integer there is exactly one way to express $n$ as $ax+by$ with $x\in\{0,1,2\dots b-1\}$ and $y\in\mathbb Z$. We call this representation of $n$ its tight representation.

Proof: By Bezout's theorem there is $s$ and $t$ so that $as+bt=1$. So taking $s'=ns$ and $t'=nt$ we have $as'+bt'=n$. Consider the set $A=\{(x,y) | ax+by=n\}$, we know $(s,t)\in A$. Clearly $(s-b,t+a)$ and $(s+b,t-a)$ are also in $A$. Because of this we can always find a pair $(x,y)\in A$ with $x\in\{0,1,2,\dots,b-1\},y\in\mathbb Z$.

To show uniqueness, suppose $ax+by=n$ and $ax'+by'=n$. Then $a(x-x')+b(y-y')=0$, if $x\neq x'$ then $(x-x')$ is not a multiple of $b$, so $a(x-x')$ is not a multiple of $b$, and $a(x-x')+b(y-y)'$ is not a multiple of $b$, a contradiction, an analogous argument shows $y=y'$.

Lemma $2$: An integer $n$ can be expressed as $sa+tb$ with $s,t$ non negative if and only if the coefficients in its tight representation are non negative.

Proof: Consider the set $B$ of integer pairs $(s,t)$ so that $s$ is non-negative and $sa+tb=n$. Clearly, the pair $A$ in which $t$ is the largest is also the pair in which $s$ is the smallest, this pair is precisely the tight representation. So if $y$ is negative in the tight representation, then for every pair $(s,t)\in B$ we have $t$ negative.

Problem $1$: Exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$.

Proof: Let the tight representation of $n$ be $xa+yb$.

Notice $ab-a-b=(b-1)a+(-1)(b)$, so $ab-a-b-n=(b-1-x)a+(-1-y)b$.

So the tight representation of $ab-a-b-n$ is $(b-1-x)a+(-1-y)b$. Clearly exactly one of $y$ and $-1-y$ is non-negative. This finishes the proof.

Problem $2$: The largest integer not expressible in this form is $ab-a-b$. (also known as the chicken McNugget theorem or the frobenius coin problem)

Proof: What can the tight representation of this integer be? Let it be $xa+yb$. Then $x$ is at most $b-1$ and $y$ is at most $-1$ (since it must be negative, so the number is not expressible in this form. We conclude the number is at most $(b-1)a+(-1)b=ab-a-b$.

• Great Proof! Thanks! – TheRandomGuy Mar 26 '16 at 16:40
• Just another question. What would the tight representation be in case we argue for $ax + by + cz$? – TheRandomGuy Mar 26 '16 at 16:43
• I mean, how would we choose non-negative $x$,$y$ and $z$? – TheRandomGuy Mar 26 '16 at 16:49
• I'm not sure, I guess we would have to pick a definition depending on what we want to prove. – Jorge Fernández Hidalgo Mar 26 '16 at 17:04
• Let $a,b,c$ be pairwise relatively prime positive integers. Show that $2abc − ab − bc − ca$ is the largest integer that cannot be expressed in the form $xbc + yca + zab$, where $x,y,z$ are nonnegative integers. This. Hints? – TheRandomGuy Mar 26 '16 at 17:06