# How to find this GCD?

How to find GCD of $2n + 3$ and $5n^2 + 3n -1$ (depending on $n$)

-

Note that $2n+3$ is always odd. Thus the gcd of $2n+3$ and $5n^2+3n-1$ is the same as the gcd of $20n^2+12n-4$. Now use the Euclidean Algorithm. Note that $$20n^2+12n-4=(10n-9)(2n+3)+23.$$ Thus $\gcd(5n^2+3n-1,2n+3)=\gcd(2n+3,23)$. We could go through another step of the Euclidean algorithm. But it is easier to note that since $23$ is prime, $\gcd(2n+3,23)=1$ or $\gcd(2n+3,23)=23$.

The second happens precisely when $2n+3\equiv 0\pmod{23}$, or equivalently when $n\equiv 10\pmod{23}$.

-

Let $d$ be the gcd. Then $d| (2n+3)^2=4n^2+12n+9$ and the linear combination $4(5n^2+3n-1)-5(4n^2+12n+9)=-48n-49$. It also divides $24(2n+3)-48n-49=23$. Therefore the gcd is either $1$ or $23$.

-
It is $23$ when $n=10+23k$. – PAD Dec 26 '12 at 15:42
Note that $2n+3$ is a multiple of $23$ when $2n+3 \equiv 0 \ \ (23)$ which happens if $n \equiv 10 \ \ (23)$. At the same time $5\cdot 10^2 +3 \cdot 10 -1 \equiv 529 \equiv 0 \ \ (23)$. – PAD Dec 26 '12 at 15:54

The answer is $1$, because $(5n^2+3n-1)/(2n+3)=5/2 n-9/4$ with remainder $23/4$. The next step of the Euclidean algorithm would be $(2n+3)/(23/4)=\ldots$ without any remainder. Therefore $gcd(5n^2+3n-1,2n+3)=23/4$. This is a polynomial and can be normed so multiply it with $4/23$ and you get $gcd(5n^2+3n-1,2n+3)=1$.

Keep in mind that the Euclidean algorithm doesn't yield a unique result because there are infinitely many by multiplying with constants like I did!

The general approach for $gcd(p,q)$ is the following:

\begin{align}p&=q_1\cdot q+r_1\\q&=q_2\cdot r_1+r_2\\r_1&=q_3\cdot r_2+r_3\\r_2&=q_4\cdot r_3+r_4\\&\;\vdots\end{align}

and so on. If you find a $r_k=0$ then $gcd(p,q)=r_{k-1}$.

-