1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Jorge Fernández Hidalgo Mar 26 '16 at 5:11
  • $\begingroup$ 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. $\endgroup$ – Théophile Mar 26 '16 at 5:15
  • $\begingroup$ @TheKindCat Why so? For which problem should I do it? $\endgroup$ – TheRandomGuy Mar 26 '16 at 5:16
  • $\begingroup$ In this @Théophile? $$ab -a -b = a \cdot (b-1) + b \cdot -1$$ It is clear. You see $y_0 = -1$ is negative. $\endgroup$ – TheRandomGuy Mar 26 '16 at 5:17
  • $\begingroup$ @Dhruv for both. $\endgroup$ – Jorge Fernández Hidalgo Mar 26 '16 at 5:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great Proof! Thanks! $\endgroup$ – TheRandomGuy Mar 26 '16 at 16:40
  • $\begingroup$ Just another question. What would the tight representation be in case we argue for $ax + by + cz$? $\endgroup$ – TheRandomGuy Mar 26 '16 at 16:43
  • $\begingroup$ I mean, how would we choose non-negative $x$,$y$ and $z$? $\endgroup$ – TheRandomGuy Mar 26 '16 at 16:49
  • $\begingroup$ I'm not sure, I guess we would have to pick a definition depending on what we want to prove. $\endgroup$ – Jorge Fernández Hidalgo Mar 26 '16 at 17:04
  • $\begingroup$ 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? $\endgroup$ – TheRandomGuy Mar 26 '16 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.