[]
KΤȤơ¿༰f,gK[x]ͿƤȤ롣ΤȤΩġ
(1)hK[x] s.t. ǥ(h)=(f,g)
(2)A,BK[x] s.t. h=Af+Bg
(3)h=GCD(f,g)
[]f=g=0ΤȤˤϡh=0ȤФ褤
ʲf,gΤɤ餫0ǤʤȤ롣
(1)ǥI=(f,g)˴ޤޤ0Ǥʤ¿༰ǺǾμΤΤh(x)Ȥ롣
껻ơf=qh+rdeg(r)deg(h)ȤʤäȤȡrIȤʤ롣
ޤhμr=0
äơh|f
Ʊͤˤơh|g
äơf,g(h),h(f,g)Ȥʤꡢ(h)=(f,g)Ȥʤ롣
(2)h(f,g)顢h=Af+BgA,BK[x]¸ߤ롣
(3)h'f,gϤθȤ(2)ꡢh'|hȤʤ롣
äơh=GCD(f,g)Q.E.D.
[]桼åɤθ߽ˡ
KΤȤ롣
¿༰f,gK[x],g0γ껻ơf=qg+rȤʤäȤ롣
ΤȤGCD(f,g)=GCD(g,r)Ωġ
[]ʬ
RȤRʬUnique Factorization DomainUFD)ǤȤ
(1)0ǤñǤʤǤդθaRʬġ
¨ͭ¸Ĥδa1,,ar¸ߤơa=a1arɽ롣
(2)Τ褦ʬϽñѤȤưŪǤ롣
¨a1,,arȴb1,,brˤĤơa1ar=b1bsǤСr=sǤꡢֹդؤФ٤ƤiˤĤbiaiƱȼˤʤ롣
[]
ʬR0Ǥʤaϡηɽ롣
ǡuñǤꡢpiϴǤäơijΤȤpipjƱȼǤϤʤ
[]ʬɽƱȼʴޤȤФ褤
[]
Rʬ
a1,,arR0ǤʤȤ롣
ΤȤGCD(a1,,ar)ӢLCM(a1,,ar)
[]
ɽ롣
ǡuiñؿeijpjϴǤ롣
ijΤȤpipjƱȼǤϤʤ
ΤȤ
ȤСd=GCD(a1,,ar)
ȤСl=LCM(a1,,ar)Q.E.D.
[]
GCD(a1,,ar)=1ע͡GCD(da1,,dar)=d
[]ʬδǸǤ롣
[]
a
a=bcȤȡ
a|a a|bc bc=ad,dR b1brc1cs=ad1dtʢb,c,dʬơb=b1br,c=c1cs,d=d1dt
ʬΰˤäơabi,cjΤɤ줫ƱȼǤʤФʤʤ
ΤȤ顢a|b or a|cQ.E.D.
[ͻ]λ¤顢ʬǸʬȤƤФ롣
[]RСʬǤ롣
(1)0ǤñǤʤϴʬġ
(2)ǸǤ롣
[]ʬΰ롣
Rδa1,,ar,b1,,bsˤĤơa1ar=b1bsꤹ롣
ǡrsȤƤ⡢ϼʤ
a1|b1bs顢bi¸ߤơa1|biȤʤ롣ֹդؤơi=1Ȥ롣
ȤʤΤǡa1biƱȼ
äơb1=u1a1,ñu1RȽ롣
ȡΤ褦ˤʤ롣
a1ar=b1bs
a1ar=u1a1bs
a2ar=u1b2bs
֤ȤǡaibiƱȼQ.E.D.