0
$\begingroup$

I'm struggling with how to prove that the $\gcd(n,m)=m$?

It is given that $m$ is positive and $m|n$… But isn't that the proof already? If $m$ divides $n$ and $m$ divides itself (of course) then how can I formulate this properly?

Thanks!

$\endgroup$
  • $\begingroup$ A gcd of two numbers $m,n$ is a number $h$ such that $h\mid m$, $h\mid n$ and, for all $k$ such that $k\mid m$ and $k\mid n$, $k\mid h$ as well. Since your candidate is already a common divisor of $m$ and $n$ by hypothes, you only need to argument that any other $k$ such that $k\mid m$ and $k\mid n$ divides it (which is not hard at all, but it should be done). $\endgroup$ – user228113 Nov 6 '17 at 11:29
5
$\begingroup$

Let $d$ be a natural number which divides $m$. Since $m\mid n$, it follows that $d\mid n$. Therefore$$\{\text{divisors of }m\}\subset\{\text{divisors of }n\},$$and so\begin{align}\{\text{common divisors of }m\text{ and }n\}&=\{\text{divisors of }m\}\cap\{\text{divisors of }n\}\\&=\{\text{divisors of }m\}.\end{align}Therefore,$$\gcd(m,n)=\text{greatest divisor of }m=m.$$

$\endgroup$
0
$\begingroup$

Use that for every number $a$ for which $a|n$ and $a|m$, we conclude that $a|m$ (trivially), which makes $m$ the gcd. That is what the definition says. The proof follows very directly indeed.

$\endgroup$
0
$\begingroup$

The key point here is that in absolute value there is no bigger divisor of m than m. Thas why its the greates common divisor.

$\endgroup$
-1
$\begingroup$

This is proper way to formulate this problem. $m \mid n$, thus there is an integer $k$ such that $n=mk$, then

$$\gcd(m, n)=\gcd(m, mk)=m \ \underbrace{\gcd(1, k)}_{=1}=m$$

$\endgroup$
  • 2
    $\begingroup$ And how do you know that $\gcd(m,mk)=m\gcd(1,k)$? $\endgroup$ – José Carlos Santos Nov 6 '17 at 13:40

Your Answer

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

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