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.


marked as duplicate by Bill Dubuque polynomials Apr 22 at 21:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Remember that you're working over real polynomials, not integer polynomials. So as far as divisibility is concerned, the polynomial $22$ is equivalent to the polynomial $1$.

That means that the Euclidean algorithm gives $$ \gcd(x^2-3, x+5)\\ =\gcd(x^2-3-x(x+5), x+5)\\ =\gcd(-5x-3, x+5)\\ =\gcd(-5x-3+5(x+5), x+5)\\ =\gcd(22, x+5)\\ =\gcd(1, x+5)=1 $$

  • $\begingroup$ Sorry, how come 5x is positive, not negative? My final polynomial was 22, not -22. $\endgroup$ – CoopDaddio Apr 22 at 6:50
  • $\begingroup$ I realised I am getting 22 instead of -28... Where is my mistake? $\endgroup$ – CoopDaddio Apr 22 at 6:54
  • $\begingroup$ @CoopDaddio Yes, sorry, that was indeed my mistake. I had both $x+5$ and $x-5$ in my head for some reason and got them mixed up. $\endgroup$ – Arthur Apr 22 at 6:56
  • $\begingroup$ So why is 22 equivalent to 1? And does this mean all polynomials that are just integers are all equal to 1 in this case? $\endgroup$ – CoopDaddio Apr 22 at 6:58
  • $\begingroup$ Sorry just want to confirm before you answer: so if the divisior of 2 polynomials that are non-zero and have a single variable (x in this case) is ever just an integer value (either negative or positive), and the remainder is 0, the GCD is always 1. Is this correct? $\endgroup$ – CoopDaddio Apr 22 at 7:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.