Homework Help: Basic number theory

1. Mar 26, 2013

EulerRules

If a and b are relatively prime natural numbers, how many numbers cannot be written on the form xa+yb where x and y are nonnegative integers?

My thoughts:
Let n be a fixed integer such that$n=ax_{0}+by_{0}$. Assume that we want to minimize $x_{0}$ but keep it nonnegative. Then the following must be true:
$0 \leq x_{0} \leq b-1$
If n cannot be expressed where both x0 and y0 are positive (I am trying to get at the maximum number which cannot be expressed on above form), then the following must be true as well
$y_{0} \leq -1$
and
$ax_{0}>n$
Since y0 is negative, the following holds true:
$ax_{0}-b \geq n$
And since $x_{0}\leq b-1$
$a(b-1)-b \geq n \rightarrow ab-a-b \geq n$
The largest number that cannot be written on above form is ab-a-b. How do I determine what numbers between 1 and ab-a-b that cannot be written on the form?

IF you have any other ideas on how to solve this problem, please share them with me. But do keep in mind that I'm only a junior in high school so I may not be familiar with more "advanced" methods.

2. May 8, 2015

geoffrey159

Since $a$ and $b$ are relatively prime, you can find $(u,v)\in \mathbb{Z}^2$ such that $1 = a u + bv$ (Bezout theorem).
You must have $a (x -u(ax+by) ) = b (v(ax+by) - y)$.
Using again that $\text{gcd}(a,b) = 1$, $a$ divides $(v(ax+by) - y)$ and $b$ devides $(x -u(ax+by) )$. Solving that will give you the set of solutions in $\mathbb{Z}^2$ for $(x,y)$ depending on $a,b,u,v$ and some factors $k,k'$.

3. May 9, 2015

Staff: Mentor

geoffrey159, you replied to a post two years old. The poster hasn't logged in to PF since that time.

4. May 9, 2015

geoffrey159

Sorry, I won't do it anymore