This question already has an answer here:
I have written a program that calculates the GCD of 2 polynomials using long division (Euclid's algorithm/theorem).
I am trying to find the GCD of x^2 - 3 and x + 5, which I already know is 1. However, the division process does not give me this answer. I will step through what my program does.
Firstly, it divides x^2 by x to get x. x + 5 is then multiplied by x to get x^2 + 5x. It then subtracts x^2 + 5x from x^2 - 3 to get -5x - 3. It then divides -5x by x to get -5. x + 5 is then multiplied by -5 to get -5x - 25. It then subtracts -5x - 25 from -5x - 3 to get 22. The degree of 22 (0) is less than the degree of x + 5 (1), so it stops, and passes the remainder of 22 to the program.
The program then sets up another long division, but this time divides x + 5 by 22. Firstly, it divides x by 22 to get 1/22 x. 22 is then multiplied by 1/22x to get x. It then subtracts x from x + 5 to get 5. It then divides 5 by 22 to get 5/22. 22 is then multiplied by 5/22 to get 5. It then subtracts 5 from 5 to get 0. Remainder is 0, so program stops.
According to Euclid's algorithm/theorem, the GCD would then be 22, as it was the divisor when the remainder was 0, but the GCD is in fact 1 for polynomials x^2 - 3 and x + 5. Why doesn't this work, and how would I fix it? Thankyou.