# How to find the gcd of this polynomial?

What would the GCD of $3n + 2$ and $4n + 3$ be using Euclid's algorithm

-

Hint: Note that $$-4(3n+2)+3(4n+3)=1$$

-
Probably the point of the exercise was to learn how to use the Euclidean algorithm symbolically - as instructed "by using Euclid's algorithm" (see Brett's answer). This gives the gcd without needing to obtain the above Bezout identity (i.e. without using the extended Euclidean algorithm). – Math Gems Feb 9 '13 at 20:15
@MathGems: Yes and that's why I prefer Brett answer than mine. I tried to solve it by using Bézout's identity. You are right. +1 for him. – Babak S. Feb 9 '13 at 20:21
That's not to say that other methods aren't useful. For example, the above apporach may be generalized to show that $\rm\: A(n,1)\:$ is a coprime pair for any $2 \times 2$ integer matrix $\rm\,A\,$ with determinant $= 1,$ e.g. see this answer. – Math Gems Feb 9 '13 at 20:32
I like this...it's good to have different approaches+1 – amWhy Feb 10 '13 at 0:16

$$4n+3=(3n+2)+(n+1)$$ $$(3n+2)=3\cdot(n+1)-1$$

Since the remainder is $\pm 1$, the GCD is $1$.

Alternatively, note that the greatest common divisor must divide both numbers, as well as their difference. So if $d$ is the GCD, $d|(n+1)$. But $(n+1)$ cannot share any factors with $(4n+3)=4\cdot(n+1)-1$.

-
I hope the OP didn't mislead by my very short answer. – Babak S. Feb 9 '13 at 20:23