离散数学 数论

[e-mail]en,Sections3-4to3-7.2TheIntegersandDivisionOfcourse,youalreadyknowwhattheintegersare,andwhatdivisionis…However:Therearesomespecificnotations,terminology,andtheoremsassociatedwiththeseconceptswhichyoumaynotknow.Theseformthebasicsofnumbertheory.–Vitalinmanyimportantalgorithmstoday(hashfunctions,cryptography,digitalsignatures;ingeneral,on-linesecurity).3ThedividesoperatorNewnotation:3|12–Tospecifywhenanintegerevenlydividesanotherinteger–Readas“3divides12”Thenot-dividesoperator:5|12–Tospecifywhenanintegerdoesnotevenlydivideanotherinteger–Readas“5doesnotdivide12”4Divides,Factor,MultipleLeta,bZwitha0.Defn.:a|b“adividesb”:(cZ:b=ac)“Thereisanintegercsuchthatctimesaequalsb.”–Example:312True,but37False.Iffadividesb,thenwesayaisafactororadivisorofb,andbisamultipleofa.Ex.:“biseven”:≡2|b.Is0even?Is−4?5ResultsonthedividesoperatorIfa|banda|c,thena|(b+c)–Example:if5|25and5|30,then5|(25+30)Ifa|b,thena|bcforallintegersc–Example:if5|25,then5|25*cforallintscIfa|bandb|c,thena|c–Example:if5|25and25|100,then5|100(“commonfacts”butgoodtorepeatforbackground)6DividesRelationTheorem:a,b,cZ:1.a|02.(a|ba|c)a|(b+c)3.a|ba|bc4.(a|bb|c)a|cCorollary:Ifa,b,careintegers,suchthata|banda|c,thena|mb+ncwhenevermandnareintegers.7Proofof(2)Showa,b,cZ:(a|ba|c)a|(b+c).Leta,b,cbeanyintegerssuchthata|banda|c,andshowthata|(b+c).Bydefn.of|,weknows:b=as,andt:c=at.Lets,t,besuchintegers.Thenb+c=as+at=a(s+t).So,u:b+c=au,namelyu=s+t.Thusa|(b+c).QEDDividesRelationCorollary:Ifa,b,careintegers,suchthata|banda|c,thena|mb+ncwhenevermandnareintegers.Proof:Fromprevioustheorempart3(i.e.,a|ba|be)itfollowsthata|mbanda|nc;again,fromprevioustheorempart2(i.e.,(a|ba|c)a|(b+c))itfollowsthata|mb+nc9TheDivision“Algorithm”Theorem:DivisionAlgorithm---Letabeanintegeranddapositiveinteger.Thenthereareuniqueintegersqandr,with0≤rd,suchthata=dq+r.It’sreallyatheorem,notanalgorithm…Onlycalledan“algorithm”forhistoricalreasons.•qiscalledthequotient•riscalledtheremainder•discalledthedivisor•aiscalledthedividend10Whatarethequotientandremainderwhen101isdividedby11?•qiscalledthequotient•riscalledtheremainder•discalledthedivisor•aiscalledthedividend101=119+2Wewrite:q=9=101div11r=2=101mod11adqr11Ifa=7andd=3,thenq=2andr=1,since7=(2)(3)+1.Ifa=−7andd=3,thenq=−3andr=2,since−7=(−3)(3)+2.So:givenpositiveaand(positive)d,inordertogetrwerepeatedlysubtractdfroma,asmanytimesasneededsothatwhatremains,r,islessthand.Givennegativeaand(positive)d,inordertogetrwerepeatedlyadddtoa,asmanytimesasneededsothatwhatremains,r,ispositive(orzero)andlessthand.Theorem:Division“Algorithm”---Letabeanintegeranddapositiveinteger.Thenthereareuniqueintegersqandr,with0≤rd,suchthata=dq+r.Proof:We’llusethewell-orderingpropertydirectlythatstatesthateverysetofnonnegativeintegershasaleastelement.a)ExistenceWewanttoshowtheexistenceofqandr,withthepropertythata=dq+r,0≤rdNote:thissetisnonemptysinceqcanbeanegativeintegerwithlargeabsolutevalue.Considerthesetofnon-negativenumbersoftheforma-dq,whereqisaninteger.Hmm.Canthissetbeempty?Bythewell-orderingproperty,Shasaleastelement,r=a-dq0.(Existence,cont.)risnon-negative;also,rd.otherwiseifr≥d,therewouldbeasmallernonnegativeelementinS,namelya-d(q0+1)≥0.Butthena-d(q0+1),whichissmallerthana-dq0,isanelementofS,contradictingthata-dq0wasthesmallestelementofS.So,itcannotbethecasethatr≥d,provingtheexistenceof0≤rdandq.•qiscalledthequotient•riscalledtheremainder•discalledthedivisor•aiscalledthedividendb)UniquenessSuppose.,0,,,RdQaandrdqathatsuchdRrRrQqWithoutlossofgeneralitywemayassumethatq≤Q.Subtractingbothequationswehave:d(q-Q)=(R–r)(*)So,ddivides(R-r);so,either|d|≤|(R–r)|or(R–r)=0.Since–dR-rd(because)i.e.,|R-r|d,wemusthaveR–r=0.So,R=r.Substitutingintotheoriginaltwoequations,wehavedq=dQ(noted≠0)andthusq=Q,provinguniqueness.(ordirectlyfrom(*))QEDdRr,0ModulararithmeticIfaandbareintegersandmisapositiveinteger,then“aiscongruenttobmodulom”ifmdividesa-b–Notation:a≡b(modm)–Rephrased:m|a-b–Rephrased:amodm=bmodm–Iftheyarenotcongruent:a≡b(modm)Example:Is17congruentto5modulo6?–Rephrased:17≡5(mod6)–As6divides17-5,theyarecongruentExample:Is24congruentto14modulo6?–Rephrased:24≡14(mod6)–As6doesnotdivide24-14=10,theyarenotcongruentNote:thisisadifferentuseof“”thanthemeaning“isdefinedas”usedbefore.Note“=“sign.16Time-keepingonaclockgivesanexampleofmodulararithmetic.(mod12intheUS;ormod24,usingthe24hrclock.Naturallyimposedbytheperiodicityofearth’srotation.)SpiralVisualizationofmod≡3(mod5)≡2(mod5)≡1(mod5)≡0(mod5)≡4(mod5)012345678910111213141516171819202122Exampleshown:modulo-5arithmeticSo,e.g.,19iscongruentto9modulo5.Thespiral/circularviewisusefultokeepinmindwhendoingmodulararithmetic!Congruenceclassesmodulo5.Collapsesinfinitesetofnumbersinto5classes.Whereis-1?Whereis-7?MoreoncongruencesTheorem:Letaandbbeintegers,andletmbeapositiveinteger.Thena≡b(modm)ifandonlyifamodm=bmodmTheorem:Letmbeapositiveinteger.Theintegersaandbarecongruentmodulomifandonlyifthereisanintegerksuchthata=b+kmExample:17and5arecongruen