## greatest common divisor (gcd), document.SUBSCRIPTION_OPTIONS = { "thing": "thread", "subscribed": false, "url": "subscribe", "icon": { "css": "fa fa-envelope-o" } };

Help
momo
2012-07-09
2012-11-20
• 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 - 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 - 2012-07-09

Hello Arthur,
But this is incorrect
result  is always 1

• 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

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 - 2012-07-09

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

• 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 - 2012-07-10

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