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

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

• The other direction is trivial. If $\gcd(a,p) =1$ then no factor of $p$ divides $a$. In particular $p\not \mid a$. – fleablood Jan 3 '19 at 1:39

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

• So basically, I should use the contrapositive to prove this statement? – Chimin Jan 3 '19 at 1:10
• @Chimin You do not have to, but it should be a reflex to check the contrapositive to see if it is easier whenever you are working on if and only if statements. – ItsJustASeriesBro Jan 3 '19 at 1:12
• not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a] – Chimin Jan 3 '19 at 1:27
• @Chimin So you are familiar with the logical equivalence between a statement and its contrapositive? If I prove the contrapositive then the original statement has also been proven. And the point is that if you get to assume that $p\mid a$ (which is exactly the hypothesis of the contrapositive) then it is immediately apparent that $\gcd(a,p)\neq 1$. The fact that we can further show the exact value of $\gcd(a,p)$ is sort of just icing on the cake. – ItsJustASeriesBro Jan 3 '19 at 1:31
• Yes; is it enough to say: – Chimin Jan 3 '19 at 1:32

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

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

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.

• Note $\,(a,b)$ denotes $\,\gcd(a,b),\,$ standard notation in number theory. – Gone Jan 3 '19 at 2:21