Prove that $\text{gcd}(a, p) = 1 \implies p\nmid a $ is true.

Question

This is one direction of the biconditional in part b of this proposition:

Prove that for every prime, $p$, and for all natural numbers $a$, (a) $\text{gcd}(a,p)=p$ iff $p\mid a$ (b) $\text{gcd}(a,p)=1$ iff $p\nmid a$.

So far for my proof of part b, I have that:

Proposition Part (b): $\text{gcd}(a, p) = 1 \implies p\nmid a$.

Proof: Let us consider one direction of the bi-conditional proposition: $p\nmid a \implies \text{gcd}(a, p) = 1$. Let $b$ be a common divisor of $a$ and $p$. It is enough to show that $b = 1$. We know that $p$ is prime, so if $b \mid p, b = 1$ or $b = p$. If $b = p$, then $p\mid a$ because $b$ is a common divisor of both $a$ and $p$. This is a contradiction, because we assumed that $p \nmid a$. Therefore, $b = 1$.

Now I just need the proof of the other direction; please help me out!

Answer 1

If you wish to prove that $[\gcd(a,p)=1]\Rightarrow [p\nmid a]$ you could equivalently prove $[p\mid a]\Rightarrow [\gcd(a,p)\neq1]$, which I think you will find easier. If you know that $p\mid a$ then both $p$ and $a$ are divisible by $p$, so the $\gcd(a,p)=p$.

Answer 2

If $p|a$ and also $p|p$ $\Rightarrow p|gcd(a,p)$ as $gcd(a,p)=ax+py, x,y\in \mathbb{Z}$ $\rightarrow \leftarrow $ because $p\not \mid 1$

Answer 3

$p|p$ and if $p|a$ then $p$ is a common divisor of $a$ and $p$. But the greatest common factor is $1$ so this is impossible.

This direction was meant to be trivial. For positive integers $a|b \iff \gcd(a,b) = a$. If $a|b$ then its a common divisor but nothing larger than $a$ divides $a$. If $\gcd(a,b) = a$ then $a|b$.

Answer 4

Hint $ $ note that $\ p = (a,p) \iff p\mid (a,p) \iff p\mid a,p \iff p\mid a,\, $ so $(a)$ is true.

Negating above $\,p\nmid a\iff (a,p)\neq p\iff (a,p)=1,\, $ by $\, (a,p)\mid p,\, $ so $(b)$ is true.