0
$\begingroup$

This question already has an answer here:

Let a and b be positive integers. If c = gcd(a,b), prove that gcd(a/c,b/c) = 1

*Note that a/c and b/c are integers.

So I know that c|a and c|b and that a gcd of 1 implies that the resulting integers are relatively prime. I know this must be within a simple definition, however I am new to these type of proofs and I don't know how to start or conceptualize this one. Any help would be appreciated.

$\endgroup$

marked as duplicate by Martin R, user99914, Ethan Bolker, Matthew Conroy, Namaste Feb 7 '18 at 22:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Thank you for your replies. I apologize for the duplicate as I did not find the other question. I have a much better grasp on the proof now. $\endgroup$ – C.Math Feb 8 '18 at 2:16
2
$\begingroup$

$c=\gcd(a,b)$ is the positive generator of the ideal$(a,b)\subset \mathbf Z$. Actually, it is the smallest positive element in this ideal. So there exist integers $u, v$ such that $$ ua+vb=c\tag{Bézout's identity}. $$ If we set $a'=\dfrac ac$, $\;b'=\dfrac ab$, Bézout's identity becomes $\; ua'c+vb'c=c$, or, simplifying by $c$: $$ua'+vb'=1,$$ which shows $1=\gcd(a',b')$.

$\endgroup$
2
$\begingroup$

Hint: $(a,b)$ divides $c$ if and only if there exist integers $x$ and $y$ such that $ax + by = c$.

$\endgroup$
  • $\begingroup$ That's not quite true. The gcd is just the minimal such $c$. $\endgroup$ – Ravi Feb 7 '18 at 21:05
1
$\begingroup$

Let $n=\gcd(a/c,b/c)$. By definition, $n |a/c$ and $n| b/c$. That is, there exist $k_{1},k_{2}\in \mathbb{Z}$ such that $$a/c=nk_{1},\quad b/c=nk_{2}.$$ Therefore, $a=nck_{1}$ and $b=nck_{2}$. Hence, $nc|a$ and $nc|b$. Again by definition of the greater common divisor, $$nc|\gcd(a,c)=c,$$ so $n=1$ or $n=-1$.

By convention, we always take $\gcd$ to be positive, so $n=1$.

$\endgroup$

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