1

I came across this problem in a textbook (not an assignment) and was interested in how to solve it.

I imagine $\gcd(4k+2,k^2+k)$ can easily be proved to be an even integer because:

$4k+2 = 2(2k+1)$, which would be even because its $2$ times and integer, and

$k^2+k$ can be proved to be even by using $2$ cases, one where $k$ is even and is equal to $2n$ and the other for an odd $k$, where we can set it equal to $2n+1$, where $n \in \mathbb{Z}$.

From here, if we let $\gcd(4k+2,k^2+k)=x$, we can say if $x$ is the $\gcd$ of $(4k+2,k^2+k)$ then it must divide any linear combination of the 2. I'm stuck on this part, because there's so many directions this could go.

I'm thinking $x|(k^2+5k+2)$ or $x|(4k^2-2)$, but I can't find a way to prove the gcd isn't some even integer greater than $2$. Any insight is appreciated!

mathjohnn
  • 181
  • 11
  • 1
    Of course, you meant $4k+2=2(2k+1)$. If you had $2k+2 = 2(k+1)$, then $k+1$ would divide both terms. – Ted Shifrin Nov 13 '20 at 06:38
  • Yes, thank you for catching that! Lack of attention to detail on my part. – mathjohnn Nov 13 '20 at 06:48
  • 1
    Are you allowed to use the fact that $\text{gcd} (a,b) = \text{gcd} (a,b-a)$ where $a < b$? – Toby Mak Nov 13 '20 at 06:49
  • I believe I would be allowed to use that, I'm just not sure where to apply that other than to say $\gcd(a, b-a)$ divides both $a$ and $b-a$. That said, this is a new topic for me so I have much to learn – mathjohnn Nov 13 '20 at 06:59
  • @TobyMak The OP referred to linear combinations if the two, so yes. I certainly used a case of this as part of my hint. – Ted Shifrin Nov 13 '20 at 07:00
  • $4(k^2+k)-k(4k+2) = 2k$. Let m be the gcd. We know $m|2k$ because the gcd divides linear combinations. And we also know that $m|(4k+2)$. Since $m|4k$ we also know that $m|2$. So m is 1 or 2. Since we know m is even, $m=2$. – Ameet Sharma Nov 13 '20 at 07:08

2 Answers2

2

Let $(4k+2,k^2+k)=d$. Then $d|4k+2-2(4(k^2+k)-k(4k+2))=2$.

$d=2$ since both numbers are even. The motivation is to play around until we get a constant (in this case, it is $2$).

It motivates us to multiply $4k+2$ by $k$ and $k^2+k$ by 4 and to subtract those numbers so we have something easier to handle (lower in degree): $4(k^2+k)-k(4k+2)=2k$. Seeing $4k+2$, we are motivated to multiply $2k$ by two and subtract from $4k+2$ to obtain $2$.

Adola
  • 1,909
  • 2
  • 13
  • 24
1

HINT: If a prime $p$ divides both $2k+1$ and $k(k+1)$, then either $p$ divides $k$ or $p$ divides $k+1$. Show that the first leads to an immediate contradiction and the second leads to the conclusion that $p$ divides $k$.

Ted Shifrin
  • 115,160
  • Thank you! I got a couple follow ups to that. 1) How would you show a contradiction if $p$ divides $k$? Can you say that $k$, then it must divide $(2k+1) - 2(k)$, which isn't possible because an even integer can't divide $1$? And 2) If $p$ divides $k$ leads to a contradiction, how would $p$ divides $k+1$ lead to the conclusion that $p$ divides $k$? – mathjohnn Nov 13 '20 at 07:05
  • 1
    Not even integer. I removed the $2$ and sAid prime $p$. How do you show that if $p|(k+1)$ and $p|(2k+1)$ then $p|k$? – Ted Shifrin Nov 13 '20 at 07:12
  • If $p|(k+1)$ and $p|(2k+1)$ then $p$ divides the difference, or $(2k+1)-(k+1)$, so $p|k$. And if $p|k$ and $p|(k+1)$, then $p|(k+1)-k$. So $p|1$? That would imply that $p=1$ and not $2$ though right? Sorry I'm a bit slow at this right now – mathjohnn Nov 13 '20 at 07:19
  • 1
    $p$ is prime, so it can’t divide $1$. We conclude that $2k+1$ and $k(k+1)$ are relatively prime. – Ted Shifrin Nov 13 '20 at 07:21
  • Gotcha. If $2k+1$ and $k(k+1)$ are relatively prime, the gcd is $1$. So if we go back to the original equation to find $\gcd(2(2k+1), k(k+1)$, would it suffice to say since $2k+1$ and $k(k+1)$ are relatively prime, $2|(2(2k+1))$ and $k(k+1)$ is even for all $k$, then $\gcd(4k+2, k^2+k)$ is $2$? – mathjohnn Nov 13 '20 at 07:29
  • 1
    Right. It's at least $2$, but no other prime can divide both. – Ted Shifrin Nov 13 '20 at 07:34
  • Thank you for all the help Ted!! Your explaining taught me more in the past 30 minutes than I could learn from a textbook. – mathjohnn Nov 13 '20 at 07:36