# Why does the long division method not work when trying to find GCD of 2 polynomials that have an actual GCD of 1? [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); 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.

## 1 Answer

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$$

• Sorry, how come 5x is positive, not negative? My final polynomial was 22, not -22. – CoopDaddio Apr 22 at 6:50
• I realised I am getting 22 instead of -28... Where is my mistake? – CoopDaddio Apr 22 at 6:54
• @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. – Arthur Apr 22 at 6:56
• 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? – CoopDaddio Apr 22 at 6:58
• 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? – CoopDaddio Apr 22 at 7:27