Congruence[edit] ... Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference (that ...
Modulararithmetic
FromWikipedia,thefreeencyclopedia
Jumptonavigation
Jumptosearch
Computationmoduloafixedinteger
Thisarticleisaboutthe(modn)notation.Forthebinaryoperationmod(a,n),seemodulooperation.
Time-keepingonthisclockusesarithmeticmodulo12.Adding4hoursto9o'clockgives1o'clock,since13iscongruentto1modulo12.
Inmathematics,modulararithmeticisasystemofarithmeticforintegers,wherenumbers"wraparound"whenreachingacertainvalue,calledthemodulus.ThemodernapproachtomodulararithmeticwasdevelopedbyCarlFriedrichGaussinhisbookDisquisitionesArithmeticae,publishedin1801.
Afamiliaruseofmodulararithmeticisinthe12-hourclock,inwhichthedayisdividedintotwo12-hourperiods.Ifthetimeis7:00now,then8hourslateritwillbe3:00.Simpleadditionwouldresultin7+8=15,butclocks"wraparound"every12hours.Becausethehournumberstartsoverafteritreaches12,thisisarithmeticmodulo12.Intermsofthedefinitionbelow,15iscongruentto3modulo12,so"15:00"ona24-hourclockisdisplayed"3:00"ona12-hourclock.
Contents
1Congruence
1.1Examples
2Properties
3Congruenceclasses
4Residuesystems
4.1Reducedresiduesystems
5Integersmodulon
6Applications
7Computationalcomplexity
8Exampleimplementations
9Seealso
10Notes
11References
12Externallinks
Congruence[edit]
Givenanintegern>1,calledamodulus,twointegersaandbaresaidtobecongruentmodulon,ifnisadivisoroftheirdifference(thatis,ifthereisanintegerksuchthata−b=kn).
Congruencemodulonisacongruencerelation,meaningthatitisanequivalencerelationthatiscompatiblewiththeoperationsofaddition,subtraction,andmultiplication.Congruencemodulonisdenoted:
a
≡
b
(
mod
n
)
.
{\displaystylea\equivb{\pmod{n}}.}
Theparenthesesmeanthat(modn)appliestotheentireequation,notjusttotheright-handside(here,b).Thisnotationisnottobeconfusedwiththenotationbmodn(withoutparentheses),whichreferstothemodulooperation.Indeed,bmodndenotestheuniqueintegerasuchthat0≤a0as:
Z
/
n
Z
=
{
a
¯
n
∣
a
∈
Z
}
=
{
0
¯
n
,
1
¯
n
,
2
¯
n
,
…
,
n
−
1
¯
n
}
.
{\displaystyle\mathbb{Z}/n\mathbb{Z}=\left\{{\overline{a}}_{n}\mida\in\mathbb{Z}\right\}=\left\{{\overline{0}}_{n},{\overline{1}}_{n},{\overline{2}}_{n},\ldots,{\overline{n{-}1}}_{n}\right\}.}
(Whenn=0,
Z
/
n
Z
{\displaystyle\mathbb{Z}/n\mathbb{Z}}
isnotanemptyset;rather,itisisomorphicto
Z
{\displaystyle\mathbb{Z}}
,sincea0={a}.)
Wedefineaddition,subtraction,andmultiplicationon
Z
/
n
Z
{\displaystyle\mathbb{Z}/n\mathbb{Z}}
bythefollowingrules:
a
¯
n
+
b
¯
n
=
(
a
+
b
)
¯
n
{\displaystyle{\overline{a}}_{n}+{\overline{b}}_{n}={\overline{(a+b)}}_{n}}
a
¯
n
−
b
¯
n
=
(
a
−
b
)
¯
n
{\displaystyle{\overline{a}}_{n}-{\overline{b}}_{n}={\overline{(a-b)}}_{n}}
a
¯
n
b
¯
n
=
(
a
b
)
¯
n
.
{\displaystyle{\overline{a}}_{n}{\overline{b}}_{n}={\overline{(ab)}}_{n}.}
Theverificationthatthisisaproperdefinitionusesthepropertiesgivenbefore.
Inthisway,
Z
/
n
Z
{\displaystyle\mathbb{Z}/n\mathbb{Z}}
becomesacommutativering.Forexample,inthering
Z
/
24
Z
{\displaystyle\mathbb{Z}/24\mathbb{Z}}
,wehave
12
¯
24
+
21
¯
24
=
33
¯
24
=
9
¯
24
{\displaystyle{\overline{12}}_{24}+{\overline{21}}_{24}={\overline{33}}_{24}={\overline{9}}_{24}}
asinthearithmeticforthe24-hourclock.
Weusethenotation
Z
/
n
Z
{\displaystyle\mathbb{Z}/n\mathbb{Z}}
becausethisisthequotientringof
Z
{\displaystyle\mathbb{Z}}
bytheideal
n
Z
{\displaystylen\mathbb{Z}}
,asetcontainingallintegersdivisiblebyn,where
0
Z
{\displaystyle0\mathbb{Z}}
isthesingletonset{0}.Thus
Z
/
n
Z
{\displaystyle\mathbb{Z}/n\mathbb{Z}}
isafieldwhen
n
Z
{\displaystylen\mathbb{Z}}
isamaximalideal(i.e.,whennisprime).
Thiscanalsobeconstructedfromthegroup
Z
{\displaystyle\mathbb{Z}}
undertheadditionoperationalone.Theresidueclassanisthegroupcosetofainthequotientgroup
Z
/
n
Z
{\displaystyle\mathbb{Z}/n\mathbb{Z}}
,acyclicgroup.[8]
Ratherthanexcludingthespecialcasen=0,itismoreusefultoinclude
Z
/
0
Z
{\displaystyle\mathbb{Z}/0\mathbb{Z}}
(which,asmentionedbefore,isisomorphictothering
Z
{\displaystyle\mathbb{Z}}
ofintegers).Infact,thisinclusionisusefulwhendiscussingthecharacteristicofaring.
Theringofintegersmodulonisafinitefieldifandonlyifnisprime(thisensuresthateverynonzeroelementhasamultiplicativeinverse).If
n
=
p
k
{\displaystylen=p^{k}}
isaprimepowerwithk>1,thereexistsaunique(uptoisomorphism)finitefield
G
F
(
n
)
=
F
n
{\displaystyle\mathrm{GF}(n)=\mathbb{F}_{n}}
withnelements,butthisisnot
Z
/
n
Z
{\displaystyle\mathbb{Z}/n\mathbb{Z}}
,whichfailstobeafieldbecauseithaszero-divisors.
Themultiplicativesubgroupofintegersmodulonisdenotedby
(
Z
/
n
Z
)
×
{\displaystyle(\mathbb{Z}/n\mathbb{Z})^{\times}}
.Thisconsistsof
a
¯
n
{\displaystyle{\overline{a}}_{n}}
(whereaiscoprimeton),whicharepreciselytheclassespossessingamultiplicativeinverse.Thisformsacommutativegroupundermultiplication,withorder
φ
(
n
)
{\displaystyle\varphi(n)}
.
Applications[edit]
Intheoreticalmathematics,modulararithmeticisoneofthefoundationsofnumbertheory,touchingonalmosteveryaspectofitsstudy,anditisalsousedextensivelyingrouptheory,ringtheory,knottheory,andabstractalgebra.Inappliedmathematics,itisusedincomputeralgebra,cryptography,computerscience,chemistryandthevisualandmusicalarts.
Averypracticalapplicationistocalculatechecksumswithinserialnumberidentifiers.Forexample,InternationalStandardBookNumber(ISBN)usesmodulo11(for10digitISBN)ormodulo10(for13digitISBN)arithmeticforerrordetection.Likewise,InternationalBankAccountNumbers(IBANs),forexample,makeuseofmodulo97arithmetictospotuserinputerrorsinbankaccountnumbers.Inchemistry,thelastdigitoftheCASregistrynumber(auniqueidentifyingnumberforeachchemicalcompound)isacheckdigit,whichiscalculatedbytakingthelastdigitofthefirsttwopartsoftheCASregistrynumbertimes1,thepreviousdigittimes2,thepreviousdigittimes3etc.,addingalltheseupandcomputingthesummodulo10.
Incryptography,modulararithmeticdirectlyunderpinspublickeysystemssuchasRSAandDiffie–Hellman,andprovidesfinitefieldswhichunderlieellipticcurves,andisusedinavarietyofsymmetrickeyalgorithmsincludingAdvancedEncryptionStandard(AES),InternationalDataEncryptionAlgorithm(IDEA),andRC4.RSAandDiffie–Hellmanusemodularexponentiation.
Incomputeralgebra,modulararithmeticiscommonlyusedtolimitthesizeofintegercoefficientsinintermediatecalculationsanddata.Itisusedinpolynomialfactorization,aproblemforwhichallknownefficientalgorithmsusemodulararithmetic.Itisusedbythemostefficientimplementationsofpolynomialgreatestcommondivisor,exactlinearalgebraandGröbnerbasisalgorithmsovertheintegersandtherationalnumbers.AspostedonFidonetinthe1980sandarchivedatRosettaCode,modulararithmeticwasusedtodisproveEuler'ssumofpowersconjectureonaSinclairQLmicrocomputerusingjustone-fourthoftheintegerprecisionusedbyaCDC6600supercomputertodisproveittwodecadesearlierviaabruteforcesearch.[9]
Incomputerscience,modulararithmeticisoftenappliedinbitwiseoperationsandotheroperationsinvolvingfixed-width,cyclicdatastructures.Themodulooperation,asimplementedinmanyprogramminglanguagesandcalculators,isanapplicationofmodulararithmeticthatisoftenusedinthiscontext.ThelogicaloperatorXORsums2bits,modulo2.
Inmusic,arithmeticmodulo12isusedintheconsiderationofthesystemoftwelve-toneequaltemperament,whereoctaveandenharmonicequivalencyoccurs(thatis,pitchesina1:2or2:1ratioareequivalent,andC-sharpisconsideredthesameasD-flat).
Themethodofcastingoutninesoffersaquickcheckofdecimalarithmeticcomputationsperformedbyhand.Itisbasedonmodulararithmeticmodulo9,andspecificallyonthecrucialpropertythat10≡1(mod9).
Arithmeticmodulo7isusedinalgorithmsthatdeterminethedayoftheweekforagivendate.Inparticular,Zeller'scongruenceandtheDoomsdayalgorithmmakeheavyuseofmodulo-7arithmetic.
Moregenerally,modulararithmeticalsohasapplicationindisciplinessuchaslaw(e.g.,apportionment),economics(e.g.,gametheory)andotherareasofthesocialsciences,whereproportionaldivisionandallocationofresourcesplaysacentralpartoftheanalysis.
Computationalcomplexity[edit]
Sincemodulararithmetichassuchawiderangeofapplications,itisimportanttoknowhowharditistosolveasystemofcongruences.AlinearsystemofcongruencescanbesolvedinpolynomialtimewithaformofGaussianelimination,fordetailsseelinearcongruencetheorem.Algorithms,suchasMontgomeryreduction,alsoexisttoallowsimplearithmeticoperations,suchasmultiplicationandexponentiationmodulo n,tobeperformedefficientlyonlargenumbers.
Someoperations,likefindingadiscretelogarithmoraquadraticcongruenceappeartobeashardasintegerfactorizationandthusareastartingpointforcryptographicalgorithmsandencryption.TheseproblemsmightbeNP-intermediate.
Solvingasystemofnon-linearmodulararithmeticequationsisNP-complete.[10]
Exampleimplementations[edit]
Thissectionpossiblycontainsoriginalresearch.Pleaseimproveitbyverifyingtheclaimsmadeandaddinginlinecitations.Statementsconsistingonlyoforiginalresearchshouldberemoved.(May2020)(Learnhowandwhentoremovethistemplatemessage)
BelowarethreereasonablyfastCfunctions,twoforperformingmodularmultiplicationandoneformodularexponentiationonunsignedintegersnotlargerthan63bits,withoutoverflowofthetransientoperations.
Analgorithmicwaytocompute
a
⋅
b
(
mod
m
)
{\displaystylea\cdotb{\pmod{m}}}
:[11]
uint64_tmul_mod(uint64_ta,uint64_tb,uint64_tm){
if(!((a|b)&(0xFFFFFFFFULL<<32)))returna*b%m;
uint64_td=0,mp2=m>>1;
inti;
if(a>=m)a%=m;
if(b>=m)b%=m;
for(i=0;i<64;++i){
d=(d>mp2)?(d<<1)-m:d<<1;
if(a&0x8000000000000000ULL)d+=b;
if(d>=m)d-=m;
a<<=1;
}
returnd;
}
Oncomputerarchitectureswhereanextendedprecisionformatwithatleast64bitsofmantissaisavailable(suchasthelongdoubletypeofmostx86Ccompilers),thefollowingroutineis[clarificationneeded],byemployingthetrickthat,byhardware,floating-pointmultiplicationresultsinthemostsignificantbitsoftheproductkept,whileintegermultiplicationresultsintheleastsignificantbitskept:[citationneeded]
uint64_tmul_mod(uint64_ta,uint64_tb,uint64_tm){
longdoublex;
uint64_tc;
int64_tr;
if(a>=m)a%=m;
if(b>=m)b%=m;
x=a;
c=x*b/m;
r=(int64_t)(a*b-c*m)%(int64_t)m;
returnr<0?r+m:r;
}
BelowisaCfunctionforperformingmodularexponentiation,thatusesthemul_modfunctionimplementedabove.
Analgorithmicwaytocompute
a
b
(
mod
m
)
{\displaystylea^{b}{\pmod{m}}}
:
uint64_tpow_mod(uint64_ta,uint64_tb,uint64_tm){
uint64_tr=m==1?0:1;
while(b>0){
if(b&1)r=mul_mod(r,a,m);
b=b>>1;
a=mul_mod(a,a,m);
}
returnr;
}
However,forallaboveroutinestowork,mmustnotexceed63bits.
Seealso[edit]
Booleanring
Circularbuffer
Division(mathematics)
Finitefield
Legendresymbol
Modularexponentiation
Modulo(mathematics)
Multiplicativegroupofintegersmodulon
Pisanoperiod(Fibonaccisequencesmodulon)
Primitiverootmodulon
Quadraticreciprocity
Quadraticresidue
Rationalreconstruction(mathematics)
Reducedresiduesystem
Serialnumberarithmetic(aspecialcaseofmodulararithmetic)
Two-elementBooleanalgebra
Topicsrelatingtothegrouptheorybehindmodulararithmetic:
Cyclicgroup
Multiplicativegroupofintegersmodulon
Otherimportanttheoremsrelatingtomodulararithmetic:
Carmichael'stheorem
Chineseremaindertheorem
Euler'stheorem
Fermat'slittletheorem(aspecialcaseofEuler'stheorem)
Lagrange'stheorem
Thue'slemma
Notes[edit]
^SandorLehoczky;RichardRusczky.DavidPatrick(ed.).theArtofProblemSolving.Vol. 1(7 ed.).p. 44.ISBN 0977304566.
^Weisstein,EricW."ModularArithmetic".mathworld.wolfram.com.Retrieved2020-08-12.
^Pettofrezzo&Byrkit(1970,p. 90)
^Long(1972,p. 78)
^Long(1972,p. 85)
^Itisaring,asshownbelow.
^"2.3:IntegersModulon".MathematicsLibreTexts.2013-11-16.Retrieved2020-08-12.
^SengadirT.,DiscreteMathematicsandCombinatorics,p.293,atGoogleBooks
^"Euler'ssumofpowersconjecture".rosettacode.org.Retrieved2020-11-11.
^Garey,M.R.;Johnson,D.S.(1979).ComputersandIntractability,aGuidetotheTheoryofNP-Completeness.W.H.Freeman.ISBN 0716710447.
^ThiscodeusestheCliteralnotationforunsignedlonglonghexadecimalnumbers,whichendwithULL.Seealsosection6.4.4ofthelanguagespecificationn1570.
References[edit]
JohnL.Berggren."modulararithmetic".EncyclopædiaBritannica.
Apostol,TomM.(1976),Introductiontoanalyticnumbertheory,UndergraduateTextsinMathematics,NewYork-Heidelberg:Springer-Verlag,ISBN 978-0-387-90163-3,MR 0434929,Zbl 0335.10001.Seeinparticularchapters5and6forareviewofbasicmodulararithmetic.
MaartenBullynck"ModularArithmeticbeforeC.F.Gauss.Systematisationsanddiscussionsonremainderproblemsin18th-centuryGermany"
ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,andCliffordStein.IntroductiontoAlgorithms,SecondEdition.MITPressandMcGraw-Hill,2001.ISBN 0-262-03293-7.Section31.3:Modulararithmetic,pp. 862–868.
AnthonyGioia,NumberTheory,anIntroductionReprint(2001)Dover.ISBN 0-486-41449-3.
Long,CalvinT.(1972).ElementaryIntroductiontoNumberTheory(2nd ed.).Lexington:D.C.HeathandCompany.LCCN 77171950.
Pettofrezzo,AnthonyJ.;Byrkit,DonaldR.(1970).ElementsofNumberTheory.EnglewoodCliffs:PrenticeHall.LCCN 71081766.
Sengadir,T.(2009).DiscreteMathematicsandCombinatorics.Chennai,India:PearsonEducationIndia.ISBN 978-81-317-1405-8.OCLC 778356123.
Externallinks[edit]
"Congruence",EncyclopediaofMathematics,EMSPress,2001[1994]
Inthismodularartarticle,onecanlearnmoreaboutapplicationsofmodulararithmeticinart.
AnarticleonmodulararithmeticontheGIMPSwiki
ModularArithmeticandpatternsinadditionandmultiplicationtables
vteNumbertheoryFields
Algebraicnumbertheory(classfieldtheory,non-abelianclassfieldtheory,Iwasawatheory,Iwasawa-Tatetheory,Kummertheory)
Analyticnumbertheory(analytictheoryofL-functions,probabilisticnumbertheory,sievetheory)
Geometricnumbertheory
Computationalnumbertheory
Transcendentalnumbertheory
Diophantinegeometry(Arakelovtheory,Hodge–Arakelovtheory)
Arithmeticcombinatorics(additivenumbertheory)
Arithmeticgeometry(anabeliangeometry,P-adicHodgetheory)
Arithmetictopology
Arithmeticdynamics
Keyconcepts
Numbers
Naturalnumbers
Primenumbers
Rationalnumbers
Irrationalnumbers
Algebraicnumbers
Transcendentalnumbers
P-adicnumbers(P-adicanalysis)
Arithmetic
Modulararithmetic
Chineseremaindertheorem
Arithmeticfunctions
Advancedconcepts
Quadraticforms
Modularforms
L-functions
Diophantineequations
Diophantineapproximation
Continuedfractions
Category
Listoftopics
Listofrecreationaltopics
Wikibook
Wikiversity
Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Modular_arithmetic&oldid=1094563299"
Categories:ModulararithmeticFiniteringsGrouptheoryHiddencategories:ArticleswithshortdescriptionShortdescriptionisdifferentfromWikidataArticlesthatmaycontainoriginalresearchfromMay2020AllarticlesthatmaycontainoriginalresearchWikipediaarticlesneedingclarificationfromMay2020AllarticleswithunsourcedstatementsArticleswithunsourcedstatementsfromMay2020ArticleswithexampleCcode
Navigationmenu
Personaltools
NotloggedinTalkContributionsCreateaccountLogin
Namespaces
ArticleTalk
English
Views
ReadEditViewhistory
More
Search
Navigation
MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate
Contribute
HelpLearntoeditCommunityportalRecentchangesUploadfile
Tools
WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem
Print/export
DownloadasPDFPrintableversion
Inotherprojects
WikimediaCommonsWikibooks
Languages
العربيةAsturianuবাংলাБашҡортсаBosanskiCatalàČeštinaΕλληνικάEspañolEsperantoEuskaraفارسیFrançaisGalego한국어हिन्दीHrvatskiBahasaIndonesiaÍslenskaItalianoעבריתLatinaLombardMagyarമലയാളംNederlands日本語NorskbokmålPolskiPortuguêsРусскийShqipSimpleEnglishSlovenčinaSlovenščinaکوردیСрпски/srpskiSrpskohrvatski/српскохрватскиSuomiSvenskaதமிழ்ไทยTürkçeУкраїнськаاردوTiếngViệt粵語中文
Editlinks
Modular exponentiation