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?
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$.