Suppose that $\mathbf{a}$ and $\mathbf{b}$ are relatively prime, and that $\mathbf{c}$ and $\mathbf{d}$ are relatively prime. Prove that $\mathbf{ac = bd}$ implies $\mathbf{a = d}$ and $\mathbf{b = c}$.

I'm a little stuck on this. I know that by definition $\mathbf{gcd(a,b) = 1}$ and $\mathbf{gcd(c,d) = 1}$ for $\mathbf{ a,b,c,d \in}$ $\Bbb{N}$.

Thus $$\mathbf{\alpha a + \beta b = 1}$$ $${ \alpha, \beta \in} \Bbb{Z}$$ and $$\mathbf{\gamma c + \delta d = 1 }$$ $${\gamma, \delta \in} \Bbb{Z}.$$

By manipulating these equations using the equality given, I've come up with the following equations: $$\mathbf{b(\alpha d + \beta c) = c}$$ $$\mathbf{a(\alpha d + \beta c) = d}$$ $$\mathbf{d(\gamma b + \delta a) = a}$$ $$\mathbf{c(\gamma b + \delta a) = b}$$

If I can show that $\mathbf{\alpha d + \beta c = 1}$ and $\mathbf{\gamma b + \delta a = 1}$ then I'll be done, but I'm not sure how to do this, or if this is even the best approach to prove the implication.


I suppose $a,b,c,d >0$ here, as it's certainly not true otherwise (take distinct primes $p,q$ and set $a=p$, $b=q$, $c=-q$, $d=-p$. It's a lot simpler than you're making it. I'll give you a hint...

$$ac=bd \Rightarrow a \mid bd \Rightarrow a \mid d\; \text{since}\; (a,b)=1$$ $$ac=bd \Rightarrow d \mid ac \Rightarrow d \mid a\; \text{since}\; (c,d)=1.$$

Thus we have $a \mid d$, $d \mid a$ so $a= \pm d$. But both are positive...

  • $\begingroup$ oh wow, yeah that makes a lot of sense. I always over-complicate these types of division proofs. and yes, $\mathbf{ a,b,c,d \in} \Bbb{N}$ so they're positive $\endgroup$ – Steven Apr 11 '14 at 15:40
  • $\begingroup$ Sorry, I missed that line! $\endgroup$ – ah11950 Apr 11 '14 at 15:40
  • $\begingroup$ Or also, $\frac ab=\frac dc$, since both are irreducible fractions... $\endgroup$ – chubakueno Apr 11 '14 at 15:54
  • $\begingroup$ @chu It does follow from the uniqueness of reduced fractions, but that result is less well-known than Euclid's Lemma. Both are equivalent to unique factorization. $\endgroup$ – Bill Dubuque Apr 11 '14 at 16:11
  • $\begingroup$ @BillDubuque Yes. I was assuming that the uniqueness of reduced fractions was an already accepted fact. But obviously given the level of the question, it is better to prove it explicitly. $\endgroup$ – chubakueno Apr 11 '14 at 20:31

Another direct way is to work with prime factorizations:

$\prod_{i=1}^r p_i^{a_i+c_i}=ac=bd=\prod_{i=1}^r p_i^{b_i+d_i}$,

so, for all $i=1,\ldots,r$, it must hold that $a_i+c_i=b_i+d_i$. From this you can easily derive $a_i=d_i$ and $b_i=c_i$ when you consider the constraints $a_i>0\implies b_i=0,\:\:$ $b_i>0\implies a_i=0$, etc.


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.