Let $a,b,c,d$ be positive integers. Suppose that $$\frac cd=\frac ab.$$ I want to prove that if $a$ and $b$ are relative primes, then $c/a=d/b$ is an integer.

That is, the only way a fraction can be represented in a way other than its simplest form is to multiply both the numerator and the denominator by the same integer.

I’m a little ashamed to seek help, because the statement seems so trivial, yet I’m stuck with a rigorous proof. Any input would be appreciated.

  • 2
    $\begingroup$ I think this is backwards, and you should have $c/a$: Take $a = 1, b = 2, c = 2, d = 4$ for a counterexample. $\endgroup$ – user296602 Feb 4 '16 at 0:24
  • $\begingroup$ @T.Bongers You’re right, correction made. $\endgroup$ – triple_sec Feb 4 '16 at 0:26
  • $\begingroup$ If a and b are relative primes then c =ka and d = kb and your integer is k. $\endgroup$ – Piquito Feb 4 '16 at 0:30
  • 1
    $\begingroup$ @Piquito that's what the OP is trying to prove. That the only way to write a/b is as ak/bk. $\endgroup$ – fleablood Feb 4 '16 at 0:31

Let's restate the question without fractions. We want to show that if $bc = ad$ and $\gcd(a, b) = 1$, then there is some $k \in \mathbb Z$ such that $c = ak$ (and thus $d = bk$).

Indeed, using Bezout's Identity, we know that there exist $u,v \in \mathbb Z$ such that: $$ au + bv = 1 $$ Multiplying through by $c$, we get: $$ c = acu + (bc)v = acu + (ad)v = a\underbrace{(cu + dv)}_{k \in \mathbb Z} $$ as desired.

  • $\begingroup$ Thank you, but I’m not familiar with Bezout’s identity (even though it is apparently very elementary). I have presented a little more complicated, but (for me) more transparent, proof based on the fundamental theorem of arithmetic (which I’m more comfortable with). $\endgroup$ – triple_sec Feb 4 '16 at 0:50

I think I got it. By the fundamental theorem of arithmetic, each $x\in\{a,b,c,d\}$ can be represented as $$x=\prod_{i=1}^k p_i^{n^x_i},$$ where $(p_i)_{i=1}^k$ are distinct primes, $(n_i^x)_{i=1}^k$ are non-negative integers, and $k\in\mathbb N$. Since $a$ and $b$ are relative primes, $n_i^a n_i^b=0$ for each $i\in\{1,\ldots,k\}$ (otherwise both $a$ and $b$ would be divisible by $p_i$).

Now, $c/a=d/b$ means that $$\prod_{i=1}^k p_i^{n^c_i-n^a_i}=\prod_{i=1}^k p_i^{n^d_i-n_i^b}.$$ By the uniqueness of prime factorizations (which holds also when the exponents are potentially non-positive), one must have $$n^c_i-n_i^a=n^d_i-n^b_i\quad\forall i\in\{1,\ldots,k\}.$$ There are two cases. If $n_i^a>0$, then $n_i^b=0$, so that $n_i^c-n_i^a=n_i^d\geq 0$. If $n_i^a=0$, then $n_i^c-n_i^a=n_i^c\geq 0$. The point is that, in each case, $\Delta_i\equiv n_i^c-n_i^a\geq 0$. Therefore, $$w\equiv\prod_{i=1}^kp_i^{\Delta_i}$$ is a positive integer, and, by construction, $c/a=w$.


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.