Friday, December 28, 2018

elementary number theory - Show that if d1e1=d2e2,andgcd(e1,e2)=1Rightarrowlcm(d1,d2)=d1e1=d2e2



Show that for positive integers if d1e1=d2e2 andgcd
We know that: lcm(d_1,d_2)gcd(d_1,d_2)=d_1d_2 but this doesn't help much!
What's the trick?


Answer



Let k=\gcd(d_1,d_2). Then d_1=kd_1' and d_2=kd_2' where d_1' and d_2' are relatively prime. Thus from the relationship you stated we have \text{lcm}(d_1,d_2)k=k^2d_1'd_2',
and therefore
\text{lcm}(d_1,d_2)=kd_1'd_2'.

It remains to show that kd_1'd_2'=d_1e_1=kd_1'e_1, or equivalently d_2'=e_1.



We were told that d_1e_1=d_2e_2, or equivalently that d_1'e_1=d_2'e_2. Since e_1 and e_2 are relatively prime, we have e_1\mid d_2'. And because d_1' and d_2' are relatively prime, we have d_1'\mid e_2.



But because d_1'e_1=d_2'e_2, it follows that e_1=d_2' and d_1'=e_2.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...