# How to show that $p \nmid a \Rightarrow \gcd(p,a)=1$?

How to show that $p \nmid a \Rightarrow \gcd(p,a)=1$?

If we have canonical representations of $p= q_1^{b_1} \cdots q_n^{b_n}$ and $a= r_1^{c_1} \cdots r_k^{c_k}$, then because $p \nmid a$, $q_i \neq r_j$ for all $i=1, \dots, n$ and $j=1, \dots k \Rightarrow \gcd(p,a)=1$.

-
This problem is poorly stated. It's true that if $p = q_1^{b_1}\dots q_n^{b_n}$ and $a=r_1^{c_1}\dots r_k^{c_k}$ with $q_i \neq r_j$ then gcd$(p,a)=1$. But it's not true that if $p$ doesn't divide $a$ then gcd$(p,a)=1$. For instance, 6 doesn't divide 10 but gcd$(6,10)=2$. Ask yourself, is it possible for gcd$(q_i,r_j)>1$? – Dimitrije Kostic Nov 19 '11 at 17:54

I think the problem must have come from a source that assumes $p$ is prime.
Suppose $\gcd(a,p)=m\ne 1$. Then $m$ is a common divisor of $a$ and $p$. That means $m$ divides $a$ and $m$ divides $p$. If $m$ divides $p$ and $p$ is prime, then $m = \text{either }1\text{ or }p$. We've ruled out $1$, so $m=p$. If $m$ divides $a$ and $m=p$, then $p$ divides $a$. But you ruled that out at the beginning.