# Thread: Greatest common divisor Proof (very hard!)

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

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

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

Any help is appreciated.

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

3. Originally Posted by Plato
Suppose that $\displaystyle k=\gcd(p,c)>1$.
So $\displaystyle k|p~\&~k|c$. But $\displaystyle p$ being prime implies $\displaystyle 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 $\displaystyle p$ being prime implies $\displaystyle 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 $\displaystyle k=\gcd(p,c)=1 \text{ or } k=\gcd(p,c)>1$.
Now if $\displaystyle k=\gcd(p,c)=1$ we are done with the proof.
So suppose that $\displaystyle k=\gcd(p,c)>1$ then $\displaystyle k \not= 1$.
Thus this means that $\displaystyle k=p$ so $\displaystyle p|c$.