The last non-zero remainder in the euclidean division algorithm gives the GCD.
The GCD h(x) can be expressed as the linear combination of f(x) and g(x) i.e.
h(x)=r(x)f(x)+s(x)g(x) where f(x) is the dividend and g(x) is the divisor.
Procedure:
Using landscape mode is recommended on mobile phones and other smaller screens.
Polynomials can be entered in the fields provided. Use only lower case x in the field.
Expressions like x2 can be entered in the field by typing x^2 on the
keyboard.
1, x, +, x^2, x^3 and their combinations need to be entered in the fields in this task.
Do not enter any other symbols.
Enter the values in all the fields of a row and click on Submit.
The correctness of the entered answer is displayed in Observations.
If the answer is correct, proceed to the next row. Values in the fields
of a row cannot be entered without completing the previous row correctly.
Repeat this process until all the rows are filled and the algorithm is complete when a
success message displaying the GCD appears in Observations.
Next - Displays the next example.
Previous - Displays the previous example.
Compute the GCD of x5+x2+x+1 and
x3+x2+x+1 over GF(2)
using the
extended Euclidean Division Algorithm.
Remainder
r(x)
s(x)
Quotient
x5+x2+x+1
1
0
x3+x2+x+1
0
1
0
Observations
Compute the GCD of x6+x3+x2+1 and x3+1
over GF(2)
using the
extended Euclidean Division Algorithm.