# Prove that ac=bd implies a=d and b=c (if a,b relatively prime and c,d relatively prime)

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

• 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 – Steven Apr 11 '14 at 15:40
• Sorry, I missed that line! – ah11950 Apr 11 '14 at 15:40
• Or also, $\frac ab=\frac dc$, since both are irreducible fractions... – chubakueno Apr 11 '14 at 15:54
• @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. – Bill Dubuque Apr 11 '14 at 16:11
• @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. – 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.