Monday, 12 August 2013

elementary number theory - Let amidc and bmidc such that gcd(a,b)=1, Show that abmidc




Let ac and bc such that greatest common divisor (gcd) gcd, Show that ab\mid c.


Answer



HINT \rm\quad\ \ a,b\ |\ c\ \Rightarrow\ ab\ |\ ac,bc\ \Rightarrow\ ab\ |\ (ac,bc) = (a,b)\:c = c\ via \rm\:(a,b)= 1\:.



NOTE \ This proof works in every domain where GCDs exist, since it doesn't use Bezout's identity. Instead it uses the GCD distributive law \rm\ (ac,bc) = (a,b)\:c\:,\ true in every GCD domain, viz.



LEMMA \rm\quad (a,b)\ =\ (ac,bc)/c\ \ if \rm\ (ac,bc)\ exists.



Proof \rm\quad\ d\ |\ a,b\ \iff\ dc\ |\ ac,bc\ \iff\ dc\ |\ (ac,bc)\ \iff\ d\ |\ (ac,bc)/c




The above proofs use the universal definitions of GCD, LCM, which often serve to simplify proofs, e.g. see this proof of the GCD * LCM law.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...