ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

ʬ

[]
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ϡa=up_{1}^{e_{1}}~\cdots~p_{r}^{e_{r}}ηɽ롣
ǡuñǤꡢpiϴ󸵤ǤäơijΤȤpipjƱȼǤϤʤ

[]ʬɽƱȼʴ󸵤ޤȤФ褤

ʬθGCD,LCM

[]

a1,,arR0ǤʤȤ롣
ΤȤGCD(a1,,ar)ӢLCM(a1,,ar)

[]

a_{i}~=~u_{i}~\sum_{j}~p_{j}^{e_{ij}}ɽ롣

ǡuiñؿeijpjϴ󸵤Ǥ롣

ijΤȤpipjƱȼǤϤʤ

ΤȤ

d~=~\sum_{j}~p_{j}^{n_{j}}~\,~,~\,~~n_{j}=\min_{i}~\bigl\{~e_{ij}~\bigr\}ȤСd=GCD(a1,,ar)

d~=~\sum_{j}~p_{j}^{m_{j}}~\,~,~\,~~m_{j}=\min_{i}~\bigl\{~e_{ij}~\bigr\}ȤС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.

ʸ

  • ضΩֺ¡21ο8ĤΤ