# Solution of $\frac{a}{b}=\frac{a'}{b'}$ if $a,b,a',b' \in \mathbb{N}$

Let $\dfrac{a}{b}=\dfrac{a'}{b'}$ , $a,b,a',b' \in \mathbb{N}$ s.t. $a$ and $b$ have no common factors.
How can we show that the only solution to this equality is $a'=na$ and $b'=nb$, $n$ is a natural number. I know that $a'=na$ and $b'=nb$ is a valid solution of equation-1, because $(an)b=(bn)a$. But how can we prove that this is the only solution?

What I have tried is this:

Version 1. We know the two fractions $\dfrac{a}{b},\dfrac{a'}{b'}$ are equal iff $ab'=a'b\tag{1}.$ Let $ab'=a'b=c$. Now, $a$ and $b$ have no common factors means that they are coprime, so we have, $a=p_1p_2\cdots p_m$ and $b=q_1q_2\cdots q_n$. $p's$ and $q's$ are prime numbers and no $p$ is equal to any $q$. Equation 1 becomes $$(p_1p_2\cdots p_m)b'=(b_1b_2\cdots b_n)a'$$ By the Fundamental theorem of Arithmetic, both the sides should have same prime numbers, so $b'$ should contain $(b_1b_2\cdots b_n)$ and $a'$ should contain $(p_1p_2\cdots p_m)$, i.e. $b'=r(b_1b_2\cdots b_n)=rb$ and $a'=(p_1p_2\cdots p_n)s=sa$, where $r,s \in \mathbb{N}$. Now equation 1 becomes, $a(rb)=(sa)b$. This leaves the only possibility, $r=s$.

Version 2. The idea is basically the same as of version 1, but now I use Euclid's lemma in place of FTA. We know the two fractions $\dfrac{a}{b},\dfrac{a'}{b'}$ are equal iff $ab'=a'b\tag{1}.$ Let $ab'=a'b=c$. $a$ and $b'$ are the factors of $c$, so both of them divide $c$, i.e. $a|c$ and $b'|c$. Now $a|c \implies a|{(a'b)}$, by Euclid's lemma, $a$ divides at least one of $a'$ and $b$, but we know that $a$ doesn't divide $b$, so $a$ has to divide $a'$.

Similarly we can show that $b$ divides $b'$. So we have $a'=\alpha a$ and $b' = \beta b$, where $\alpha, \beta \in \mathbb{N}$. Substituting these in equation 1 gives $\alpha = \beta$.

Question

1. Is my method correct?

2. Is there any other method to prove that $a'=na$ and $b'=nb$ is the only solution of $\dfrac{a}{b}=\dfrac{a'}{b'}$; If yes then please explain.

3. Also if $a$ and $b$ have common factor then for what condition there does not exist any $n$ s.t. $a'=na$ and $b'=nb$ where $n$ is a natural number. E.g. $\dfrac 39 = \dfrac 26$

P.S: I've just improved my question. Barry's comment points a crucial error in my previous proof. I needed to justify $a|a'$ and $b|b'$. In previous proof I proceeded with proof by contradiction. The proof by contradiction was ok, but unnecessary, so I've replaced it with a direct proof. At the time of asking the question I lacked the knowledge of some introductory number theory concepts. Now I've learned them and soon I will ask in comments for further clarifications. Thank you.

• You might like to learn about the field of fractions of an integral domain :) Mar 16, 2014 at 9:30
• @BarryCipra I edited my question. Is it correct now? Mar 16, 2014 at 10:23
• @anupam, yes, your edit makes the statement true. But your method for proving it is not correct. In your proof, you are assuming that $a'$ and $b'$ are multiples of $a$ and $b$, so all your proof shows is that they can't be different multiples. You still need to show that $a\mid a'$ and $b\mid b'$. Mar 16, 2014 at 10:58
• Reminder: To be accepted. Dec 2, 2014 at 9:08
• The boxed text has a number of typos. Among other things, it ends with the Greek letter beta which, unless I missed it, appears nowhere else. (Incidentally, on my screen at least, the characters $a$ and $\alpha$ are virtually indistinguishable.) Dec 8, 2014 at 19:40

The proof boils down to a little lemma:

If $\gcd(a,b)=1$ and $a\mid bc$, then $a\mid c$.

Here's how it applies:

\begin{align} {a\over b}={a'\over b'}&\implies ab'=ba'\\ &\implies a\mid ba'\\ &\implies a\mid a'\qquad\text{(by the lemma)}\\ &\implies a'=an\\ &\implies ab'=ban\\ &\implies b'=bn \end{align}

One way to prove the lemma is by invoking the theorem that if $\gcd(a,b)=1$, then $am+bn=1$ for some integers $m$ and $n$. Combining this with $bc=ak$ (based on the assumption $a\mid bc$), we have

