# If c = gcd(a, b), prove that gcd( a/c , b/c ) = 1 [duplicate]

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.

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

• 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. – C.Math Feb 8 '18 at 2:16

$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')$.
Hint: $(a,b)$ divides $c$ if and only if there exist integers $x$ and $y$ such that $ax + by = c$.
• That's not quite true. The gcd is just the minimal such $c$. – Ravi Feb 7 '18 at 21:05
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$.