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

ܼ

ȺǾܿ

[]a,bФơΩġ
(1)a,bθܿϡǾܿܿǤ롣
(2)a,bθϡǤ롣

[]a,bκdǾܿmȤСab=dmΩġ

㡧a=12,b=18ǤΩĤȤǧ롣

  • d=GCD(12,18)=6
  • m=LCM(12,18)=36
  • աab=1218
  • աdm=636

[]
a,bǰʬ˸ǿ碌ơp1,,pnȤϸߤۤʤȤ롣
ΤȤa=[i=1;n]pie_ib=[i=1;n]pif_iȤʤei0fi0ȡa,bκȺǾܿϤ줾켡Τ褦Ϳ롣

  • d=[i=1;n]pimin(e_i,f_i)
  • m=[i=1;n]pimax(e_i,f_i)

[]a,bǤդθdȤ롣

ΤȤdǰʬ򤷡Τ褦ɽǤ롣

d=[i=1;n]pig_i

ƻؿgi0giei0gifi

ΤǺdϡξλؿgiϡgi=min{ei,fi}ˤʤ롣ȾdФ򼨤ȤϤǤ

ϸȾmˤĤƼƱͤ˵Ǥ롣

a,bǤդθܿmǰʬϡpiʳǰѤ1ĤˤޤȤqȽ񤱤СΤ褦ɽ롣

m=q[i=1;n]pih_i

ƻؿhieihifihipiʳǰ¸ߤʤq=1Ȥ롣

ΤȤǾmϡǾqӾξǾλؿhiǤꡢq=1hi=max{ei,fi}ˤʤ롣

[̾]ʺǾܿm˴ؤ

ab=mdꡢm=ab/dΩġd0ΤȤˡ

ޤη̤Ǥd=[i=1;n]piSUP{min{e_i,f_i}};פȡe+f=min{e,f}+max{e,f}פΩġ

äơΤ褦˼ŸǤ롣

m =ab/d =ab/[i=1;n]piSUP{min{e_i,f_i}}; =ab/[i=1;n]piSUP{e+f-max{e_i,f_i}}; =(([i=1;n]piSUP{e_i}[i=1;n]pif_i}/[i=1;n]pie+f)ߦ[i=1;n]piSUP{max{e_i,f_i}}; =1ߦ[i=1;n]piSUP{max{e_i,f_i}}; =[i=1;n]piSUP{max{e_i,f_i}};

㡧a=60,b=42ΤȤκdȺǾܿm롣

a,bǰʬ򤹤ȼΤ褦ˤʤ롣

  • a=60=2235
  • b=42=237

äơΤ褦ˤɽǤ롣

  • a=60=22315170
  • b=42=21315071

ǡ嵭Ѥ롣

  • d=2SUP{min{2,1}};3SUP{min{1,1}};5SUP{min{1,0}};7SUP{min{0,1}};=21315070=6
  • m=2SUP{max{2,1}};3SUP{max{1,1}};5SUP{max{1,0}};7SUP{max{0,1}};=22315171=420

ϺܿȤƤŪ˽פǤ뤬ǰʬ򤬤狼ʤ褦礭ʿФƤϼŪǤϤʤǰʬ˻֤礭ʿξϡ桼åɤθ߽ˡѤƺƤ顢[]a,bФơab=GCD(a,b)LCM(a,b)ΩġפѤƺǾܿ᤿ΨŪǤ롣

[]2Ĥr,mʤrmˤˤĤơ
(r,m)=1 (m-r,m)=1

[](m-r.m)1Ȳꤹ롣

ΤȤ1ʳθdĤΤǡm-r=dp,~m=dqʤp,qϤ

1m2ȡ

dp-r=dp
d(q-p)=r

m=dq

äơ(m,r)1Ȥʤꡢȿ롣

椨ˡ(m-r,m)=1

ʸ

  • عʷϤΤν硡Źᤶơ