Show that if $fd'=f'd $ and the pair $f, d $ are coprime, that is gcd($d,f $)=1, as is the pair $f',d' $, then $f=f' $ and $d=d' $.

This should be simple, but I couldn't verify it. Thanks in advance!

  • 1
    $\begingroup$ Are $f$ and $f'$ related in any way? What about $g$ and $g'$? If not, then I suggest for clarity not to use apostrophes to denote different variables. $\endgroup$ – Myridium Jun 8 '14 at 9:25
  • 1
    $\begingroup$ You need to assume all are positive else it is false. $\endgroup$ – Bill Dubuque Jun 8 '14 at 13:56


Use the Euclid's lemma to show that $f$ divides $f'$ and $f'$ divides $f$ and conclude that $f=f'$ and then $d=d'$.

  • $\begingroup$ Hi, I need help here. I tried as follows: if $a|f $ then $fd' =aqd'=f'd$. And so $a |f'd $ but $a $ cannot divide $f' $ so that we must have $a |d $, and $aqd'=f'ak $ so that $qd'=f'k $. But I get no where here... $\endgroup$ – Alexander Jun 8 '14 at 10:00
  • 1
    $\begingroup$ We have $f|f'd$ and $\gcd(f,d)=1$ so by the Euclid's lemma we have $f|f'$. Do the same thing to find $f'|f$. $\endgroup$ – user63181 Jun 8 '14 at 10:05
  • $\begingroup$ Understod how to do it now, thanks! $\endgroup$ – Alexander Jun 8 '14 at 10:16

Clearer with fractions $\, \begin{array}{c} (f,\,\ d)\,=\,1\\ (f',d')=1\end{array},\, \ \ \dfrac{f}d\, =\, \dfrac{f'}{d'}\ \Rightarrow\ \begin{array}{c} f\, =\, f'\\ d\, =\, d'\end{array}\,\ $ $\ \bbox[5px,border:1px solid #c00]{\text{ reduced fractions are }\textit{unique}}$

It suffices to show that the denominator of a reduced fraction $\rm\color{#0a0}{divides}$ every other denominator, since then we deduce that $\,d\mid d'$ and $\,d'\mid d,\ $ so $\,d = d',\,$ both being positive (cf. my comment).

But if $\ \color{#c00}{(a,b)= 1}\ \,$ & $\,\ \dfrac{A}B\, =\, \dfrac{a}b\, $ then $\, Ab = aB \ $ so $\ \color{#c00}{b\mid a}B\,\Rightarrow\,\color{#0a0}{b\mid B}\ $ by Euclid's Lemma.

Remark $\,\ $ Further: $\ \ \begin{align} A &\,=\, n\:\!a\\ B &\,=\, n\:\! b\end{align}\ \,$ by $\,\ \dfrac{A}a = \color{#0a0}{\dfrac{B}b} =: n\in\Bbb Z$

By $\,n\mid A,B,\:$ if $\ (A,B)=1\,$ then $\, n\mid 1\,$ so $\, n= \pm 1,\,$ i.e. reduced fractions are unique up to sign. Usually we normalize fractions by requiring positive denominators, cf. unit normalization.

Conversely, this denominator divisibility property implies Euclid's Lemma. So both are equivalent. Further, they are both equivalent to uniqueness of prime factorizations. As such, I call the fractional version unique fractionization. It is discussed further in various answers. If you know about ideals, then you may also find of interest various posts on denominator ideals (the denominator divisibility property is a special case of the fact that the set of denominators of a fraction forms an ideal, and $\,\Bbb Z\,$ is a PID, i.e. all ideals are principal, being generated by their least nonzero element).

Alternatively, we can replace use of Euclid's Lemma by a descent using the Division Algorithm, which yields a more direct (but less conceptual proof), e.g. see here.. This can be employed to give proofs of irrationality of square-roots using only the division algorithm, using a descent achieved by taking fractional parts of fractions, e.g. see this answer (based on a discussion with John Conway on irrationality proofs).

  • $\begingroup$ The trivial case $\,dd' = 0\,$ is left to the reader. $\endgroup$ – Bill Dubuque Dec 5 '19 at 4:57

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.