Show that if $fd'=f'd $ and the pairs $f, d $ and $f',d' $ are coprime, then $f=f' $ and $d=d' $.

Solution 1:

Hint

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

Solution 2:

Another solution, using Corollary 31.4 from CLRS:

For all integers a and b and any nonnegative integer n, $ (an, bn) = n*(a, b); $

$ (f, d) = 1 => (ff', df') = f' $ (multiplying by f')

$ (f', d') = 1 => (ff', d'f) = f $ (multiplying by f)

Now it's easy:

$ (ff', df') = (ff', d'f) => f' = f $ (because df' = d'f)

$ df' = df = d'f => d' = d $

Solution 3:

Clearer by 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]{\begin{align}&\bf{Unique\ Fractionization}\\ &\!\text{ reduced fractions are }\textit{unique}\end{align}}$

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: $\ \ \bbox[5px,border:1px solid #c00]{\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). So reduced fraction uniqueness boils down to the principality of an ideal.

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).