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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .