2

For $l \in \mathbb{N}$ I'm to prove that the greatest common divisor, $\gcd(8l^2+20l+13,4l+2) = 1$. I've tried induction, but I couldn't pull off, now I'm at a loss of how to even begin to solve this.

PS: It's also possible that it's not possible to prove it, because it's not correct.

Giuseppe
  • 737
Mathaniel
  • 781
  • 1
    As the other answers have pointed out, the Euclidean algorithm is valid for polynomials too. Depending on happenstance it won't always finish (take $\gcd(l, 2)$, for instance) but when it does finish, it gives a valid answer. – Arthur Oct 31 '17 at 13:28
  • 1
    Possible typo in the question? It seems to me that if $l=2$, then the left hand side is $\operatorname{gcd}(85, 10) = 5$. – Daniel Schepler Oct 31 '17 at 17:38
  • @Arthur What do you mean it won't always finish? If it didn't, it wouldn't be an algorithm. Following the algorithm gives $\gcd(l,2)=2$. – Théophile Oct 31 '17 at 17:43
  • @Théophile If you only allow integer coefficients, then the $\gcd$ of two polynomials doesn't always exist, and in those cases, the Euclidean algorithm doesn't finish (for instance, with $2$ and $l$ we find $\gcd(2,l)=\gcd(2,l-2l)$ and you never get anywhere). However, if there is a $\gcd$, then the Euclidean algorithm finds it. – Arthur Oct 31 '17 at 18:41
  • @Arthur Personally, I always allow rational coefficients. – Théophile Oct 31 '17 at 18:49
  • @Théophile Always is a strong word. At any rate, we're told that $l\in\Bbb N$, so at the bottom here is actually a $\gcd$ of integers, not of polynomials (is just that one of the natural numbers is unknown). Thus rational coefficients breaks that, and you can't use the $\gcd$ result your get to answer the actual question. In that context, if you had ended up with $\gcd(l,2)$, the final answer would be "the $\gcd$ is $1$ if $l$ is odd and $2$ if $l$ is even" – Arthur Oct 31 '17 at 18:52
  • @Arthur I meant my last comment as a (half-)joke. In seriousness, just because $l \in \Bbb N$, we cannot assume that the $\gcd$ is to be taken over the integers. (If we had been given that $l$ is of the form $3k+1$, would we restrict the $\gcd$ to the same form?) You may be right that it was intended to be over the integers, but in that case it should be explicitly mentioned in the problem. It is much more common to work over a field; otherwise, as you say, the algorithm may not work. – Théophile Oct 31 '17 at 19:24

3 Answers3

8

Set $p(l)=8l^2+20l+13$ and $q(l)=4l+2$.

Polynomial division will give you $s(l), r(l)$ with $$p(l)=q(l)s(l)+r(l)$$ and here you can guarantee that the degree of $r(l)$ is less than the degree of $q(l)$ - so in this case it must be a constant $r$

Write $$r=p(l)-q(l)s(l)$$ - any common factor of $p$ and $q$ is a factor of the right-hand side, so must be a factor of $r$. Here such a factor must be a constant, therefore, because $r$ is a non-zero constant when you work it out. (You can see this is non-zero because for integer $l$ we have that $p$ is odd and $q$ is even)

Now any common factor of $p(l)$ and $q(l)$ is a common factor for any choice of $l$. So put $l=0$ and see what options you have.

Mark Bennet
  • 100,194
2

Try to calculate $(8l^2+20l+13)\div (4l+2)$

Cornman
  • 11,065
  • 4
  • 30
  • 57
2

Hint:

For all integers $a,b,q,r$, if $a=bq+r$ then $\gcd(a,b)=\gcd(b,r)$.

ajotatxe
  • 65,084