Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks in advance!

share|improve this question

3 Answers 3

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

share|improve this answer

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

share|improve this answer
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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