# Finding number of integers not satisfying an expression

• Mar 22nd 2012, 04:36 PM
pranay
Finding number of integers not satisfying an expression
Hi,
For any a, b >= 0, how can one find the number of positive integers which cannot be expressed as ax + by where gcd(x,y) = 1 and x,y > 1
E.g for x,y = 3,4 the number of such integers is 3
I think that extended euledian algorithm can be used here but am not sure how.
Thanks.
• Mar 22nd 2012, 05:57 PM
emakarov
Re: Finding number of integers not satisfying an expression
Given coprime positive integers x, y, the set of positive integers that cannot be represented as ax + by for some nonnegative integers a, b is called the set of gaps of a numerical semigroup $\langle x, y\rangle$ with two generators x and y. The number of elements in the set of gaps is called the genus of the semigroup. In the case of two generators x and y, the genus equals (x − 1)(y − 1) / 2.
• Mar 22nd 2012, 08:45 PM
pranay
Re: Finding number of integers not satisfying an expression
thanks a lot emakarov :)