Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Finding number of integers not satisfying an expression

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778

    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.
    Thanks from pranay
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    95

    Re: Finding number of integers not satisfying an expression

    thanks a lot emakarov
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: March 15th 2011, 03:42 AM
  2. Replies: 5
    Last Post: February 22nd 2009, 02:10 PM
  3. Replies: 2
    Last Post: November 8th 2008, 08:05 PM
  4. Proof needed that expression <=1 for all positive integers
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: August 7th 2008, 02:23 AM
  5. real problem finding all values satisfying....
    Posted in the Calculus Forum
    Replies: 0
    Last Post: April 22nd 2008, 01:53 AM

Search Tags


/mathhelpforum @mathhelpforum