# How to prove that the $\gcd(n,m)=m$?

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!

• 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). – user228113 Nov 6 '17 at 11:29

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.$$

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.

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.

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$$

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