How do I prove that "If prime p does not divide natural number m, then gcd(p,m) = 1" I am having a problem with this. 
If prime p does not divide natural number m, then gcd(p,m) = 1
I had to use this for my another proof and because I thought it was quite intuitive, I just assumed this is true and used it for my proof but then I was told that I have to prove it too. But the problem is I can't figure out how I should write a proof for this formally. 
Any help would be appreciated! Thank you

Your proof might be different depending on your definition of GCD.  The definition I prefer is the following: a GCD of two integers $m,p$ is a number $d$ which divides $m$ and $p$, and which has the property that if $e$ is an integer dividing $m$ and $p$, then $e$ divides $d$.  A GCD of two nonzero integers exists, is nonzero, and is unique up to sign, so it makes sense to say the GCD (that is, the positive one).
Since $d = \textrm{GCD}(m,p)$ is necessarily a divisor of $p$, your choices for $d$ are $1$ and $p$.  But also $d$ must divide $m$, so you cannot have $d = p$.  Therefore, the GCD is $1$.
