- #1
EulerRules
- 3
- 0
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[itex]n=ax_{0}+by_{0}[/itex]. Assume that we want to minimize [itex]x_{0}[/itex] but keep it nonnegative. Then the following must be true:
[itex]0 \leq x_{0} \leq b-1[/itex]
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
[itex]y_{0} \leq -1[/itex]
and
[itex]ax_{0}>n[/itex]
Since y0 is negative, the following holds true:
[itex]ax_{0}-b \geq n[/itex]
And since [itex]x_{0}\leq b-1[/itex]
[itex]a(b-1)-b \geq n \rightarrow ab-a-b \geq n[/itex]
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.
My thoughts:
Let n be a fixed integer such that[itex]n=ax_{0}+by_{0}[/itex]. Assume that we want to minimize [itex]x_{0}[/itex] but keep it nonnegative. Then the following must be true:
[itex]0 \leq x_{0} \leq b-1[/itex]
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
[itex]y_{0} \leq -1[/itex]
and
[itex]ax_{0}>n[/itex]
Since y0 is negative, the following holds true:
[itex]ax_{0}-b \geq n[/itex]
And since [itex]x_{0}\leq b-1[/itex]
[itex]a(b-1)-b \geq n \rightarrow ab-a-b \geq n[/itex]
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.