Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Greatest common factor

  1. Aug 14, 2010 #1
    1. The problem statement, all variables and given/known data

    is this suppose to be very obvious???

    (xa,xb)=x(a,b) , x are constant

    i cant see it T_T

    nevertheless, i cant even prove it

    to prove (xa,xb) l x(a,b)

    let e=(a,b), then there exist integer m,n such that

    e=ma+nb

    xe=max+nbx

    since (xa,xb) l ax and (xa,xb) l bx, then (xa,xb) l xe

    to prove x(a,b) l (xa,xb)

    i'm stuck here, many method i used but all halfway, can someone give me clue, and tell me is that suppose to be obvious? i'm rushing to class now, thanks in advance
     
  2. jcsd
  3. Aug 14, 2010 #2
    [tex](a,b)=e\Rightarrow{xe=xam+xbn}[/tex]

    (1) [tex]e | a \Rightarrow{es=a}\Rightarrow{xes=xa}\Rightarrow{xe | xa}[/tex]

    (2) [tex]e | b \Rightarrow{et=b}\Rightarrow{xet=xb}\Rightarrow{xe | xb}[/tex]

    (3) [tex]d |xa, d | xb \Rightarrow{di=xa,dj=xb}\Rightarrow{xe=xam+xbn=d(im+jn)}\Rightarrow{d | xe} [/tex]

    [tex]\(1\),\(2\),\(3\)\Rightarrow{(ax,bx)=ex} [/tex]
     
  4. Aug 14, 2010 #3
    huaaaaa, thankss, i didn't noticed the (1) and (2), it really helpful, thanks
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook