1
$\begingroup$

I'm a physicist taking elementary number theory so while I've had a class discussing proofs in the past, my experience with rigorous mathematical proofs is very limited. I've got a problem and I'm not sure how many things I need to show to adequately complete it. The question is:

Prove that if $d$ is a common divisor of $a$ and $b$, then $d = gcd(a,b)$ if and only if $gcd(a/d,b/d) = 1$.

The math itself is very simple. But what I actually need to show is less clear to me. I know iff statements need to be shown both ways ($A\Rightarrow B$ and $B\Rightarrow A$ since it's essentially an equality statement), so would I need to show both directions for that and THEN assume 'if $d$ is a common divisor, then...'? Or should I start with that assumption and do something extra later on?

Much appreciation for the help.

$\endgroup$
2
  • $\begingroup$ In this case, every situation we are considering has $d$ being a common divisor of $a$ and $b$. With that knowledge, we wish to show that $d=gcd(a,b)$ implies $gcd(a/d,b/d)=1$ as well as showing that $gcd(a/d,b/d)=1$ implies $d=gcd(a,b)$. Note that these statements need not necessarily imply one another in the case that $d$ is not a common divisor of each. $\endgroup$ – JMoravitz Feb 4 '17 at 21:15
  • $\begingroup$ Very well explained. Thanks for your quick response. $\endgroup$ – cybenddragon Feb 4 '17 at 21:29
2
$\begingroup$

You can prove a proposition of the form 'If A then (B if and only if C)' by doing these two things: First assume A and B and prove C. Then assume A and C and prove B.

$\endgroup$
1
  • $\begingroup$ That makes sense. Thank you very much. $\endgroup$ – cybenddragon Feb 4 '17 at 21:28
0
$\begingroup$

Show that $\gcd(a, b)$ $=$ $d$ if and only if $\gcd(a/d, b/d)$ $=$ $1$

What is the gcd? The gcd stands for greatest common divisor. Notice the word in bold. So the gcd of $a$ and $b$ is $d$ means there is no other divisor $x$ in common with $a$ and $b$, that is $x>d$. Therefore since $d$ is the gcd of $a$ and $b$, $a/d$ and $b/d$ must be relatively prime (their gcd is $1$). Otherwise, the gcd would be $hd$ with $h$ $>$ $1$. Hence $hd$ $>$ $d$.

$\endgroup$

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.