Usor:Trlit/DA/SectioQuarta

SECTIO QUARTA

DE

CONGRUENTIIS SECUNDI GRADUS.

---

Residua et non-residua quadratica.

94.

Theorema. Numero quocunque $m$ pro modulo accepto, ex numeris $0$, $1$, $2$, $3$ $\ldots$ $m-1$, plures quam $\textstyle {\frac {1}{2}}m+1$, quando $m$ est par, sive plures quam $\textstyle {\frac {1}{2}}m+{\frac {1}{2}}$, quando $m$ est impar, quadrato congrui fieri non possunt.

Dem. Quoniam numerorum congruorum quadrata sunt congrua: quivis numerus, qui ulli quadrato congruus fieri potest, etiam quadrato alicui cuius radix $<m$ congruus erit. Sufficit itaque residua minima quadratorum $0$, $1$, $4$, $9$ $\ldots$ $(m-1)^{2}$ considerare. At facile perspicitur, esse $(m-1)^{2}\equiv 1$, $(m-2)^{2}\equiv 2^{2}\!$, $(m-3)^{2}\equiv 3^{2}\!$ etc. Hinc etiam, quando $m$ est par, quadratorum $\textstyle ({\frac {1}{2}}m-1)^{2}\!$ et $\textstyle ({\frac {1}{2}}m+1)^{2}\!$, $\textstyle ({\frac {1}{2}}m-2)^{2}\!$ et $\textstyle ({\frac {1}{2}}m+2)^{2}\!$ etc. residua minima eadem erunt: quando vero $m$ est impar, quadrata $\textstyle ({\frac {1}{2}}m-{\frac {1}{2}})^{2}\!$ et $\textstyle ({\frac {1}{2}}m+{\frac {1}{2}})^{2}\!$, $\textstyle ({\frac {1}{2}}m-{\frac {3}{2}})^{2}\!$ et $\textstyle ({\frac {1}{2}}m+{\frac {3}{2}})^{2}\!$ etc. erunt congrua. Unde palam est, alios numeros, quam qui alicui ex quadratis $0$, $1$, $4$, $9$ $\ldots$ $\textstyle ({\frac {1}{2}}m)^{2}\!$ congrui sint, quadrato congruos fieri non posse, quando $m$ par; quando vero impar, quemvis numerum, qui ulli quadrato sit congruus, alicui ex his $0$, $1$, $4$, $9$ $\ldots$ $\textstyle ({\frac {1}{2}}m-{\frac {1}{2}})^{2}\!$ necessario congruum esse. Quare dabuntur ad summum in priori casu $\textstyle {\frac {1}{2}}m+1$ residua minima diversa, in posteriori $\textstyle {\frac {1}{2}}m+{\frac {1}{2}}$. Q. E. D.

Exemplum. Secundum modulum 13 quadratorum numerorum 0, 1, 2, 3 … 6 residua minima inveniuntur 0, 1, 4, 9, 3, 12, 10, post haec vero eadem ordine inverso recurrunt 10, 12, 3 etc. Quare numerus quisque, nulli ex istis residuis congruus, sive qui alicui ex his est congruus, 2, 5, 6, 7, 8, 11, nulli quadrato congruus esse potest.

Secundum modulum 15 haec inveniuntur residua 0, 1, 4, 9, 1, 10, 6, 4, post quae eadem ordine inverso recurrunt. Hic igitur numerus residuorum, quae quadrato congrua fieri possunt, minor adhuc est quam $\textstyle {\frac {1}{2}}m+{\frac {1}{2}}$, quum sint 0, 1, 4, 6, 9, 10. Numeri autem 2, 3, 5, 7, 8, 11, 12, 13, 14 et qui horum alicui sunt congrui, nulli quadrato secundum mod. 15 congrui fieri possunt.

95.

Hinc colligitur, pro quovis modulo omnes numeros in duas classes distingui posse, quarum altera contineat numeros, qui quadrato alicui congrui fieri possint, altera eos, qui non possint. Illos appellabimus residua quadratica numeri istius quem pro modulo accepimus^[1], hos vero ipsius non-residua quadratica, sive etiam, quoties ambiguitas nulla inde oriri potest, simpliciter residua et non-residua. Ceterum palam est sufficere, si omnes numeri $0$, $1$, $2$ $\ldots$ $m-1$ in classes redacti sint: numeri enim congrui ad eandem classem erunt referendi.

Etiam in hac disquisitione a modulis primis initium faciemus, quod itaque subintelligendum erit, etiamsi expressis verbis non moneatur. Numerus primus $2$ autem excludendus, sive numeri primi impares tantum considerandi.

Quoties modulus est numerus primus, multitudo residuorum ipso minorum multitudini non-residuorum aequalis.

96.

Numero primo $p$ pro modulo accepto, numerorum $1$, $2$, $3$ $\ldots$ $p-1$ semissis erunt residua quadratica, reliqui non-residua, i. e. dabuntur ${\scriptstyle {\frac {1}{2}}}(p-1)$ residua totidemque non-residua.

