Ad argvmentvm transi
Topos Uranos
Latine

Congrventiae et arithmetica modvlaris

Svmmarivm

Haec lectio distribvtionem integrorvm secvndvm residvvm in calcvlvm convertit. Congrventiam modvlo nn definit, ostendit eam idem valere ac idem residvvm relinqvere, relationem aeqvivalentiae esse et svmmam, prodvctvm potentiasqve servare, atqve ex classibvs eivs copiam Zn\mathbb{Z}_n residvorvm constrvit, cvm tabvlis additionis et mvltiplicationis. Identitate Bezovtiana decernit qvae residva inversvm habeant et congrventias lineares omnino solvit; theorema Sinicvm de residvis et theorema parvvm Fermatii demonstrat, criteria divisibilitatis vt congrventias relegit, eaqve omnia ad digitos verificationis, ad calendarivm et ad systema cryptographicvm RSA adhibet, cvivs rectitvdo demonstratvr.

Proposita discendi

  1. Demonstrare congrventiam modvlo nn relationem aeqvivalentiae esse cvm svmma, prodvcto et potentiis compatibilem, eaqve vti ad residva magnorvm nvmerorvm compvtanda.
  2. Tabvlas additionis et mvltiplicationis ipsivs Zn\mathbb{Z}_n constrvere et, maximo commvni divisore adhibito, decernere qvae residva inversvm habeant.
  3. Decernere vtrvm congrventia linearis solvtionem habeat, compvtare qvot solvtiones modvlo nn habeat, et omnes invenire.
  4. Systemata congrventiarvm cvm modvlis inter se primis theoremate Sinico de residvis solvere, solvtione constrvcta eivsqve vnicitate demonstrata.
  5. Theorema parvvm Fermatii demonstrare et ad residva potentiarvm, ad divisibilitates qvae pro omni integro valent et ad rectitvdinem systematis RSA adhibere.
  6. Examinare qvos errores digitvs verificationis detegat, et dies hebdomadis per congrventias compvtare.

Relatio congrventiae

Si hodie est dies Lvnae, post 1515 dies erit dies Martis, et post 10001000 dies erit dies Solis: ad id sciendvm non opvs est dies singillatim nvmerare, qvia satis est residvvm nvmeri diervm per 77 divisi. Eodem modo, 55 horis post horam 99 est hora 22 in horologio 1212 horarvm, et vltimvs digitvs prodvcti a solis vltimis digitis factorvm pendet. In tribvs casibvs residvis compvtatvr et qvotiens neglegitvr. Lectio de divisibilitate et divisione cvm residvo integros in classes distribvit secvndvm residvvm qvod relinqvvnt cvm per nvmervm natvralem dividvntvr, et demonstravit residvvm svmmae, prodvcti et potentiae a solis residvis datorvm pendere. Haec lectio iis observationibvs sermonem proprivm dat, congrventiarvm, qvem Gavss anno 1801 in opere Disqvisitiones Arithmeticae indvxit, evmqve in instrvmentvm compvtandi convertit. Vt in illa lectione, integri anticipantvr, cvm regvlis arithmeticae eorvm ordinisqve qvae in lectione de nvmeris integris fvndantvr.

Definitio (congrventia). Sit nn nvmervs natvralis. Dvo integri aa et bb congrventes modvlo nn svnt si nn differentiam eorvm a−ba - b dividit. Scribitvr a≡b(modn)a \equiv b \pmod{n} et legitvr «aa congrvens est cvm bb modvlo nn»; nvmervs natvralis nn modvlvs congrventiae appellatvr.
a≡b(modn)↔n∣a−ba \equiv b \pmod{n} \leftrightarrow n \mid a - b

Sic 17≡2(mod5)17 \equiv 2 \pmod{5}, qvia 17−2=1517 - 2 = 15; −3≡9(mod4)-3 \equiv 9 \pmod{4}, qvia −3−9=−12-3 - 9 = -12; et integer par est exacte cvm congrvens est cvm 00 modvlo 22. Qvod aa mvltiplvm sit ipsivs nn nvnc scribitvr a≡0(modn)a \equiv 0 \pmod{n}. Si modvlvs est 11, omnes integri inter se congrventes svnt, qvia 11 omnem integrvm dividit; is casvs nvllivs momenti est, et in exemplis modvlvs saltem 22 erit. Signvm ≡\equiv, tribvs lineolis constans, signvm aeqvalitatis in memoriam revocat qvia, vt videbitvr, congrventia fere in omnibvs vt aeqvalitas se gerit; exceptio, divisio, sectionem de inversis occvpabit.

Definitio per differentiam ad demonstrandvm commodissima est, sed intvitio exemplorvm initialivm est residvi. Propositio seqvens confirmat vtramqve idem dicere; qvod continet iam alia forma in lectione de divisibilitate observatvm est, cvm criteria divisibilitatis fvndarentvr, et hic plene demonstratvr.

PropositioCongrventia et residvvm

Dvo integri congrventes svnt modvlo nn si et solvm si idem residvvm relinqvvnt cvm per nn dividvntvr. Sint a=nq+ra = nq + r et b=ns+tb = ns + t divisiones cvm residvo ipsorvm aa et bb per nn, vbi 0≤r<n0 \leq r < n et 0≤t<n0 \leq t < n. Figvra integros a −10-10 vsqve ad 2424 in versibvs 55 nvmerorvm disponit, ita vt qvaeqve colvmna eos colligat qvi idem residvvm relinqvvnt.

Demonstratio

  1. a−b=(nq+r)−(ns+r)=n(q−s)a - b = (nq + r) - (ns + r) = \resaltar{n(q - s)}

    Si residva coincidvnt, r=tr = t, dvabvs divisionibvs svbtractis residvvm tollitvr, et differentia mvltiplvm est ipsivs nn.

  2. a=b+nk=ns+t+nk=n(s+k)+ta = \resaltar{b} + nk = \resaltar{ns + t} + nk = \dato{d}{n(s + k) + t}

    Vicissim, ponamvs nn dividere a−ba - b, id est a=b+nka = b + nk pro aliqvo integro kk. Divisionem ipsivs bb svbstitvimvs.

  3. 0≤t<n→r=t0 \leq t < n \rightarrow \resaltar{r = t}

    Cvm sit 0≤t<n0 \leq t < n, haec aeqvalitas divisio est ipsivs aa per nn cvm residvo tt. Propter vnicitatem qvotientis et residvi, tt residvvm est ipsivs aa, id est t=rt = r.

  4. 23≡8≡−2≡−7≡3(mod5)23 \equiv 8 \equiv -2 \equiv -7 \equiv 3 \pmod{5}

    In figvra, −7-7, −2-2, 33, 88, 1313, 1818 et 2323 eandem colvmnam occvpant: omnes residvvm 33 relinqvvnt, et differentiae eorvm mvltipla svnt ipsivs 55.

Praesertim, omnis integer modvlo nn congrvens est cvm residvo svo, qvod vnvs est ex nn integris 0,1,…,n−10, 1, \ldots, n - 1, et cvm vno tantvm ex iis, qvia dvo ex iis integris sva ipsorvm residva svnt et, si diversi svnt, residva diversa relinqvvnt. Modvlo nn compvtare est pro singvlis nvmeris repraesentantem commodvm colvmnae svae ponere: residvvm, vel interdvm nvmervm negativvm parvvm, vt −1-1 loco ipsivs n−1n - 1.