1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You might like to learn about the field of fractions of an integral domain :) $\endgroup$ – Shaun Mar 16 '14 at 9:30
  • 1
    $\begingroup$ @BarryCipra I edited my question. Is it correct now? $\endgroup$ – user103816 Mar 16 '14 at 10:23
  • 2
    $\begingroup$ @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'$. $\endgroup$ – Barry Cipra Mar 16 '14 at 10:58
  • 1
    $\begingroup$ Reminder: To be accepted. $\endgroup$ – user103816 Dec 2 '14 at 9:08
  • 2
    $\begingroup$ 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.) $\endgroup$ – Barry Cipra Dec 8 '14 at 19:40
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I understand your answer completely now, thank you. $\endgroup$ – user103816 Dec 1 '14 at 15:25
  • 1
    $\begingroup$ @user31782, great, glad to help. $\endgroup$ – Barry Cipra Dec 1 '14 at 15:31
2
$\begingroup$

$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}$$

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – user103816 Dec 9 '14 at 12:09
  • $\begingroup$ 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. $\endgroup$ – user 170039 Dec 10 '14 at 4:10
  • $\begingroup$ How about $a'<a$ and $b'<b$. This require different justification. $\endgroup$ – user103816 Dec 10 '14 at 10:50
  • $\begingroup$ @user31782: Is there still any doubt? $\endgroup$ – user 170039 Dec 11 '14 at 5:05
  • $\begingroup$ If I get it correctly then the case a′<a and b′<b is rejected because we reach at $a'=km'a'+kr'$. $\endgroup$ – user103816 Dec 11 '14 at 5:15
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ @anupam. thanks for tidying up. Doesn't seem that anyone particularly likes the proof though. Tom. $\endgroup$ – Tom Collinge Mar 16 '14 at 16:00
  • $\begingroup$ 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) $\endgroup$ – user103816 Dec 1 '14 at 15:20
1
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is nice.(+1) $\endgroup$ – user103816 Dec 9 '14 at 7:20
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user103816 Dec 2 '14 at 6:03
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Dec 18 '14 at 4:06
  • $\begingroup$ 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? $\endgroup$ – user103816 Dec 18 '14 at 7:50
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How can you say $\dfrac{a}{a'}=k=\dfrac{a}{b}$? $\endgroup$ – user103816 Mar 16 '14 at 9:03
  • 1
    $\begingroup$ 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'}$! $\endgroup$ – Emin Mar 16 '14 at 9:06
  • 1
    $\begingroup$ 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? $\endgroup$ – user103816 Mar 16 '14 at 9:57
  • 2
    $\begingroup$ Hmm, you are right! Then I have to modify a bit my answer. $\endgroup$ – Emin Mar 16 '14 at 9:59
  • 1
    $\begingroup$ How $a=a′k \implies a′=a\frac{1}{k}$? $\endgroup$ – user103816 Mar 16 '14 at 10:29

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.