1
$\begingroup$

I am trying to grasp basic concepts of number theory, I would like to know if my reasoning is correct. When attempting to find the $\gcd(a, b)$ where $a = n^2$ and $b = 2n$ such that $n$ is odd, I first express $n$ as an odd integer in terms of $k$, $$n = 2k + 1 : k \in \Bbb Z^+ $$ then I express $a$ and $b$ in terms of $n = 2k + 1$ $$a = n^2 = (2k + 1)^2$$ $$b = 2n = 2(2k + 1)$$ and then I apply the Euclidean algorithm to find $\gcd\left((2k + 1)^2, 2(2k + 1)\right)$, $$(2k + 1)^2 = (4k + 2)(k) + (2k + 1)$$ $$(4k + 2) = (2k + 1)(2) + 0$$ $$\therefore \quad \forall\; n = 2k + 1:k\in\Bbb Z^ + , \; \gcd(n^2,\, 2n) = n$$

Trying the other case when $n$ is even I express it as $$n = 2k:k\in\Bbb Z^ + $$ such that $a$ and $b$ in terms of $n = 2k$ gives $$a = n^2 = (2k)^2$$ $$b = 2n = 2(2k)$$ and apply the Euclidean Algorithm for $\gcd\left((2k)^2, 2(2k)\right)$ $$(2k)^2 = 2(2k)(k) + 0$$ This result is a bit unclear to me since this is all new material, what does that result tell me about the $\gcd$ if the algorithm goes to zero in the first step?

From divisibility, I see this as $k\;|\;(2k)^2$ such that $\frac {(2k)^2}k = 2(2k) = 2n$ from which I would claim that $$\forall\; n = 2k : k\in \Bbb Z^ + , \;\gcd(n^2, 2n) = 2n$$ Is this a correct reasoning about the relation between the divisibility, the Euclidean algorithm and the $\gcd$?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ If it goes to zero in the first step, that means $\gcd(a,b)$ is $b$ and that therefore $b|a$. A few things to keep in mind $\gcd(c*m,d*m) = m\gcd(c,d)$ and that $\gcd(n,kn) = n$ and $\gcd (a,b) = b \iff b|a$. $\endgroup$ – fleablood Feb 5 '17 at 21:30
1
$\begingroup$

It's a bit simpler than that.

we know that if $a = n^2$ and $b = 2n$ that $n$ is a common divisor.

$a = n*n; b = 2*n$ so if there is any other common factor it will be a common factor of $2$ and $n$.

But as $n$ is odd there is no common divisor between $2$ and $n$ so the greatest common divisor is $n$.

This all hinges on understanding that

Lemma: $\gcd(c*m, d*m) = m\gcd(c,d)$

And therefore $\gcd(a,b) = \gcd(n^2, 2n) = n\gcd(2,n) = n*1 = n$ (as $n$ is odd).

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Which isn't to say what you did was wrong. It looks good and correct. Just a bit more complicated than necessary. $\endgroup$ – fleablood Feb 5 '17 at 21:17
  • $\begingroup$ If I'm following you correctly, from $Lemma : gcd((m)c, (m)d) = (m)gcd(c, d)$, if I let $gcd(c, d)=e$ and $m=\frac 1e$, it follows by definition that $gdc((m)c, (m)d) = gcd(\frac ce, \frac de) = \frac 1e gcd(c, d) = \frac ee = 1$, correct? $\endgroup$ – user409521 Feb 6 '17 at 19:12
  • $\begingroup$ I was assuming it was obvious from context that m was an integer. $\endgroup$ – fleablood Feb 6 '17 at 22:23
  • $\begingroup$ It was and your explanation is very clear, my last question in the comments was out of context, which I should have mentioned. Sorry if this does not abide by the rules of the site. I was just wondering if I could apply the lemma to other things. $\endgroup$ – user409521 Feb 6 '17 at 23:12
  • $\begingroup$ well, sure. but not to fractions which wouldn't make gcd meaningful. But it's a pretty basic result. Comes down to if $cm$ and $gm$ have factors in common either the will be a factor of $m$ or a common factor $c$ and $g$ which is obvious. $\endgroup$ – fleablood Feb 6 '17 at 23:55
0
$\begingroup$

Yes, $gcd(a, b) =b$ in this case, because as $n=2k$ then $b=4k|4k^2=a$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy