UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 8

Problem:

Solution:

The answer for part (a) is $ x^2 + x + 1 $
The answer for part (b) is $ x - 1 $

In order to solve this problem, I could have just use MATLAB/Octave. It seems that the GCD function in Octave does not support symbolic expressions, but I could write a simple script for that in MATLAB.

But instead, in order to practice Python. I wrote the whole symbolic processing and GCD in Python myself. The code for computing the final GCD is very close to what one would do in MATLAB (arguably closer to mathematics, I hate to type 2 * x in MATLAB, 2x is much more mathematically intuitive)

Here is the main function used to solve the problem.

from polynomial_module import *

# Problem 8a
print polynomial.polynomial_gcd(
    polynomial.polynomial_gcd(
        polynomial.from_string("x^4 + x^2 + 1"),
        polynomial.from_string("x^4 - x^2 - 2x - 1")),
    polynomial.from_string("x^3 - 1"))

# Problem 8b
print polynomial.polynomial_gcd(
    polynomial.polynomial_gcd(
        polynomial.from_string("x^3 + 2x^2 - x - 2"),
        polynomial.from_string("x^3 - 2x^2 - x + 2")),
    polynomial.from_string("x^3 - x^2 - 4x + 4"))

Of course, the magic of this problem lies within the polynomial module. I described the module in this post.