Number theory

E

EulerRules

New member
Joined
Mar 27, 2013
Messages
5
First of all: I am not sure if this is the correct subforum to post this thread, so please move it if it has been incorrectly placed.

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

My thoughts:
First of all, we want to know the highest number that cannot be written on above form. That will make it easier to then investigate the numbers between 1 and said number that cannot be written on above form.

Let n be a fixed integer (also negative) such that \(\displaystyle n = ax_{0}+by_{0}.\) If n lacks solutions for positive x0 and y0, assume that we want x0 to be as small as positive but nonetheless nonnegative. Then the following holds true:
\(\displaystyle 0 \leq x_{0} \leq b-1\)
\(\displaystyle y_{0} \leq -1 \)
\(\displaystyle ax_{0} > n\)
We could go as far as state the following since y0 is negative
\(\displaystyle ax_{0}-b \geq n \)
since \(\displaystyle x_{0}\leq b-1\) we can write
\(\displaystyle a(b-1)-b \geq n \leftrightarrow ab-a-b \geq n \)

Now to my question: How do I continue to evaluate what numbers in the interval [1,ab-a-b] that may not be written on above form?
Please note that there is a difference between x, x0, y and y0. x and y are natural numbers whereas x0 is a nonnegative integer and y0 is an integer.
 
Last edited:
EulerRules said:
If and >> > a and b are relatively prime natural numbers < < < , how many natural numbers cannot be written on the form xa+yb where > > > x and y are nonnegative integers < < < ?

My thoughts:
First of all, we want to know the highest number that cannot be written on above form. That will make it easier to then investigate the numbers between 1 and said number that cannot be written on above form.

Let n be a fixed integer (also negative) n can't be negative because of the restrictions on a, b, x, and y.such that \(\displaystyle n = ax_{0}+by_{0}.\) If n lacks solutions for positive x0 and y0, assume that we want x0 to be as small as positive but nonetheless nonnegative. Then the following holds true:
\(\displaystyle 0 \leq x_{0} \leq b-1\)
\(\displaystyle y_{0} \leq -1 \)
\(\displaystyle ax_{0} > n\)
We could go as far as state the following since y0 is negative
\(\displaystyle ax_{0}-b \geq n \)
since \(\displaystyle x_{0}\leq b-1\) we can write
\(\displaystyle a(b-1)-b \geq n \leftrightarrow ab-a-b \geq n\)<----- This is not true if a = 1 and b is any natural number (positive integer).**

Now to my question: How do I continue to evaluate what numbers in the interval [1,ab-a-b] that may not be written on above form?
Please note that there is a difference between x, x0, y and y0. x and y are natural numbers whereas x0 is a nonnegative integer and y0 is an integer.
Click to expand...

** That inequality is equivalent to \(\displaystyle \ n \ \le \ ab - a - b. \ \ \ \) If a = 1, and b = b, then ab - a - b = -1. \(\displaystyle \ \ But, \ n\ne -1, \ \ because \ \ n \ \ can't \ \ be \ \ negative.\)
 
Last edited:
lookagain said:
** That inequality is equivalent to \(\displaystyle \ n \ \le \ ab - a - b. \ \ \ \) If a = 1, and b = b, then ab - a - b = -1. \(\displaystyle \ \ But, \ n\ne -1, \ \ because \ \ n \ \ can't \ \ be \ \ negative.\)
Click to expand...
As I mentioned in my post, there is a difference between x, x0, y and y0. n is a fixed integer for integers x0 and y0, therefore n can be negative.
If a=1 then a and b cannot be relatively prime which they should be.
 
lookagain said:
False. Two numbers are relatively prime when their greatest common factor is 1. gcf(1, b) = 1. Edit: Here are a bunch of Web pages:http://wiki.answers.com/Q/What_is_a_relative_prime_number
Click to expand...
Yeah my mistake. But your objection is not very valid. If a=1 and b is any natural number, then yes we would get the result \(\displaystyle -1 \geq n\). However, what this tells us is that the largest number that cannot be written on the form xa+yb is -1 if a=1 which indeed is correct. There is nothing wrong there, although the special case of either a or b being 1 is not of very much interest. I think you are confused with the notation, xa+yb is a natural number yes, but in my proof I am taking use of other coefficients (x0 and y0 where x0 is a nonnegative integer and y0 is an integer (midway through the proof I am turning it into a negative integer)) and as such ax0+by0 can be negative.
 
Last edited:
For the sake of preventing confusion, misunderstanding and misguidance, I will postulate the problem a bit more precise.
How many natural numbers cannot be written on the form \(\displaystyle xa+yb: a,b \in N, a,b >1, x,y \in N, x,y \geq 0\) if GCD(a,b)=1?
 
EulerRules said:
For the sake of preventing confusion, misunderstanding and misguidance, I will postulate the problem a bit more precise.
How many natural numbers cannot be written on the form \(\displaystyle xa+yb: a,b \in N, a,b >1, x,y \in N, x,y \geq 0\) if GCD(a,b)=1?
Click to expand...
The set of natural numbers, N, is typically stated to be the set of positive integers only. So, for the sake of further preventing confusion, I would go with something such as \(\displaystyle "Let \ \ a, \ b, \ x, \ y \ \ belong \ \ to \ \ the \ \ set \ \ of \ \ positive \ \ integers, \ \ with \ \ a, \ b \ > \ 1, \ \ and \ \ x, \ y \ \ge \ 0."\)



Edit:I do not know how to help at this time, other than to show n values for specific cases of a and b values.
 
Last edited:
lookagain said:
The set of natural numbers, N, is typically stated to be the set of positive integers only. So, for the sake of further preventing confusion, I would go with something such as \(\displaystyle "Let \ \ a, \ b, \ x, \ y \ \ belong \ \ to \ \ the \ \ set \ \ of \ \ positive \ \ integers, \ \ with \ \ a, \ b \ > \ 1, \ \ and \ \ x, \ y \ \ge \ 0."\)
Click to expand...
Isn't that pretty much what I wrote? Although more elegantly expressed! :)
Anyway, I think there shouldn't be any confusion now. Do you have any ideas on how I may continue my solution?
 
You must log in or register to reply here.
Top