How to find GCD of $2n + 3$ and $5n^2 + 3n -1$ (depending on $n$)
Thanks in advance!
How to find GCD of $2n + 3$ and $5n^2 + 3n -1$ (depending on $n$)
Thanks in advance!
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$.
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}$.
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}$.