greatest common divisor (gcd),

Help
momo
2012-07-09
2012-11-20
  • momo

    momo - 2012-07-09

    Hello,
    can reduce, or can man calculate gcd of two polynomials with symbolic coefficients.
    example
    Variable : lambda.
    p1 = a * lambda ^ 2 +2 * a * lambda * b +2 * a * b + (2 * lambda * 2) + b * lambda ^ 3
    p2: = 2 * a * lambda + 2 * a * b + (2 * 2) * b +3 * lambda ^ 2
    thanks

     
  • Arthur Norman

    Arthur Norman - 2012-07-09

    When I ry an example I can eg observe

    gcd(x^2+2*x*y+y^2, x^2-y^2);

    x + y

    Note that "lambda"  is a keyword in Reduce and attempts to use it as a variable name may end up "delicate". Also you have a ": =" with a space within when assigning to p1 where ":=" (without a space) is needed

    If I fix those two I see for your example
    12: p1 := a * lam ^ 2 +2 * a * lam * b +2 * a * b + (2 * lam * 2) + b * lam ^ 3;
               

                                   2        3
    p1 := 2*a*b*lam + 2*a*b + a*lam  + b*lam  + 4*lam

    13: p2:= 2 * a * lam + 2 * a * b + (2 * 2) * b +3 * lam ^ 2;      

                                       2
    p2 := 2*a*b + 2*a*lam + 4*b + 3*lam

    14: gcd(p1, p2);

    1

    Hope this helps. Arthur

     
  • momo

    momo - 2012-07-09

    Hello Arthur,
    Thank you for your answer
    But this is incorrect
    result  is always 1

     
  • Thomas Sturm

    Thomas Sturm - 2012-07-09

    The gcd function of Reduce computes a multivariate gcd.

    Maybe you are looking for a univariate gcd in the variable lam considering the other variables as parameters. This requires a finite case distinction on the parameters. It is in fact a special case of a comprehensive Gröbner system.

    Does the following match your expectations?

    Thomas

    1: load_package cgb;                                                           
    2: p1 := a * lam ^ 2 +2 * a * lam * b +2 * a * b + (2 * lam * 2) + b * lam ^ 3;
    p₁ := 2⋅a⋅b⋅lam + 2⋅a⋅b + a⋅lam² + b⋅lam³ + 4⋅lam

    3: p2:= 2 * a * lam + 2 * a * b + (2 * 2) * b +3 * lam ^ 2;                    
    p₂ := 2⋅a⋅b + 2⋅a⋅lam + 4⋅b + 3⋅lam²

    4: torder({lam},lex);                                                          
    {{},lex}

    5: gsys {p1,p2};
    {{2⋅a⁴⋅b³ - 7⋅a⁴⋅b² + 6⋅a⁴⋅b + 2⋅a³⋅b⁵ - 12⋅a³⋅b⁴ + 36⋅a³⋅b³ - 28⋅a³⋅b²

       - 12⋅a³⋅b + 12⋅a²⋅b⁵ - 48⋅a²⋅b⁴ + 40⋅a²⋅b³ + 91⋅a²⋅b² - 60⋅a²⋅b + 24⋅a⋅b⁵

       - 48⋅a⋅b⁴ - 96⋅a⋅b³ + 144⋅a⋅b² + 72⋅a⋅b + 16⋅b⁵ - 96⋅b³ + 144⋅b ≠ 0

       ∧ 2⋅a²⋅b - 3⋅a² - 3⋅a⋅b² + 9⋅a⋅b - 6⋅b² + 18 ≠ 0 ∧ b ≠ 0,

      {2⋅a⁴⋅b³ - 7⋅a⁴⋅b² + 6⋅a⁴⋅b + 2⋅a³⋅b⁵ - 12⋅a³⋅b⁴ + 36⋅a³⋅b³ - 28⋅a³⋅b²

        - 12⋅a³⋅b + 12⋅a²⋅b⁵ - 48⋅a²⋅b⁴ + 40⋅a²⋅b³ + 91⋅a²⋅b² - 60⋅a²⋅b + 24⋅a⋅b⁵

        - 48⋅a⋅b⁴ - 96⋅a⋅b³ + 144⋅a⋅b² + 72⋅a⋅b + 16⋅b⁵ - 96⋅b³ + 144⋅b}},

    {2⋅a²⋅b² - 3⋅a²⋅b + 4⋅a⋅b² + 3⋅a⋅b ≠ 0 ∧ b ≠ 0

       ∧ 2⋅a²⋅b - 3⋅a² - 3⋅a⋅b² + 9⋅a⋅b - 6⋅b² + 18 = 0,

      {2⋅a²⋅b² - 3⋅a²⋅b + 4⋅a⋅b² + 3⋅a⋅b}},

    {2⋅a²⋅b - 3⋅a² - 3⋅a⋅b² + 9⋅a⋅b - 6⋅b² + 18 ≠ 0 ∧ b ≠ 0 ∧ 2⋅a⁴⋅b³ - 7⋅a⁴⋅b²

       + 6⋅a⁴⋅b + 2⋅a³⋅b⁵ - 12⋅a³⋅b⁴ + 36⋅a³⋅b³ - 28⋅a³⋅b² - 12⋅a³⋅b + 12⋅a²⋅b⁵

       - 48⋅a²⋅b⁴ + 40⋅a²⋅b³ + 91⋅a²⋅b² - 60⋅a²⋅b + 24⋅a⋅b⁵ - 48⋅a⋅b⁴ - 96⋅a⋅b³

       + 144⋅a⋅b² + 72⋅a⋅b + 16⋅b⁵ - 96⋅b³ + 144⋅b = 0,

      {b⋅lam³ + a⋅lam² + (2⋅a⋅b + 4)⋅lam + 2⋅a⋅b,

       3⋅lam² + (2⋅a)⋅lam + (2⋅a⋅b + 4⋅b),

       (2⋅a²⋅b - 3⋅a² - 3⋅a⋅b² + 9⋅a⋅b - 6⋅b² + 18)⋅lam

        + (2⋅a²⋅b² - 3⋅a²⋅b + 4⋅a⋅b² + 3⋅a⋅b)}},

    {a² - 3⋅a⋅b - 6 ≠ 0 ∧ a ≠ 0 ∧ b = 0,

      {a⋅lam² + (2⋅a⋅b + 4)⋅lam + 2⋅a⋅b,

       3⋅lam² + (2⋅a)⋅lam + (2⋅a⋅b + 4⋅b),

       (a² - 3⋅a⋅b - 6)⋅lam + (a²⋅b - a⋅b)}},

    {a⋅b + 2 ≠ 0 ∧ a = 0 ∧ b = 0,

      {3⋅lam² + (2⋅a)⋅lam + (2⋅a⋅b + 4⋅b),

       (2⋅a⋅b + 4)⋅lam + 2⋅a⋅b}},

    {a ≠ 0 ∧ a² - 3⋅a⋅b - 6 = 0 ∧ b = 0,

      {a⋅lam² + (2⋅a⋅b + 4)⋅lam + 2⋅a⋅b,

       3⋅lam² + (2⋅a)⋅lam + (2⋅a⋅b + 4⋅b)}},

    {b ≠ 0 ∧ 2⋅a²⋅b² - 3⋅a²⋅b + 4⋅a⋅b² + 3⋅a⋅b = 0

       ∧ 2⋅a²⋅b - 3⋅a² - 3⋅a⋅b² + 9⋅a⋅b - 6⋅b² + 18 = 0,

      {b⋅lam³ + a⋅lam² + (2⋅a⋅b + 4)⋅lam + 2⋅a⋅b,

       3⋅lam² + (2⋅a)⋅lam + (2⋅a⋅b + 4⋅b)}},

    {a⋅b + 2 = 0 ∧ a = 0 ∧ b = 0,{2⋅a⋅b}}}

     
  • momo

    momo - 2012-07-09

    Hello Thomas,
    Sorry, where is the gcd!
    I must then divide p1 by gcd
    Thank you
    momo

     
  • Thomas Sturm

    Thomas Sturm - 2012-07-09

    The gcd is not a single object: Consider a*x+y and y^2. For a<>0 the gcd is 1 but for a=0 it is y. The system I sent you is a complete case distinction, where the 1st entry

    {2⋅a⁴⋅b³ - 7⋅a⁴⋅b² + 6⋅a⁴⋅b + 2⋅a³⋅b⁵ - 12⋅a³⋅b⁴ + 36⋅a³⋅b³ - 28⋅a³⋅b²

       - 12⋅a³⋅b + 12⋅a²⋅b⁵ - 48⋅a²⋅b⁴ + 40⋅a²⋅b³ + 91⋅a²⋅b² - 60⋅a²⋅b + 24⋅a⋅b⁵

       - 48⋅a⋅b⁴ - 96⋅a⋅b³ + 144⋅a⋅b² + 72⋅a⋅b + 16⋅b⁵ - 96⋅b³ + 144⋅b ≠ 0

       ∧ 2⋅a²⋅b - 3⋅a² - 3⋅a⋅b² + 9⋅a⋅b - 6⋅b² + 18 ≠ 0 ∧ b ≠ 0,

      {2⋅a⁴⋅b³ - 7⋅a⁴⋅b² + 6⋅a⁴⋅b + 2⋅a³⋅b⁵ - 12⋅a³⋅b⁴ + 36⋅a³⋅b³ - 28⋅a³⋅b²

        - 12⋅a³⋅b + 12⋅a²⋅b⁵ - 48⋅a²⋅b⁴ + 40⋅a²⋅b³ + 91⋅a²⋅b² - 60⋅a²⋅b + 24⋅a⋅b⁵

        - 48⋅a⋅b⁴ - 96⋅a⋅b³ + 144⋅a⋅b² + 72⋅a⋅b + 16⋅b⁵ - 96⋅b³ + 144⋅b}}

    is the "generic case," which is sufficient in many cases. Assuming the negated equations, which are the first entry of the pair, the second entry if a singleton containing the gcd. Note, however, that if any of the negated equations is violated, then this result is meaningless.

    All this is valid if you want to think about "parametric gcd". If you need a multivariate gcd, then the gcd function of Reduce does the job.

    Thomas

     
  • momo

    momo - 2012-07-10

    Hello Thomas,
    yes
    that was my question
    Thank you very much

     

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks