# Math Help - Greatest common divisor Proof (very hard!)

1. ## Greatest common divisor Proof (very hard!)

I can't figure out how to prove the following:

Let $p \in N$ be a prime and $c \in Z$. Show that either $p | c$ or $gcd(p,c)=1$.

Any help is appreciated.

2. Originally Posted by Roam
Let $p \in N$ be a prime and $c \in Z$. Show that either $p | c$ or $gcd(p,c)=1$.
Suppose that $k=\gcd(p,c)>1$.
So $k|p~\&~k|c$. But $p$ being prime implies $k=1\text{ or }k=p$.
What does that tell you?

3. Originally Posted by Plato
Suppose that $k=\gcd(p,c)>1$.
So $k|p~\&~k|c$. But $p$ being prime implies $k=1\text{ or }k=p$.
What does that tell you?
Is that meant to be a contradiction to show that the greatest common divisor of (p,c) is 1 and the k cannot be greater?

But $p$ being prime implies $k=1\text{ or }k=p$.
How do we know that p is a divisable to c (so it can't be the gcf(p,c))?

4. Originally Posted by Roam
Is that meant to be a contradiction to show that the greatest common divisor of (p,c) is 1 and the k cannot be greater?
How do we know that p is a divisable to c (so it can't be the gcf(p,c))?
You need lessons in basic logic.
The point is that either $k=\gcd(p,c)=1 \text{ or } k=\gcd(p,c)>1$.
Now if $k=\gcd(p,c)=1$ we are done with the proof.
So suppose that $k=\gcd(p,c)>1$ then $k \not= 1$.
Thus this means that $k=p$ so $p|c$.