; TeX output 1995.12.12:0701 F S0*"V cmbx10ATMA TRIXMETHODF9ORSOLVINGTHE qPOST A9GETSTAMPSPR9OBLEM$ Z K`y cmr10W*en{SenrgUUChÎou /EInstiturtUeUUofMa tUhemÎatics,UUAcadTemiaSinica,Nankanrg,T*aipai,TaiwanpHaroldUUBowmÎanandJau{ShyonrgShiue>1Unive rs#ityUUofNevqadra,LasV*egas$ Y-$ ': cmti10De}'dicatedtothememoryofPr}'ofessorC.H.T;eng' 1.IntroQd9uction.InJs1eve ralrecentpap#ersGildTer[1]andPlanitz[2]cons#idTereGdtUhe problemrofpurchas#inrgrpGoqstagestampqsofvqar*iousdTenominÎa tionssoastromeetaxeGdbudget.IfUUtUhe reareb> cmmi10ntyp#eGsofstampqstUhi#srequireGsthesolurtionoftUheequa tionU(1:1) aٓR cmr71|sx1S+8a2x2+8!", cmsy10g+8a 0er cmmi7nq~xn8=cwhe reai?Gi#stUhecoqstoftUheitUhtyp#eofstamp, @xi?Gi#stUhenUurm|qb#e rofstampqsandci#stUhebudget, whe rexir.andair.arenon{nega tiveintUege rs._KIn[1]GildTerdi#sTcusqs1eGstUhesolurtioninintUege rsoftUheUUequa tionU(1:2) 12x1S+817x2C=100z;whe rex1ki#stUhenUurm|qb#e rofs1econdclasqsstampqs(a ttUheoldra tUeof12p),x2ktUhenUurm|qb#e rof rstvclasqsstamps(a t17p),EandzytUhetrotalcoqstinpGournds.mPlanitzextUendstUheproblembyshÎoppinrgUUfortUhreetyp#eGsofstampqsgivinrgtUheequa tionU(1:3) 13x1S+818x2+22x3C=cUU: Solvinrg(1.2)i#saclasqsicalproblemindiophantineequa tionsprovidTeGdtUha ttUhexi:˫are urnreGstr*ictUed.muTheH_noveltyH_oftUhepGoqstagestampproblemlieGsintUhef#acttUha ttUhesolurtionximUustUUb#enon{nega tive. T*osolve(1.2)GildTe r[1]andPlanitz[2]us1etUheknowncontinUueGdf*ractionsolurtionfor(1.1)xfornr=2xtrogene ra tUeallintege rsolurtions.0Thexnon{nega tiveoneGsaretUhenobtaineGd 70 G * f*rom(as#impleinequality*.bPlanitz(reGduces(tUhetUhreevqar*iablecas1etroapairofequivqalenttwo vqar*iable=equa tionsinordTe rtrous1econtinUueGdf*ractions.*jHeagaini#sabletrondsolurtionsintUe rmsofinequalitieGsobtainedf*romtUheparametr*icrepreGs1enta tiongivenbycontinUueGdf*ractions.>Ifiwepurchas1eafourtUhtyp#eofstampandtUhi#sbecomeGsaproblemwitUhfoururnknowns,tUhi#s3methÎoGd3willnotwor kourtdirectly*,b#ecaus1ethelineqartransformÎa tioni#snoteqas#ilyUUfournd. In]atUhi#snotUeweextendtUheapproachofPlanitzbygivinrganalgor*itUhmwhichyieldsalltUheMsolurtionsof(1.1).XOurmetUhÎoGddo#esnotdTep#endoncontinUueGdf*ractions,tUhusitmÎayb#eapplieGdindirectfashiontroequa tionswitUhanynUurm|qb#e rofvqar*iableGsandmÎayb#eeqasilyprogrammeGdUUforcompurtUe rsolution. TheproGofoftUhealgor*itUhmi#sgivenins1ection2.]F*ollowinrgtUhi#sweshÎowhÎowGildTe r'ssolurtionUUof(1.2)andPlanitz'ssolurtionof(1.3)mÎayb#efourndf*rom(1.1). 2.dSMaftr1ixSoJlut9ionof(1.1).In,tUhi#ss1ectionwewillpreGs1entanalgor*itUhmforndinrgtUheUUgene ralsolurtionoftUhelineqardiophantineequa tion,(2:1) a1|sx1S+8a2x2+8g+8anq~xn8=bwhe reUUa1|s,a2,:::UQ,anq~,bareintUege rs. ThroughÎourt,ZAiwillYdTenotUetUheithrowvectrorofmÎa tr*ixA.~dTet7x(A)andA^twilldTenotUe tUhe`dTetUe rminÎantofandtUhetranspGoqs1eofA,resp#ectively*.The`followinrgtwointUegralrowop#e ra tionsUUarewellknown: (1)UUE (i;j ):qIntUe rchanrgetUheitUhandj tUhrow. (2)UUE (i(kP);j ):qAddanintUegralmUulrtipleofktimeGstUheitUhrowtrotUhej tUhrow. IfD[(2.1)hasanintUegralsolurtion, tUhentUhegreqa tUeGstcommondivi#sor(g.c.d.) >ofa1|s;a2;:::;an AmUustkdividTeb. The refore,/0withÎourtloqsskofgene ralitykwemÎayasqsurmetUha ttUheUUg.c.d.qofa1|s,a2,:::,anӫi#s1. Let AdTenotUetUherowmÎa tr*ixoftUheco#ecient sof(2.1)andletX=[x1|s;x2;:::;xnq~].ThenUUequa tion(2.1)i#softUheformAX ^tP=b. TheUUmÎainreGsulrtoftUhepap#e ristUhefollowinrgtUheorem. TheoremUU1 fe .莑B.qLet-Y rbC~4=[AtV;Inq~]=Vu cmex1026 6fi48䍍a11.0=Sǫ0 a20.1=Sǫ07 5. 5.5. . . . /. /./. >eW.BH .F,q . T9. T9.T9.lan0.0=Sǫ1VZ,p3Z,p7 Z,p7fiZ,p5e: 71 H W*eUUapplyintUegralrowop#e ra tionsonCqurntilwehaveamÎa tr*ixoftUheform7V FZ2 FZ6 FZ6fi FZ4 1 6p11 (p12 χ ±p1n 0 6p21 (p22 χ ±p2n . . . s. s. s. . . . . Y . . ,. ,. ,. 0 pn1 pn2 χ 2