Facile enim probatur, omnia quadrata $1$, $4$, $9\ldots$ ${\scriptstyle {\frac {1}{4}}}(p-1)^{2}\!$ esse incongrua. Scilicet si fieri posset $\textstyle rr\equiv r'\!r'\!{\pmod {p}}$ atque numeri $r$, $r'\!$ inaequales et non maiores quam ${\scriptstyle {\frac {1}{2}}}(p-1)$ posito $r>r'\!$ i. q. licet, fieret $(r-r')(r+r')$ positivus et per $p$ divisibilis. At uterque factor $r-r'\!$, et $r+r'\!$ ipso $p$ est minor, quare suppositio consistere nequit (art. 13). Habentur itaque $\textstyle {\frac {1}{2}}(p-1)$ residua quadratica inter hos numeros $1$, $2$, $3$ $\ldots$ $p-1$ contenta; plura vero inter ipsos esse nequeunt, quia accedente residuo $0$ prodeunt $\textstyle {\frac {1}{2}}(p+1)$, quem numerum omnium residuorum multitudo superare nequit. Quare reliqui numeri erunt non-residua horumque multitudo $\textstyle ={\frac {1}{2}}(p-1)$.

Quum cifra semper sit residuum, hanc numerosque per modulum divisibiles ab investigationibus his excludimus, quia hic casus per se est clarus, theorematumque concinnitatem tantum turbaret. Ex eadem caussa etiam modulum $2$ exclusimus.

97.

Quum plura quae in hac Sect. exponemus, etiam ex principiis Sect. praec. derivari possint, neque inutile sit, eandem veritatem per methodos diversas perscrutari, hunc nexum ostendemus. Facile vero intelligitur, omnes numeros quadrato congruos, indices pares habere, eos contra, qui quadrato nullo modo congrui fieri possint, impares. Quia vero $p-1$ est numerus par, tot indices pares erunt quot impares, scilicet $\textstyle {\frac {1}{2}}(p-1)$, totidemque tum residua tum non-residua dabuntur.

Exempla. Pro modulis		sunt residua
3	…	1.
5	…	1, 4.
7	…	1, 2, 4.
11	…	1, 3, 4, 5, 9.
13	…	1, 3, 4, 9, 10, 12.
17	…	1, 2, 4, 8, 9, 13, 15, 16.
	etc.

reliqui vero numeri his modulis minores, non-residua.

Quaestio, utrum numerus compositus residuum numeri primi dati sit an non-residuum, ab indole factorum pendet.

98.

Theorema. Productum e duobus residuis quadraticis numeri primi $p$, est residuum; productum e residuo in non-residuum, est non-residuum; denique productum e duobus non-residuis, residuum.

Demonstr. I. Sint $A$, $B$ residua e quadratis $aa$, $bb$ oriunda sive $A\equiv aa$, $B\equiv bb$, eritque productum $AB$ quadrato numeri ab congruum i. e. residuum.

II. Quando $A$ est residuum, puta $\equiv aa$, $B$ vero non-residuum, $AB$ erit non-residuum. Ponatur enim, si fieri potest, $AB\equiv kk$, sitque valor expressionis $\textstyle {\frac {k}{a}}{\pmod {p}}\equiv b$; erit itaque $aaB\equiv aabb$, unde $B\equiv bb$, i. e. $B$ residuum contra hyp.

Aliter. Multiplicentur omnes numeri, qui inter hos $1$, $2$, $3$ $\ldots$ $p-1$ sunt residua (quorum multitudo $={\scriptstyle {\frac {1}{2}}}(p-1)$), per $A$ omniaque producta erunt residua quadratica, et quidem erunt omnia incongrua. Iam si non-residuum $B$ per $A$ multiplicatur, productum nulli productorum quae iam habentur congruum erit; quare si residuum esset, haberentur ${\scriptstyle {\frac {1}{2}}}(p+1)$ residua incongrua, inter quae nondum est residuum $0$, contra art. 96.

III. Sint $A$, $B$ non-residua. Multiplicentur omnes numeri, qui inter hos $1$, $2$, $3$ $\ldots$ $p-1$ sunt residua, per $A$, habebunturque ${\scriptstyle {\frac {1}{2}}}(p-1)$ non-residua inter se incongrua (II); iam productum $AB$ nulli illorum congruum esse potest; quodsi igitur esset non-residuum, haberentur ${\scriptstyle {\frac {1}{2}}}(p+1)$ non-residua inter se incongrua, contra art. 96. Quare productum etc. Q. E. D.

Facilius adhuc haec theoremata e principiis sect. praec. derivantur. Quia enim residuorum indices semper sunt pares, non-residuorum vero impares, index producti e duobus residuis vel non-residuis erit par, adeoque productum ipsum, residuum. Contra index producti e residuo in non-residuum erit impar adeoque productum ipsum non-residuum.

Utraque demonstrandi methodus etiam pro his theorematibus adhiberi potest: Expressionis $\textstyle {\frac {a}{b}}{\pmod {p}}$ valor erit residuum, quando numeri $a$, $b$ simul sunt residua, vel simul non-residua; contra autem erit non-residuum, quando numerorum $a$, $b$ alter est residuum, alter non-residuum. Possunt etiam ex conversione theorr. praecc. obtineri.

99.

Generaliter, productum ex quotcunque factoribus est residuum tum quando omnes sunt residua, tum quando non-residuorum, quae inter eos occurrunt, multitudo est par; quando vero multitudo non-residuorum quae inter factores reperiuntur, est impar, productum erit non-residuum. Facile itaque diiudicari potest,

1. Proprie quidem hic casu secundo alio sensu utimur, quam hucusque fecimus. Dicere scilicet oporteret, $r$ esse residuum quadrati $aa$ secundum modulum $m$ quando $\textstyle r\equiv aa{\pmod {m}}$; at brevitatis gratia in hac sectione semper $r$ ipsius $m$ residuum quadraticum vocamus neque hinc ulla ambiguitas metuenda. Expressionem enim, residuum, quando idem significat quod numerus congruus, abhinc non adhibebimus, nisi forte de residuis minimis sermo sit, ubi nullum dubium esse potest.