0

Suppose $a, b, n ∈ \Bbb{N}$. Use the Euclidean algorithm to prove that $\gcd(na, nb) = n \gcd(a, b)$.

I was going to try setting it up, by literally doing:

$nb = rna + k$ and so forth, but something tells me this is wrong.

Hanul Jeon
  • 27,376
Test
  • 61

1 Answers1

1

Hint: If you are to use the Euclidean Algorithm, perhaps you should start by writing $a = qb + r$, and continuing until you compute the $\gcd$ of $a$ and $b$. Once you have that list of equations in front of you, how would you turn that into a computation of the $\gcd$ of $na$ and $nb$?

rogerl
  • 22,399
  • That's what I'm trying to figure out. Firstly, what would the a, q, b be?

    My guess is, it's up to me to decide if a or b is bigger. so let's say a > b, then:

    na = q(nb) + r na = nq(b) + r

    or something lol, I'm not sure. Is this right?

     – Test Oct 17 '14 at 02:10
  • It doesn't matter. Write down the list of equations; if you want, you can assume $a>b$ (otherwise, just switch $a$ and $b$). Then as you say $a = qb+r$ means $na = q(nb) + nr$. Follow that through the entire list of equations that you use to compute $\gcd(a,b)$. – rogerl Oct 17 '14 at 02:13
  • But I'm literally lost there. I can't seem to figure out any computation to move onto the next step. I can't divide by n, or else I get r/n. subtracting doesn't seem like it'll do anything. can't think of a substitution. – Test Oct 17 '14 at 02:14
  • The E.A allows you to compute the gcd of any two integers. Once you multiply that entire chain of equations by $n$, the two integers whose gcd you are finding are then $na$ and $nb$. So the last nonzero remainder is their gcd. – rogerl Oct 17 '14 at 18:15