Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I am asked to prove that:
For integers $n, x,y > 0$, where $x,y$ are relatively prime, every $n \ge (x-1) (y-1)$ can be expressed as $xa + yb$, with nonnegative integers $a,b \ge0$.
How should I approach this? I have very limited knowledge in number theory.
We sketch a proof. For my comfort, I will use $a$ and $b$ instead of $x$ and $y$. Sorry! So we show that every $n\ge (a-1)(b-1)$ is representable in the form $au + bv$ with $u$ and $v$ being nonnegative integers.
1. Because $a$ and $b$ are relatively prime, there exist integers $x_0,y_0$ (not necessarily both $\ge 0$) such that $ax_0+by_0=1$. Thus (multiplying through by $n$) we find that there exist integers $x_1,y_1$ such that $ax_1+by_1=n$.
2. Infinitely many solutions of the equation $ax+by=n$ are given by $x=x_1-tb$, $y=y_1+ta$, where $t$ ranges over the integers. (Actually these are all solutions, but we won't need this.)
3. Let $t$ be the smallest positive integer such that $y_1+ta\ge 0$. We show that $x_1-tb\ge 0$. We have $$a(x_1-tb)+b(y_1+ta)=n \ge (a-1)(b-1),$$ thus $$a(x_1-tb) \ge (a-1)(b-1) - b(y_1+ta).$$ But $y_1+ta\le a-1$, else we could decrement $t$. Thus $$a(x_1-tb)\ge (a-1)(b-1)-b(a-1) = -(a-1) > -a,$$ and therefore $x_1-tb> -1$, so that $x_1-tb \geq 0$ (since $x_1-tb \in \mathbb{Z}$). So we have produced the required non-negative solution.
By the extended Euclidean algorithm one finds $u,v\in\mathbb Z$ with $ux+vy=1$, hence for any integer $n$ we can find a representation $n=a x+b y$ with $a,b\in\mathbb Z$. With $ax+by=n$ we also have $(a+ky)x+(b-kx)y=n$, hence there exist solutions to $n=ax+by$ with $a\ge 0$. Among all those solutions pick one that minimizes $a$. Then $0\le a\le y-1$ because otherwise $(a-y)x+(b+x)y$ would be "better". If $n\ge (x-1)(y-1)$, we find that $$by = n-ax\ge (x-1)(y-1)-(y-1)x = 1-y>-y $$ hence $b>-1$, i.e. $b\ge 0$ as required.
Key Idea $ $ In the plane $\,\mathbb R^2,\,$ a line $\rm\,a\,x+b\,y = c\,$ of negative slope has points in the first quadrant $\rm\,x,y\ge 0\ $ iff its $\rm\,y$-intercept $\rm\,(0,\,y_0)\,$ is in the first quadrant, i.e. $\,\rm y_0 \ge 0\,.$ We can use an analogous "normalized" point test to check if a discrete line $\rm\,m\,x + n\,y = k\,$ has points in the first quadrant.
Hint $\ $ Normalize $\rm\,k = m\, x + n\, y\,$ so $\rm\,0 \le x < n\,$ by adding a multiple of $\rm\,(-n,m)\,$ to $\rm\,(x,y)$
Lemma $\rm\ \ k = m\ x + n\ y\,$ for some integers $\rm\,x,\,y \ge 0\,$ $\iff$ its normalization has $\rm\,y \ge 0.$
Proof $\ (\Rightarrow)\ $ If $\rm\ x,\, y \ge 0\,$ normalizing adds $\rm\,(-n,m)\,$ zero or more times, preserving $\rm\,y \ge 0\,.\,$
$(\Leftarrow)\ \,$ If the normalized rep has $\rm\ y < 0,\,$ then $\rm\,k\,$ has no representation with $\rm\, x,\,y \ge 0\,\, $ since to shift so that $\rm\,y > 0\,$
we must add $\rm\,(-n,m)\,$ at least once, which forces $\rm\,x < 0,\,$ by $\rm\,0\le x < n.\ \ \ $ QED
To solve the OP, note that since $\rm\, k = m\ x + n\ y\, $ is increasing in both $\rm\,x\,$ and $\rm\,y,\,$ it is clear that the largest non-representable $\rm\,k\,$ has normalization $\rm\,(x,y) = (n\!-\!1,-1),\,$ i.e. the lattice point that is rightmost (max $\rm\,x$) and topmost (max $\rm\,y$) in the nonrepresentable lower half $\rm (y < 0)$ of the normalized strip, i.e. the vertical strip where $\rm\, 0\le x \le n-1.\,$ Thus $\rm\,(x,y) = (\color{#0a0}{n\!-\!1},\color{#c00}{-1})\,$ yields that $\rm\, k = mx+ny = m\,(\color{#0a0}{n\!-\!1})+n\,(\color{#c00}{-1}) = mn\! -\! m\! -\! n\ $ is the largest nonrepresentable integer. $\ $ QED
Notice that the proof has a vivid geometric picture: representations of $\rm\,k\,$ correspond to lattice points $\rm\,(x,y)\,$ on the line $\rm\, n\ y + m\ x = k\,$ with negative slope $\rm\, = -m/n\,.\,$ Normalization is achieved by shifting forward/backward along the line by integral multiples of the vector $\rm\,(-n,m)\,$ until one lands in the normal strip where $\rm\,0 \le x \le n-1.\,$ If the normalized rep has $\rm\,y\ge 0\,$ then we are done; otherwise, by the lemma, $\rm\,k\,$ has no rep with both $\rm\,x,y\ge 0\,.\,$ This result may be viewed as a discrete analog of the fact that, in the plane $\,\mathbb R^2,\,$ a line of negative slope has points in the first quadrant $\rm\,x,y\ge 0\ $ iff its $\rm\,y$-intercept $\rm\,(0,\,y_0)\,$ lies in the first quadrant, i.e. $\rm y_0 \ge 0\,.$
There is much literature on this classical problem. To locate such work you should ensure that you search on the many aliases, e.g. postage stamp problem, Sylvester/Frobenius problem, Diophantine problem of Frobenius, Frobenius conductor, money changing, coin changing, change making problems, h-basis and asymptotic bases in additive number theory, integer programming algorithms and Gomory cuts, knapsack problems and greedy algorithms, etc.
This problem is similar to the "coin problem", where you need to find the smallest integer from which every integer can be obtained with a linear combination of the values of your coins with positive coefficients.
For your problem with 2 numbers (aka 2 coin values), a solution can be found here : http://www.cut-the-knot.org/blue/Sylvester.shtml#solution
Let me show another proof of this elementary problem (in terms of $a$ and $b$ as constants and $x$, $y$ as variables).
Let $i$ be the least (non-negative) residue of $y$ modulo $a$. Then one can rewrite the form $ax+by$ as $ax+b(i+az)=bi+a(x+bz)$. Given $0 \leq i \leq a-1$, we obtain the sequence $bi+an$, $n\geq 0$, of integers, which can be represented by the form (and only elements of these sequences possess this property).
Suppose that $a$ and $b$ are coprime positive integers. It follows from the extended Euclidean algorithm that $b$ is an invertible element of $\mathbb{Z}/a\mathbb{Z}$. Therefore, the multiplication by $b$ is an automorphism of the ring $\mathbb{Z}/a\mathbb{Z}$. Thus, all $bi$'s are distinct modulo $a$, i.e. two different sequences contain no common elements.
Note that the smallest element of each of these sequence is less than or equal to $b(a-1)$, i.e. they "begin" not later than this "moment". Obviously, any integer $N \geq b(a-1)$ appears in exactly one of those sequence. Moreover, the sequence that corresponds to $b(a-1)+m$, $0<m \leq a-1$, contains $b(a-1)+m-a \geq b(a-2)$, since it begins not later than $b(a-2)$. Thus, any integer $N \geq b(a-1) + 1 - a = (a-1)(b-1)$ can be represented by the form.
It suffices to see that $ax+by=(a-1)(b-1)-1$ has no non-negative solutions.
