# Greatest common factor

1. Aug 14, 2010

### annoymage

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. Aug 14, 2010

### 8daysAweek

$$(a,b)=e\Rightarrow{xe=xam+xbn}$$

(1) $$e | a \Rightarrow{es=a}\Rightarrow{xes=xa}\Rightarrow{xe | xa}$$

(2) $$e | b \Rightarrow{et=b}\Rightarrow{xet=xb}\Rightarrow{xe | xb}$$

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

$$$$1$$,$$2$$,$$3$$\Rightarrow{(ax,bx)=ex}$$

3. Aug 14, 2010

### annoymage

huaaaaa, thankss, i didn't noticed the (1) and (2), it really helpful, thanks