\begin{align} am+bn=1&\implies amc+bnc=c\\ &\implies amc+nak=c\\ &\implies a(mc+nk)=c\\ &\implies a\mid c \end{align}

Added 12/9/14 (in response to OP's edits): Version 1 looks fine to me (except the $b_i$'s should be $q_i$'s, or vice versa), but Version 2, I'd say, makes too liberal a use of Euclid's lemma, which lets you say $a\mid a'b$ and $a\not\mid b$ implies $a\mid a'$ only if $a$ is prime. What you need to say in that proof is that $a\mid a'b$ and $(a,b)=1$ implies $a\mid a'$. The hypothesis $(a,b)=1$ is much stronger than $a\not\mid b$. Basically a correct version of Version 2 amounts to the proof in my original answer above.

• I understand your answer completely now, thank you. Dec 1, 2014 at 15:25
• @user31782, great, glad to help. Dec 1, 2014 at 15:31

$a'=ma+r, b'=nb +s\implies \dfrac{a'}{b'}=\dfrac{ma+r}{nb+s}$

\begin{align} \dfrac{a}{b}= \dfrac{ma+r}{nb+s} & \implies a(nb+s)=b(ma+r)\\ & \implies a\mid (ma+r)\land b\mid (nb+s) \\ & \implies r=s=0 \\ & \implies a'=ma, b'=nb \\ & \implies\dfrac{a}{b}= \dfrac{ma}{nb}\\ & \implies m=n\end{align}

• 1. How would we justify that $a'>a$ and $b'>b$? 2. You shouldn't be saying $r=s=0$, rather $r=ka$ and $s=k'b$, so the remainders have to be 0 and hence a|a' and b|b'. (+1) Dec 9, 2014 at 12:09
• I don't understand the second part of your comment. We can say that $r=s=0$ because of the inequalities $0\leq r <a$ and $0\leq s<b$ by the Division Algorithm. And for the first part of your comment I would say that since $a,b,a',b,\in \mathbb{N}$ if $a'>a$ and $b<b'$ then we get $a'b>ab'$ and similarly for other cases.
– user170039
Dec 10, 2014 at 4:10
• How about $a'<a$ and $b'<b$. This require different justification. Dec 10, 2014 at 10:50
• @user31782: Is there still any doubt?
– user170039
Dec 11, 2014 at 5:05
• If I get it correctly then the case a′<a and b′<b is rejected because we reach at $a'=km'a'+kr'$. Dec 11, 2014 at 5:15

As the saying goes, just when you think you have life's answers they change the questions ! (this was posted before the caveat about using rational real numbers)

For any non-zero $a, a’, b, b’$ the ratios can be expressed as non-zero real numbers $R_a$ and $R_b$, so that $b’ = R_b \cdot b$ and $a’ = R_a \cdot a$

$a'/b' = a/b = \dfrac{R_a\cdot a}{R_b\cdot b}.$

So, $\dfrac{a}{b} = \dfrac{R_a}{R_b}\cdot \dfrac{a}{b}$.

So, $\dfrac{R_a}{R_b} = 1$ and therefore $R_a = R_b$.

If you chose, you can now look only at integer values of $R_a$ and $R_b$, so that $Ra = Rb = k$

and $a’ = k\cdot a$ and $b’=k\cdot b$

• @anupam. thanks for tidying up. Doesn't seem that anyone particularly likes the proof though. Tom. Mar 16, 2014 at 16:00
• The only problem with your question is that you do not show how b|b' and a|a'. I did the same mistake in the original version of my question. Nonetheless I appreciate your answer.(+1) Dec 1, 2014 at 15:20

We use proof by contradiction. We have $\frac{a}{b}=\frac{a'}{b'}$, where $a$ and $b$ are relatively prime.

Suppose that $\frac{a'}{a}$ is not an integer, i.e. in simplest forms, it is in the form $\frac{p}{q}$ where $q>1$. Then $(a)(\frac{p}{q})$ and $(b)(\frac{p}{q})$ are both integers (equal to $a'$ and $b'$ respectively).

Since $p$ is relatively prime to $q$, $a$ and $b$ must both be divisible by $q$, contradiction as $q>1$ but $a$ and $b$ are relatively prime.

• This is nice.(+1) Dec 9, 2014 at 7:20

This is equivalent to Euclid's Lemma (EL), e.g. see the standard proof in Barry's answer However, it can also be proved directly using the foundation of EL, i.e. the (Euclidean) Division algorithm, used in the proof below to take the (unique!) fractional part $\rm\,r/B\in [0,1)\,$ of a fraction $\rm\,A/B,\,$ i.e.

by the Division Algorithm $\rm\ A = q B + r,\,\ 0\le r < B\!\! \overset{\large\ \ \times\ B^{-1}}\implies\, \dfrac{A}B = q + \dfrac{r}B,\,\ 0\le \dfrac{r}B < 1$

Unique Fractionization $\$ The least denominator $\rm\:B\:$ of a fraction divides every denominator.

Proof $\rm\displaystyle\ \ \frac{A}B = \frac{C}D\ \Rightarrow\ \frac{D}B = \frac{C}A \:.\$ Taking fractional parts $\rm\displaystyle\ \frac{b}B = \frac{a}A\$ where $\rm\,\ 0 \le b < B.\$ But

$\rm\displaystyle\ \:B\nmid D\ \Rightarrow\ b\ne 0\ \Rightarrow\ \frac{A}B = \frac{a}b\ \$ contra leastness of $\rm\:B.\:$ Hence $\rm\ B\mid D.\quad$ QED

Further $\rm\,B\mid D\,\Rightarrow\, n = \dfrac{D}B = \dfrac{C}A\,\Rightarrow\,\begin{array}{}\rm nA = C\\ \rm nB = D\phantom{{I_I}^I}\end{array}\!\!\!\!$ In particular, if $\rm\,C,D\,$ are coprime then $\rm\,n=1\,$ therefore $\rm\,C,D = A,B,\,$ i.e. a reduced fraction is in least terms, which yields the sought result.

• Your answer is too concise for me to understand.1. Why does "the least least denominator B of a fraction divide every denominator"? 2. How $\rm\displaystyle\ \frac{b}B = \frac{a}A\$? What are $a$ and $b$? Moreover can we use this approach to prove Euclid's theorem directly, without invoking Bezout's identity? Would you elaborate your answer. Dec 2, 2014 at 6:03
• @user31782 1. That's what the proof shows. 2. Bt taking fractional parts, e.g $\,\dfrac{5}3 = \dfrac{20}{12}\Rightarrow\dfrac{2}3 = \dfrac{8}{12}$. 3. Yes, as I said, it's equivalent to Euclid's Lemma. Dec 18, 2014 at 4:06
• 1. Which proof? UF's proof? but how does it show, "the least denominator B of a fraction divides every denominator"? 2. What do we mean by contra leastness? Are we assuming that A/B is already in its lowest terms, i.e A and B are coprime to each other. Even if they are then what's wrong with A/B=a/b? If A and B are not coprime then 5/20=3/12 gives $5\neq n3$ and $20 \neq n 12$. 3. Can we prove Euclid's lemma without using both UF and Bezout's identity? Dec 18, 2014 at 7:50

I think your method is correct.

I have an other method: Let $\frac{a}{b}=\frac{a'}{b'}$. From that we can write $\frac{a}{a'}=\frac{b}{b'}$, than there exist a rational number $k$ s.t. $\frac{a}{a'}=\frac{b}{b'}=k$, so $a=a'k$ and $b=b'k$ or $a'=a\frac{1}{k}$ and $b'=b\frac{1}{k}$ or for $n=\frac{1}{k}$ we finally have $a'=na$ and $b'=nb$.

Updated: If (a,b)=1, and a'>a, b'>b, than we have the following: Suppose that $\frac{a}{b}=\frac{a'}{b'}$. From $\frac{a}{b}=\frac{a'}{b'}$ and (a,b)=1, we conclude that (a',b')=n where n is natural. Now, from (a',b')=n we can write a'=pn and b'=qn where (p,q)=1.So we have (p,q)=(a,b)=1 and $\frac{a}{b}=\frac{p}{q}$ ($\frac{a}{b}=\frac{a'}{b'}=\frac{pn}{qn}=\frac{p}{q}$)which can be true iff a=p and b=q. So finally we have that a'=na and b'=nb must be the only solution.

• How can you say $\dfrac{a}{a'}=k=\dfrac{a}{b}$? Mar 16, 2014 at 9:03
• I suppose you've wanted to write $\frac{a}{a'}=k=\frac{b}{b'}$. We know that from $\frac{a}{b}=\frac{a'}{b'}$ we can write $\frac{a}{a'}=\frac{b}{b'}$!
– Emo
Mar 16, 2014 at 9:06
• You first wrote "$\frac{a}{b}=\frac{a'}{b'}=k$". So $k=\frac{a}{b}$ isn't it. Then you say $\frac{a}{a'}=k$. Am I correct? Mar 16, 2014 at 9:57
• Hmm, you are right! Then I have to modify a bit my answer.
– Emo
Mar 16, 2014 at 9:59
• How $a=a′k \implies a′=a\frac{1}{k}$? Mar 16, 2014 at 10:29