3

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

Bill Dubuque
  • 272,048
Meer
  • 341
  • 2
    One way to think about it: the greatest common divisor of $m$ and $p$ is in particular a divisor of both $m$ and $p$. Since $p$ is prime, your only choices are $1$ and $p$, and it can't be $p$. – D_S Mar 23 '16 at 04:21

3 Answers3

2

Hint:

  • By definition, the gcd of two numbers divides each of them.

  • By definition, a number is prime iff the only numbers dividing it are $1$ and itself.

Do you see how to go from here?

Noah Schweber
  • 245,398
0

p is prime, p the set of divisors of p is {1,p} 1 divides ever number. If p does not divide m, then only divisor they have is common is 1.

Doug M
  • 57,877
0

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

D_S
  • 33,891