2
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ So basically, I should use the contrapositive to prove this statement? $\endgroup$ – Chimin Jan 3 at 1:10
  • $\begingroup$ @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. $\endgroup$ – ItsJustASeriesBro Jan 3 at 1:12
  • $\begingroup$ not exactly following how this proves that [gcd(a,p)=1]⇒[p∤a] $\endgroup$ – Chimin Jan 3 at 1:27
  • $\begingroup$ @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. $\endgroup$ – ItsJustASeriesBro Jan 3 at 1:31
  • $\begingroup$ Yes; is it enough to say: $\endgroup$ – Chimin Jan 3 at 1:32
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note $\,(a,b)$ denotes $\,\gcd(a,b),\,$ standard notation in number theory. $\endgroup$ – Bill Dubuque Jan 3 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.