Disquisitiones arithmeticae/Sectio quarta

by Carolus Fridericus Gauss

Carolus Fridericus Gauss

Disquisitiones arithmeticae

Sectio quarta

1801

editio: ex opera omnia, Gottinga, 1870; Ernst Christian Julius Schering recensuit
fons: librum vide

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, utrum numerus compositus sit residuum necne, si modo, quid sint singuli ipsius factores constet. Quamobrem in tabula II numeros primos tantummodo recepimus. Oeconomia huius tabulae haec est. In margine positi sunt moduli^[2], in facie vero numeri primi successivi; quando ex his aliquis fuit residuum moduli alicuius, in spatio utrique respondente lineola collocata est, quando vero numerus primus fuit non-residuum moduli, spatium respondens vacuum mansit.

De modulis, qui sunt numeri compositi.

100.

Antequam ad difficiliora progrediamur, quaedam de modulis non primis adiicienda sunt.

Si numeri primi $p$, potestas aliqua $p^{n}$ pro modulo assumitur (ubi $p$ non esse $2$ supponimus), omnium numerorum per $p$ non divisibilium moduloque minorum altera semissis erunt residua, altera non-residua, i. e. utrorumque multitudo $={\scriptstyle {\frac {1}{2}}}(p-1)p^{n-1}\!$.

Si enim $r$ est residuum: quadrato alicui congruus erit, cuius radix moduli dimidium non superat, vid. art. 94. Iam facile perspicitur, dari ${\scriptstyle {\frac {1}{2}}}(p-1)p^{n-1}\!$ numeros per $p$ non divisibiles modulique semisse minoribus; superest itaque ut demonstretur, omnium horum numerorum quadrata incongrua esse, sive residua quadratica diversa suppeditare. Quodsi duorum numerorum $a,b$ per $p$ non divisibilium modulique semisse minorum quadrata essent congrua, foret $aa-bb$ sive $(a-b)(a+b)$ per $p^{n}\!$ divisibilis (posito i. q. licet $a>b$). Hoc vero fieri non potest, nisi vel alter numerorum $a-b$, $a+b$ per $p^{n}\!$ fuerit divisibilis, quod fieri nequit, quoniam uterque $<p^{n}\!$, vel alter per $p^{m}\!$ alter vero per $p^{n-m}\!$, i. e. uterque per $p$. Sed etiam hoc fieri nequit. Manifesto enim etiam summa et differentia $2a$ et $2b$ per $p$ foret divisibilis adeoque etiam $a$ et $b$ contra hyp. — Hinc tandem colligitur inter numeros per $p$ non divisibiles moduloque minores ${\scriptstyle {\frac {1}{2}}}(p-1)p^{n}\!$ residua dari, reliquos quorum multitudo aeque magna, esse non-residua, Q. E. D. — Potest etiam theorema hoc ex consideratione indicum derivari simili modo ut art. 97.

101.

Quivis numerus per $p$ non divisibilis, qui ipsius $p$ est residuum, erit residuum etiam ipsius $p^{n}\!$; qui vero ipsius $p$ est non-residuum, etiam ipsius $p^{n}\!$ non-residuum erit.

Pars posterior huius propositionis per se est manifesta. Si itaque prior falsa esset, inter numeros ipso $p^{n}\!$ minores simulque per $p$ non divisibiles plures forent residua ipsius $p$ quam ipsius $p^{n}\!$, i. e. plures quam ${\scriptstyle {\frac {1}{2}}}p^{n-1}(p-1)$. Nullo vero negotio perspici poterit, multitudinem residuorum numeri $p$ inter illos numeros esse praecise $={\scriptstyle {\frac {1}{2}}}p^{n-1}(p-1)$.

Aeque facile est, quadratum reipsa invenire, quod secundum modulum $p^{n}\!$ residuo dato sit congruum, si quadratum huic residuo secundum modulum $p$ congruum habetur.

Scilicet si quadratum habetur, $aa$, quod residuo dato $A$ secundum modulum $p^{\mu }\!$ est congruum, deducitur inde quadratum ipsi $A$ secundum modulum $p^{\nu }\!$ congruum (ubi $\nu >\mu$ et $=$ vel $<2\mu$ supponitur) sequenti modo. Ponatur radix quadrati quaesiti $=\pm a+xp^{\mu }\!$, quam formam eam habere debere facile perspicitur; debetque esse $aa\pm 2axp^{\mu }+xxp^{2\mu }$ $\equiv$ $\textstyle A{\pmod {p^{\nu }}}$ sive propter $2\mu >\nu$, $A-aa$ $\equiv$ $\textstyle \pm 2axp^{\mu }\!{\pmod {p^{\nu }}}$. Sit $A-aa=p^{\mu }d$, eritque $x$ valor expressionis $\textstyle \pm {\frac {d}{2a}}{\pmod {p^{\nu -\mu }}}$, quae huic $\textstyle \pm {\frac {A-aa}{2ap^{\mu }}}{\pmod {p^{\nu }}}$ aequivalet.

Dato igitur quadrato ipsi $A$ secundum $p$ congruo, deducitur inde quadratum ipsi $A$ secundum modulum $p^{2}\!$ congruum; hinc ad modulum $p^{4}\!$, hinc ad $p^{8}\!$ etc. ascendi poterit.

Ex. Proposito residuo 6, quod secundum modulum 5 quadrato 1 congruum, invenitur quadratum 9² cui secundum 25 est congruum, 16² cui secundum 125 congruum etc.

102.

Quod vero attinet ad numeros per $p$ divisibiles, patet, eorum quadrata per $pp$ fore divisibilia, adeoque omnes numeros per $p$ quidem divisibiles, neque vero per $pp$, ipsius $p^{n}\!$ fore non-residua. Generaliter vero, si proponitur numerus $p^{k}A\!$, ubi $A$ per $p$ non est divisibilis, hi casus erunt distinguendi:

1) Quando $k=$ vel $>n$, erit $\textstyle p^{k}A\equiv 0{\pmod {p^{n}}}$, i. e. residuum.

2) Quando $k<n$ atque impar, erit $p^{k}A$ non-residuum.

Si enim esset $p^{k}A$ $=$ $p^{2\kappa +1}A$ $\equiv$ $\textstyle ss{\pmod {p^{n}}}$, $ss$ per $p^{2\kappa +1}\!$ divisibilis esset, id quod aliter fieri nequit, quam si fuerit $s$ per $p^{\kappa +1}\!$ divisibilis. Tunc vero $ss$ etiam per $p^{2\kappa +2}\!$ divisibilis, adeoque etiam (quia $2\kappa +2$ certo non maior quam $n$) $p^{k}A$ i. e. $p^{2\kappa +1}A$; sive $A$ per $p$, contra hyp.

3) Quando $k<n$ atque par. Tum $p^{k}A$ erit residuum vel non-residuum ipsius $p^{n}\!$, prout $A$ est residuum vel non-residuum ipsius $p$. Quando enim $A$ est residuum ipsius $p$, erit etiam residuum ipsius $p^{n-k}\!$. Posito autem $\textstyle A\equiv aa{\pmod {p^{n-k}}}$ erit $\textstyle Ap^{k}\equiv aap^{k}\!{\pmod {p^{n}}}$, $aap^{k}\!$ vero est quadratum. Quando autem $A$ est non-residuum ipsius $p$, $p^{k}A$ residuum ipsius $p^{n}\!$ esse nequit. Ponatur enim $\textstyle p^{k}A\equiv aa{\pmod {p^{n}}}$, eritque necessario $aa$ per $p^{k}\!$ divisibilis. Quotiens erit quadratum, cui $A$ secundum modulum $p^{n-k}\!$ adeoque etiam secundum modulum $p$ congruus, i. e. $A$ erit residuum ipsius $p$ contra hyp.

103.

Quoniam casum $p=2$ exclusimus, de hoc adhuc quaedam dicenda. Quando numerus $2$ est modulus, numerus quicunque erit residuum, non-residua nulla erunt. Quando vero $4$ est modulus, omnes numeri impares formae $4k+1$ erunt residua, omnes vero formae $4k+3$ non-residua. Tandem quando $8$ aut altior potestas numeri $2$ est modulus, omnes numeri impares formae $8k+1$ erunt residua, reliqui vero, seu ii qui sunt formarum $8k+3$, $8k+5$, $8k+7$, erunt non-residua. Pars posterior huius propositionis inde clara, quod quadratum cuiusvis numeri imparis, sive sit formae $4k+1$, sive formae $4k-1$, fit formae $8k+1$. Priorem ita probamus.

1) Si duorum numerorum vel summa vel differentia per $2^{n-1}\!$ est divisibilis, numerorum quadrata erunt congrua secundum modulum $2^{n}\!$. Si enim alter ponitur $=a$, erit alter formae $2^{n-1}h\pm a$, cuius quadratum invenitur $\textstyle \equiv aa{\pmod {2^{n}}}$.

2) Quivis numerus impar, qui ipsius $2^{n}\!$ est residuum quadraticum, congruus erit quadrato alicui, cuius radix est numerus impar et $<2^{n-2}\!$. Sit enim quadratum quodcunque, cui numerus ille congruus, $aa$ atque numerus $\textstyle a\equiv \pm \alpha {\pmod {2^{n-1}}}$, ita ut $\alpha$ moduli semissem non superet (art. 4), eritque $aa\equiv \alpha \alpha$. Quare etiam numerus propositus erit $\equiv \alpha \alpha$. Manifesto vero tum $a$ tum $\alpha$ erunt impares atque $\alpha <2^{n-2}\!$.

3) Omnium numerorum imparium ipso $2^{n-2}\!$ minorum quadrata secundum $2^{n}\!$ incongrua erunt. Sint enim duo tales numeri $r$ et $s$, quorum quadrata si secundum $2^{n}\!$ essent congrua, foret $(r-s)(r+s)$ per $2^{n}\!$ divisibilis (posito $r>s$). Facile vero perspicitur numeros $r-s$, $r+s$ simul per $4$ divisibiles esse non posse, quare si alter tantummodo per $2$ est divisibilis, alter, ut productum per $2^{n}\!$ divisibilis fieret, per $2^{n-1}\!$ divisibilis esse deberet, Q. E. A. quoniam uterque $<2^{n-2}\!$.

4) Quodsi denique haec quadrata ad residua sua minima positiva reducuntur, habebuntur $2^{n-3}\!$ residua quadratica diversa modulo minora^[3], quorum quodvis erit formae $8k+1$. Sed quum praecise $2^{n-3}\!$ numeri formae $8k+1$ modulo minores exstent, necessario hi omnes inter illa residua reperientur. Q. E. D.

Ut quadratum numero dato formae $8k+1$ secundum modulum $2^{n}\!$ congruum inveniatur, methodus similis adhiberi potest, ut in art. 101; vid. etiam art. 88. — Denique de numeris paribus eadem valent, quae art. 102 generaliter exposuimus.

104.

Circa multitudinem valorum diversorum (i. e. secundum modulum incongruorum), quos expressio talis $\textstyle V=\surd {A}{\pmod {p^{n}}}$ admittit, siquidem $A$ est residuum ipsius $p^{n}\!$ facile e praecc. colliguntur haec. (Numerum $p$ supponimus esse primum, ut ante, et brevitatis caussa casum $n=1$ statim includimus). I. Si $A$ per $p$ non est divisibilis, $V$ unum valorem habet pro $p=2$, $n=1$, puta $V\equiv 1$; duos, quando $p$ est impar, nec non pro $p=2$, $n=2$, puta ponendo unum $\equiv v$, alter erit $\equiv -v$; quatuor pro $p=2$, $n>2$, scilicet ponendo unum $\equiv v$, reliqui erunt $\equiv -v$, $2^{n-1}+v$, $2^{n-1}-v$. II. Si $A$ per $p$ divisibilis est, neque vero per $p^{n}\!$, sit potestas altissima ipsius $p$ ipsum $A$ metiens $p^{2\mu }\!$ (manifesto enim ipsius exponens par esse debebit) atque $A=ap^{2\mu }\!$. Tunc patet, omnes valores ipsius $V$ per $p^{\mu }\!$ divisibiles esse, et quotientes e divisione ortos fieri valores expr. $\textstyle V'=\surd {a}{\pmod {p^{n-2\mu }}}$; hinc omnes valores diversi ipsius $V$ prodibunt, multiplicando omnes valores expr. $V'$ inter $0$ et $p^{n-\mu }\!$ sitos per $p^{\mu }\!$ quare illi exhibebuntur per $vp^{\mu },\ vp^{\mu }+p^{n-\mu }\!,\ vp^{\mu }+2p^{n-\mu }\!\ldots \ vp^{\mu }+(p^{\mu }-1)p^{n-\mu }$ si $v$ indefinite omnes valores diversos expr. $V'$ exprimit, ita ut illorum multitudo fiat $p^{\mu }\!$, $2p^{\mu }\!$ vel $4p^{\mu }\!$, prout multitudo horum (per casum I) est $1$, $2$ vel $4$. III. Si $A$ per $p^{n}\!$ divisibilis est, facile perspicietur, statuendo $n=2m$ vel $=2m-1$, prout par est vel impar, omnes numeros per $p^{m}\!$ divisibiles, neque ullos alios, esse valores ipsius $V$; quare omnes valores diversi hi erunt $0$, $p^{m}\!$, $2p^{m}\!$ $\ldots$ $(p^{n-m}-1)p^{m}\!$, quorum multitudo $p^{n-m}\!$.

105.

Superest casus, ubi modulus $m$ e pluribus numeris primis compositus est. Sit $m=abc\ldots$, designantibus $a$, $b$, $c$ etc. numeros primos diversos aut primorum diversorum potestates, patetque statim, si $n$ sit residuum ipsius $m$, fore etiam $n$ residuum singulorum $a$, $b$, $c$ etc., adeoque $n$ certo non-residuum ipsius $m$ esse, si fuerit NR. ullius e numeris $a$, $b$, $c$ etc. Vice versa autem, si $n$ singulorum $a$, $b$, $c$ etc. residuum est, etiam residuum producti $m$ erit. Supponendo enim, $n\equiv A^{2}\!$, $B^{2}\!$, $C^{2}\!$ etc. sec. mod. $a$, $b$, $c$ etc. resp., patet, si numerus $N$ ipsis $A$, $B$, $C$ etc. sec. mod. $a$, $b$, $c$ etc resp. congruus eruatur (art. 32), fore $n\equiv NN$ secundum omnes hos modulos adeoque etiam secundum productum $m$. — Quum facile perspiciatur, hoc modo e combinatione cuiusvis valoris ipsius $A$ sive expr. $\textstyle \surd {n}{\pmod {a}}$ cum quovis valore ipsius $B$ cum quovis valore ipsius $C$ etc. oriri valorem ipsius $N$ sive $\textstyle \surd {n}{\pmod {m}}$, nec non e combinationibus diversis produci diversos $N$, et e cunctis cunctos: multitudo omnium valorum diversorum ipsius $N$ aequalis erit producto e multitudinibus valorum ipsorum $A$, $B$, $C$ etc., quas determinare in art. praec. docuimus. — Porro manifestum est, si unus valor expressionis $\textstyle \surd {n}{\pmod {m}}$ sive ipsius $N$ fuerit notus, hunc simul fore valorem omnium $A$, $B$, $C$ etc.; et quum hinc per art. praec. omnes reliqui valores harum quantitatum deduci possint, facile sequitur, ex uno valore ipsius $N$ omnes reliquos obtineri posse.

Ex. Sit modulus 315, cuius residuum an non-residuum sit 46, quaeritur. Divisores primi numeri 315 sunt 3, 5, 7, atque numerus 46 residuum cuiusvis eorum, quare etiam ipsius 315 erit residuum. Porro, quia 46 ≡ 1, et ≡ 64 (mod. 9); ≡ 1 et ≡ 16 (mod. 5); ≡ 4 et ≡ 25 (mod. 7), inveniuntur radices quadratorum, quibus 46 secundum modulum 315 congruus, 19, 26, 44, 89, 226, 271, 289, 296.

Criterium generale, utrum numerus datus numeri primi dati residuum sit an non-residuum.

106.

Ex praecedentibus colligitur, si tantummodo semper dignosci possit, utrum numerus primus datus numeri primi dati residuum sit an non-residuum, omnes reliquos casus ad hunc reduci posse. Pro illo itaque casu criteria certa omni studio nobis erunt indaganda. Antequam autem hanc perquisitionem aggrediamur, criterium quoddam exhibemus ex Sect. praec. petitum, quod quamvis in praxi nullum fere usum habeat, tamen propter simplicitatem atque generalitatem memoratu dignum est.

Numerus quicunque $A$ per numerum primum $2m+1$ non divisibilis, huius primi residuum est vel non-residuum, prout $A^{m}\equiv +1$ vel $\textstyle -1{\pmod {2m+1}}$.

Sit enim pro modulo $2m+1$ in systemate quocunque numeri $A$ index $a$, eritque $a$ par, quando $A$ est residuum ipsius $2m+1$, impar vero quando $A$ non-residuum. At numeri $A^{m}\!$ index erit $ma$, i. e. $\equiv 0$ vel $\textstyle \equiv m{\pmod {2m}}$, prout $a$ par vel impar. Hinc denique $A^{m}\!$ in priori casu erit $\equiv +1$, in posteriori vero $\textstyle \equiv -1{\pmod {2m+1}}$. V. artt. 57, 62.

Ex. 3 ipsius 13 est residuum, quia 3⁶ ≡ 1 (mod. 13), 2 vero ipsius 13 non-residuum, quoniam 2⁶ ≡ -1 (mod. 13).

At quoties numeri examinandi mediocriter sunt magni, hoc criterium ob calculi immensitatem prorsus inutile erit.

Disquisitiones de numeris primis quorum residua aut non-residua sint numeri dati.

107.

Facillimum quidem est, proposito modulo, omnes assignare numeros, qui ipsius residua sunt vel non-residua. Scilicet si ille numerus ponitur $=m$, determinari debent quadrata, quorum radices semissem ipsius $m$ non superant, sive etiam numeri his quadratis secundum $m$ congrui (ad praxin methodi adhuc expeditiores dantur), tuncque omnes numeri horum alicui secundum $m$ congrui, erunt residua ipsius $m$, omnes autem numeri nulli istorum congrui erunt non-residua. — At quaestio inversa, proposito numero aliquo, assignare omnes numeros, quorum ille sit residuum vel non-residuum, multo altioris est indaginis. Hoc itaque problema, a cuius solutione illud quod in art. praec. nobis proposuimus pendet, in sequentibus perscrutabimur, a casibus simplicissimis inchoantes.

Residuum $-1$.

108.

Theorema. Omnium numerorum primorum formae $4n+1$, $-1$ est residuum quadraticum, omnium vero numerorum primorum formae $4n+3$ non-residuum.

Ex. $-1$ est residuum numerorum 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97 etc., e quadratis numerorum 2, 5, 4, 12, 6, 9, 23, 11, 27, 34, 22 etc. respective oriundum; contra non-residuum est numerorum 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83 etc.

Mentionem huius theor. iam in art. 64 fecimus. Demonstratio vero facile ex art. 106 petitur. Etenim pro numero primo formae $4n+1$ est $(-1)^{2n}\equiv 1$, pro numero autem formae $4n+3$ habetur $(-1)^{2n+1}\equiv -1$. Convenit haec demonstratio cum ea, quam l. c. tradidimus. Sed propter theorematis elegantiam atque utilitatem non superfluum erit, alio adhuc modo idem ostendisse.

109.

Designemus complexum omnium residuorum numeri primi $p$, quae ipso $p$ sunt minora, excluso residuo $0$, per literam $C$, et quoniam horum residuorum multitudo semper $={\tfrac {p-1}{2}}$, manifestum est, eam fore parem, quoties $p$ sit formae $4n+1$, imparem vero, quoties $p$ sit formae $4n+3$. Dicantur, ad instar art. 77, ubi de numeris in genere agebatur, residua socia talia, quorum productum $\textstyle \equiv 1{\pmod {p}}$; manifeste enim si $r$ est residuum, etiam $\textstyle {\frac {1}{r}}{\pmod {p}}$ residuum erit. Et quoniam idem residuum plura socia inter residua $C$ habere nequit, patet, omnia residua $C$ in classes distribui posse, quarum quaevis bina residua socia contineat. Iam perspicuum est, si nullum residuum daretur, quod sibi ipsi esset socium, i. e. si quaevis classis bina residua inaequalia contineret, omnium residuorum numerum fore duplum numeri omnium classium; quodsi vero aliqua dantur residua sibi ipsis socia i. e. aliquae classes, quae unicum tantum residuum aut, si quis malit, idem residuum bis continent, posita harum classium multitudine $=a$, reliquarumque multitudine $=b$; erit omnium residuorum $C$ numerus $=a+2b$. Quare quando $p$ est formae $4n+1$, erit $a$ numerus par; quando autem $p$ est formae $4n+3$, erit $a$ impar. At numeri ipso $p$ minores alii, quam $1$ et $p-1$, sibi ipsis socii esse nequeunt (vid. art. 77); priorque $1$ certo inter residua occurrit; unde in priori casu $p-1$ (seu quod hic idem valet, $-1$) debet esse residuum, in posteriori vero non-residuum; alias enim in illo casu foret $a=1$, in hoc autem $=2$, quod fieri nequit.

110.

Etiam haec demonstratio ill. Eulero debetur, qui et priorem primus invenit V. Opusc. Anal. T. I. p. 135. — Facile quisquis videbit eam similibus principiis innixam esse, ut demonstratio nostra secunda theor. Wilsoniani art. 77. Si vero hoc theorema supponere velimus, facilius adhuc demonstratio exhiberi poterit. Scilicet inter numeros $1$, $2$, $3$ $\ldots$ $p-1$ erunt ${\tfrac {p-1}{2}}$ residua quadratica ipsius $p$ totidemque non-residua; quare non-residuorum multitudo erit par, quando $p$ est formae $4n+1$; impar, quando $p$ est formae $4n+3$. Hinc productum ex omnibus numeris $1$, $2$, $3$ $\ldots$ $p-1$ in priori casu erit residuum, in posteriori non-residuum (art. 99). At productum hoc semper $\textstyle \equiv -1{\pmod {p}}$; adeoque etiam $-1$ in priori casu residuum, in posteriori non-residuum erit.

111.

Si itaque $r$ est residuum numeri alicuius primi formae $4n+1$, etiam $-r$ huius primi residuum erit; omnia autem talis numeri non-residua, etiam signo contrario sumta non-residua manebunt^[4]. Contrarium evenit pro numeris primis formae $4n+3$, quorum residua quando signum mutatur, non-residua fiunt et vice versa, vid. art. 98.

Ceterum facile ex praecedentibus derivatur regula generalis: $-1$ est residuum omnium numerorum, qui neque per $4$ neque per ullum numerum primum formae $4n+3$ dividi possunt; omnium reliquorum non-residuum. V. artt. 103 et 105.

Residua $+2$ et $-2$.

112.

Progredimur ad residua $+2$ et $-2$.

Si ex tabula II colligimus omnes numeros primos, quorum residuum est $+2$, hos habebimus: 7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97. Facile autem animadvertitur, inter hos numeros nullos inveniri formarum $8n+3$ et $8n+5$.

Videamus itaque, num haec inductio ad certitudinem evehi possit.

Primum observamus, quemvis numerum compositum formae $8n+3$ vel $8n+5$ necessario factorem primum alterutrius formae $8n+3$ vel $8n+5$, involvere; manifesto enim e solis numeris primis formarum $8n+1$, $8n+7$, alii numeri quam qui sunt formae $8n+1$ vel $8n+7$, componi nequeunt. Quodsi itaque inductio nostra generaliter est vera, nullus omnino numerus formae $8n+3$, $8n+5$ dabitur, cuius residuum $+2$; sicque nullus certe numerus huius formae infra $100$ exstat, cuius residuum sit $+2$. Si autem ultra hunc limitem tales numeri reperirentur, ponamus minimum omnium $=t$. Erit itaque $t$ vel formae $8n+3$ vel $8n+5$; $+2$ ipsius residuum erit, omnium autem numerorum similium minorum non-residuum. Ponatur $\textstyle 2\equiv aa{\pmod {t}}$ poteritque $a$ ita semper accipi, ut sit impar simulque $<t$, (habebit enim $a$ ad minimum duos valores positives ipso $t$ minores quorum summa $=t$, quorumque adeo alter par alter impar v. artt. 104. 105). Quo facto sit $aa=2+tu$, sive $tu=aa-2$, eritque $aa$ formae $8n+1$, $tu$ igitur formae $8n-1$, adeoque $u$ formae $8n+3$ vel $8n+5$, prout $t$ est formae posterioris vel prioris. At ex aequatione $aa=2+tu$ sequitur, etiam $\textstyle 2\equiv aa{\pmod {u}}$ i. e. $2$ etiam ipsius $u$ residuum fore. Facile vero perspicitur, esse $u<t$, quare $t$ non est minimus numerus inductioni nostrae contrarius contra hyp. Unde manifesto sequitur id quod per inductionem inveneramus, generaliter verum esse.

Combinando haec cum prop. art. 111 sequentia theoremata nanciscimur.

I. Numerorum omnium primorum formae $8n+3$, $+2$ erit non-residuum, $-2$ vero residuum.

II. Numerorum omnium primorum formae $8n+5$ tum $+2$ tum $-2$ erunt non-residua.

113.

Per similem inductionem ex tab. II inveniuntur numeri primi, quorum residuum est $-2$ hi: 3, 11, 17, 19, 41, 43, 59, 67, 73, 83, 89, 97^[5]. Inter quos quum nulli inveniantur formarum $8n+5$, $8n+7$, num etiam haec inductio theorematis generalis vim adipisci possit, investigemus. Ostenditur simili modo ut in art. praec., quemvis numerum compositum formae $8n+5$ vel $8n+7$, factorem primum involvere formae $8n+5$ vel formae $8n+7$, ita ut, si inductio nostra generaliter vera, $-2$ nullius omnino numeri formae $8n+5$ vel $8n+7$ residuum esse possit. Si autem tales numeri darentur, ponatur omnium minimus $=t$, fiatque $-2=aa-tu$. Ubi si uti supra $a$ impar ipsoque $t$ minor accipitur, $u$ erit formae $8n+5$ vel $8n+7$, prout $t$ formae $8n+7$ vel $8n+5$. At ex eo quod $aa+2=tu$ atque $a<t$, quisquis facile derivare poterit, etiam $u$ ipso $t$ minorem fore. Denique $-2$ etiam ipsius $u$ residuum erit, i. e. $t$ non erit minimus numerus, qui inductioni nostrae adversatur, contra hyp. Quare necessario $-2$ omnium numerorum formarum $8n+5$, $8n+7$ non-residuum.

Combinando haec cum prop. art. 111, prodeunt theoremata haec:

I. Omnium numerorum primorum $8n+5$, tum $-2$ tum $+2$ sunt non-residua, uti iam in art. praec. invenimus.

II. Omnium numerorum primorum formae $8n+7$, $-2$ est non-residuum, $+2$ vero residuum.

Ceterum in utraque demonstratione pro $a$ etiam valorem parem accipere potuissemus; tunc autem casum ubi $a$ fuisset formae $4n+2$, ab eo distinguere oportuisset, ubi $a$ formae $4n$. Evolutio autem perinde procedit uti supra, nullique difficultati est obnoxia.

114.

Unus adhuc superest casus, scilicet ubi numerus primus est formae $8n+1$. Hic vero methodum praecedentem eludit, artificiaque prorsus peculiaria postulat.

Sit pro modulo primo $8n+1$, radix quaecunque primitiva $a$, eritque (art. 62) $a^{4n}\equiv$ $\textstyle -1{\pmod {8n+1}}$, quae congruentia ita etiam exhiberi potest, $(a^{2n}+1)^{2}\equiv$ $\textstyle 2a^{2n}\!{\pmod {8n+1}}$, sive etiam ita, $(a^{2n}-1)^{2}\equiv 2a^{2n}\!$. Unde sequitur, tum $2a^{2n}\!$ tum $-2a^{2n}\!$ ipsius $8n+1$ esse residuum: at quia $a^{2n}\!$ est quadratum per modulum non divisibile, manifeste etiam tum $+2$ tum $-2$ residua erunt (art. 98).

115.

Haud inutile erit, adhuc aliam huius theorematis demonstrationem adiicere, quae similem relationem ad praecedentem habet, ut theorematis art. 108 demonstratio secunda (art. 109) ad primam (art. 108). Periti facilius tunc perspicient, binas demonstrationes tam illas quam has non adeo heterogeneas esse, quam primo forsan aspectu videantur.

I. Pro modulo quocunque primo formae $4n+1$, inter numeros ipso minores $1$, $2$, $3$ $\ldots$ $4m$, reperientur $m$, qui biquadrato congrui esse possunt, reliqui vero $3m$ non poterunt.

Facile quidem hoc ex principiis Sect. praec. derivatur, sed etiam absque his demonstratio haud difficilis. Demonstravimus enim, pro tali modulo $-1$ semper esse residuum quadraticum. Sit itaque $ff\equiv -1$ patetque, si $z$ fuerit numerus quicunque per modulum non divisibilis, quaternorum numerorum $+z$, $-z$, $+fz$, $-fz$ (duos incongruos esse facile perspicitur) biquadrata inter se congrua fore; porro manifestum est, biquadratum numeri cuiuscunque, qui nulli ex his quatuor congruus, illorum biquadratis congruum fieri non posse, (alias enim congruentia $x^{4}\equiv z^{4}\!$ quae est quarti gradus, plures quam $4$ radices haberet, contra art. 43). Hinc facile colligitur, omnes numeros $1$, $2$, $3$, $\ldots$ $4m$, tantummodo $m$ biquadrata incongrua praebere, quibus inter eosdem numeros $m$ congrui reperientur, reliqui autem nulli biquadrato congrui esse poterunt.

II. Secundum modulum primum formae $8n+1$, $-1$ biquadrato congruus fieri poterit ($-1$ erit residuum biquadraticum huius numeri primi).

Omnium enim residuorum biquadraticorum ipso $8n+1$ minorum (cifra exclusa) multitudo erit $=2n$ i. e. par. Porro facile probatur, si $r$ fuerit residuum biquadraticum ipsius $8n+1$, etiam valorem expr. $\textstyle {\frac {1}{r}}{\pmod {8n+1}}$ fore tale residuum. Hinc omnia residua biquadratica in classes simili modo distribui poterunt, uti in art. 109 residua quadratica distribuimus: nec non reliqua demonstrationis pars prorsus eodem modo procedit ut illic.

III. Iam sit $g^{4}\equiv -1$, et $h$ valor expr. $\textstyle {\frac {1}{g}}{\pmod {8n+1}}$. Tunc erit $(g\pm h)^{2}=g^{2}+h^{2}\pm 2gh\equiv g^{2}+h^{2}\pm 2$ (propter $gh\equiv 1$). At $g^{4}\equiv -1$, adeoque $-h^{2}\equiv g^{4}h^{2}\equiv g^{2}\!$, unde tandem $g^{2}+h^{2}\equiv 0$, atque $(g\pm h)^{2}\equiv \pm 2$ i. e. tum $+2$ tum $-2$ residuum quadraticum ipsius $8n+1$. Q. E. D.

116.

Ceterum ex praecc. facile regula sequens generalis deducitur : $+2$ est residuum numeri cuiusvis, qui neque per $4$, neque per ullum primum formae $8n+3$ vel $8n+5$ dividi potest, reliquorum autem (ex. gr. omnium numerorum formarum $8n+3$, $8n+5$, sive sint primi, sive compositi) non-residuum.

$-2$ est residuum numeri cuiusvis, qui neque per $4$, neque per ullum primum formae $8n+5$ vel $8n+7$ dividi potest, omnium autem reliquorum non-residuum.

Theoremata haec elegantia iam sagaci Fermatio innotuerunt, Op. Mathem. p. 168. Demonstrationem vero quam se habere professus est, nusquam communicavit. Postea ab ill. Eulero frustra semper est investigata: at ill. La Grange primus demonstrationem rigorosam reperit, Nouv. Mém. de l'Ac. de Berlin 1775. p. 349, 351. Quod ill. Eulerum adhuc latuisse videtur, quando scripsit diss. in Opusc. Analyt. conservatam, T. I. p. 259.

Residua $+3$ et $-3$.

117.

Pergimus ad residua $+3$ et $-3$. A posteriori initium faciamus.

Reperiuntur ex tab. II numeri primi, quorum residuum est $-3$, hi: 3, 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, inter quos nullus invenitur formae $6n+5$. Quod vero etiam ultra tabulae limites nulli primi huius formae dantur, quorum residuum $-3$, ita demonstramus: Primo patet, quemvis numerum compositum formae $6n+5$ necessario factorem primum aliquem eiusdem formae involvere. Quousque igitur nulli numeri primi formae $6n+5$ dantur, quorum residuum $-3$, eousque tales etiam compositi non dabuntur. Quodsi vero ultra tabulae nostrae limites tales numeri darentur, sit omnium minimus $=t$, ponaturque $-3=aa-tu$. Tunc erit, si acceperis $a$ parem ipsoque $t$ minorem, $u<t$ atque $-3$ residuum ipsius $u$. Sed quando $a$ formae $6n\pm 2$, $tu$ erit formae $6n+1$, adeoque $u$ formae $6n+5$, Q. E. A. quia $t$ minimum esse numerum inductioni nostrae adversantem supposuimus. Quando vero $a$ formae $6n$, erit $tu$ formae $36n+3$ adeoque ${\tfrac {1}{3}}tu$ formae $12n+1$, quare ${\tfrac {1}{3}}u$ erit formae $6n+5$; patet autem, $-3$ etiam ipsius ${\tfrac {1}{3}}u$ residuum fore, atque esse ${\tfrac {1}{3}}u<t$, Q. E. A. Manifestum itaque, $-3$ nullius numeri formae $6n+5$ residuum esse posse.

Quoniam quisque numerus formae $6n+5$ necessario vel sub forma $12n+5$, vel sub hac $12n+11$ continetur, prior autem forma sub hac $4n+1$, posterior sub hac $4n+3$, haec habentur theoremata:

I. Cuiusvis numeri primi formae $12n+5$, tum $-3$ tum $+3$ non-residuum est.

II. Cuiusvis numeri primi formae $12n+11$, $-3$ est non-residuum, $+3$ vero residuum.

118.

Numeri quorum residuum est $+3$, ex tabula II. inveniuntur hi: 3, 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, inter quos nulli sunt formae $12n+5$ vel $12n+7$. Nullos autem omnino numeros formarum $12n+5$, $12n+7$ dari, quorum $+3$ sit residuum, eodem prorsus modo, ut in artt. 112, 113, 117, comprobari potest, quare hoc negotio supersedemus. Habemus itaque collato art. 111 theoremata:

I. Numeri cuiusvis primi formae $12n+5$ non-residua sunt tum $+3$ tum $-3$ (uti iam in art. praec. invenimus).

II. Numeri cuiusvis primi formae $12n+7$ non-residuum est $+3$, $-3$ vero residuum.

119.

Nihil autem per hanc methodum pro numeris formae $12n+1$ inveniri potest, qui proin artificia singularia requirunt. Ex inductione quidem facile colligitur, omnium numerorum primorum huius formae residua esse $+3$ et $-3$. Manifesto autem demonstrari tantummodo debet, numerorum talium residuum esse $-3$, quia tunc necessario etiam $+3$ residuum esse debet (art. 111). Ostendemus autem generalius, $-3$ esse residuum numeri cuiusvis primi formae $3n+1$.

Sit $p$ huiusmodi primus atque $a$ numerus pro modulo $p$ ad exponentem $3$ pertinens (quales dari ex art. 54 manifestum, quia $3$ submultiplum ipsius $p-1$). Erit itaque $\textstyle a^{3}\equiv 1{\pmod {p}}$ i. e. $a^{3}-1$ sive $(a^{2}+a+1)(a-1)$ per $p$ divisibilis. Sed patet $a$ esse non posse $\textstyle \equiv 1{\pmod {p}}$, quia $1$ ad exponentem $1$ pertinet, quare $a-1$ per $p$ divisibilis non erit, sed $a^{2}+a+1$ erit, hincque etiam $4aa+4a+4$, i. e. erit $\textstyle (2a+1)^{2}\equiv -3{\pmod {p}}$ sive $-3$ residuum ipsius $p$. Q. E. D.

Ceterum patet, hanc demonstrationem (quae a praecedentibus est independens) etiam numeros primos formae $12n+7$ complecti, quos iam in art. praec, absolvimus.

Observare adhuc convenit, hanc analysin ad instar methodi in artt. 109, 115 usitatae exhiberi posse, at brevitatis gratia huic rei non immoramur.

120.

Colliguntur facile ex praec. theoremata haec (vid. artt. 102, 103, 105):

I. $-3$ est residuum omnium numerorum, qui neque per $8$, neque per $9$, neque per ullum numerum primum formae $6n+5$ dividi possunt, non-residuum autem omnium reliquorum.

II. $+3$ est residuum omnium numerorum, qui neque per $4$, neque per $9$, neque per ullum primum formae $12n+5$ vel $12n+7$ dividi possunt, omnium reliquorum non-residuum.

Teneatur imprimis casus particularis hic:

$-3$ est residuum omnium numerorum primorum formae $3n+1$, seu quod idem est omnium, qui ipsius $3$ sunt residua, non-residuum vero omnium numerorum primorum formae $6n+5$, seu, excluso numero $2$, omnium formae $3n+2$, i. e. omnium, qui ipsius $3$ sunt non-residua. Facile vero perspicitur omnes reliquos casus ex hoc sponte sequi.

Propositiones ad residua $+3$ et $-3$ pertinentes iam Fermatio notae fuerunt, Opera Wallisii T. II. p. 857. At ill. Euler primus demonstrationes tradidit, Comm. nov. Petr. T. VIII. p. 105 sqq. Eo magis est mirandum, demonstrationes propositionum ad residua $+2$ et $-2$ pertinentium, prorsus similibus artificiis innixas, semper ipsius sagacitatem fugisse. Vid. etiam comment. ill. La Grange, Nouv. Mém. de l'Ac. de Berlin, 1775 p. 352.

Residua $+5$ et $-5$.

121.

Per inductionem deprehenditur, $+5$ nullius numeri imparis formae $5n+2$ vel $5n+3$ residuum esse, i. e. nullius numeri imparis, qui ipsius $5$ non-residuum sit. Hanc vero regulam nullam exceptionem pati, ita demonstratur. Sit numerus minimus, si quis datur, ab hac regula excipiendus $=t$, qui itaque numeri $5$ est non-residuum, $5$ autem ipsius $t$ residuum. Sit $aa=5+tu$, ita ut $a$ sit par ipsoque $t$ minor. Erit igitur $u$ impar ipsoque $t$ minor, $+5$ autem ipsius $u$ residuum erit. Quodsi iam $a$ per $5$ non est divisibilis, etiam $u$ non erit; manifesto autem $tu$ ipsius $5$ est residuum, quare quum $t$ ipsius $5$ sit non-residuum, etiam $u$ non-residuum erit; i. e. datur non-residuum impar numeri $5$, cuius residuum est $+5$, ipso $t$ minus, contra hyp. Si vero $a$ per $5$ est divisibilis, ponatur $a=5b$, atque $u=5v$, unde $\textstyle tv\equiv$ $-1\equiv$ $\textstyle 4{\pmod {5}}$, i. e. $tv$ erit residuum numeri $5$. In reliquis demonstratio perinde procedit ut in casu priori.

122.

Omnium igitur numerorum primorum, qui simul sunt ipsius $5$ non-residua simulque formae $4n+1$, i. e. omnium numerorum primorum formae $20n+3$ vel $20n+17$, tum $+5$ quam $-5$ non-residua erunt; omnium autem numerorum primorum formae $20n+3$ vel $20n+7$, non-residuum erit $+5$, $-5$ residuum.

Potest vero prorsus simili modo demonstrari, $-5$ esse non-residuum omnium numerorum primorum formarum $20n+11$, $20n+13$, $20n+17$, $20n+19$, facileque perspicitur hinc sequi, $+5$ esse residuum omnium numerorum primorum formae $20n+11$ vel $20n+19$, non-residuum autem omnium formae $20n+13$ vel $20n+17$. Et quoniam quivis numerus primus, praeter $2$ et $5$ (quorum residuum $\pm 5$), in aliqua harum formarum continetur $20n+1$, $3$, $7$, $9$, $11$, $13$, $17$, $19$, patet, de omnibus iam iudicium ferri posse, exceptis iis, qui sint formae $20n+1$ vel formae $20n+9$.

123.

Ex inductione facile deprehenditur, $+5$ et $-5$ esse residua omnium numerorum primorum formae $20n+1$ vel $20n+9$. Quodsi hoc generaliter verum est, lex elegans habebitur, $+5$ esse residuum omnium numerorum primorum, qui ipsius $5$ sint residua, (hi enim in alterutra formarum $5n+1$ vel $5n+4$ sive in aliqua harum, $20n+1$, $9$, $11$, $19$, continentur, de quarum tertia et quarta illud iam ostensum est) non-residuum vero omnium numerorum imparium, qui ipsius $5$ sint non-residua, ut iam supra demonstravimus. Clarum autem est, hoc theorema sufficere, ad diiudicandum, utrum $+5$ (eoque ipso, $-5$, si tamquam productum ex $+5$ et $-1$ consideretur) numeri cuiuscunque dati residuum sit an non-residuum. Denique observetur huius theorematis cum illo, quod art. 120 de residuo $-3$ exposuimus, analogia.

At verificatio illius inductionis non adeo facilis. Quando numerus primus formae $20n+1$, sive generalius formae $5n+1$ proponitur, res simili modo absolvi potest, ut in artt. 114, 119. Sit scilicet numerus quicunque pro modulo $5n+1$ ad exponentem $5$ pertinens $a$, quales dari ex Sect. praec. manifestum, eritque $a^{5}\equiv 1$, sive $(a-1)(a^{4}+a^{3}+a^{2}+a+1)\equiv$ $\textstyle 0{\pmod {5n+1}}$. At quia nequit esse $a\equiv 1$, neque adeo $a-1\equiv 0$; necessario erit $a^{4}+a^{3}+a^{2}+a+1\equiv 0$. Quare etiam $(a^{4}+a^{3}+a^{2}+a+1)=$ $(2aa+a+2)^{2}-5a^{2}\!$ erit $\equiv 0$ i. e. $5a^{2}\!$ erit residuum ipsius $5n+1$, adeoque etiam $5$, quia $a^{2}\!$ est residuum per $5n+1$ non divisibile ($a$ enim per $5n+1$ non divisibilis propter $a^{5}\equiv 1$). Q. E. D.

At casus, ubi numerus primus formae $5n+4$ proponitur, subtiliora artificia postulat. Quoniam vero propositiones, quarum ope negotium absolvitur, in sequentibus generalius tractabuntur, hic breviter tantum eas attingimus.

I. Si $p$ est numerus primus atque $b$ non-residuum quadraticum datum ipsius $p$, valor expressionis $(A)\ldots {\frac {(x+\surd {b})^{p+1}-(x-\surd {b})^{p+1}}{\surd {b}}}$ (ex qua evoluta irrationalitatem abire facile perspicitur), semper per $p$ divisibilis erit, quicunque numerus pro $x$ assumatur. Patet enim ex inspectione coëfficientium, qui ex evolutione ipsius $A$ obtinentur, omnes terminos a secundo usque ad penultimum (incl.) per $p$ divisibiles fore, adeoque esse $A\equiv$ $2(p+1)$$\textstyle (x^{p}+xb^{\scriptstyle {\frac {p-1}{2}}}){\pmod {p}}$. At quoniam $b$ ipsius $p$ non-residuum est, erit $b^{\scriptstyle {\frac {p-1}{2}}}\equiv$ $\textstyle -1{\pmod {p}}$, (art. 106); $x^{p}\!$ autem semper est $\equiv x$ (Sect. praec.), unde fit $A\equiv 0$. Q. E. D.

II. In congruentia $\textstyle A\equiv 0{\pmod {p}}$, indeterminata $x$ habet $p$ dimensiones omnesque numeri $0$, $1$, $2$ $\ldots$ $p-1$ illius radices erunt. Iam ponatur $e$ esse divisorem ipsius $p+1$ eritque expressio ${\frac {(x+\surd {b})^{e}-(x-\surd {b})^{e}}{\surd {b}}}$ (quam per $B$ designamus) si evolvitur, ab irrationalitate libera, indeterminata $x$ in ipsa $e-1$ dimensiones habebit, constatque ex analyseos primis elementis, $A$ per $B$ (indefinite) esse divisibilem. Iam dico $e-1$ valores ipsius $x$ dari, quibus in $B$ substitutis, $B$ per $p$ divisibilis evadat. Ponatur enim $A\equiv BC$, habebitque $x$ in $C$ dimensiones $p-e+1$, adeoque congruentia $\textstyle C\equiv 0{\pmod {p}}$ non plures quam $p-e+1$ radices. Unde facile patet, omnes reliquos numeros ex his $0$, $1$, $2$, $3$ $\ldots$ $p-1$, quorum multitudo $=e-1$, congruentiae $B\equiv 0$ radices fore.

III. Iam ponatur $p$ esse formae $5n+4$, $e=5$, $b$ non-residuum ipsius $p$, atque numerum $a$ ita determinatum, ut sit ${\frac {(a+\surd {b})^{5}-(a-\surd {b})^{5}}{\surd {b}}}$ per $p$ divisibilis. At illa expressio fit $=10a^{4}+20aab+2bb=2((b+5aa)^{2}-20a^{4})$ Erit igitur etiam $(b+5aa)^{2}-20a^{4}\!$ per $p$ divisibilis i. e. $20a^{4}\!$ residuum ipsius $p$, at quoniam $4a^{4}\!$ residuum est per $p$ non divisibile (facile enim intelligitur, $a$ per $p$ dividi non posse), etiam $5$ residuum ipsius $p$ erit. Q. E. D.

Hinc patet theorema in initio huius articuli prolatum generaliter verum esse. —

Observamus adhuc, demonstrationes pro utroque casu ill. La Grange deberi, Mém. de l'Ac. de Berlin 1775, p. 352 sqq.

De $\pm 7$.

124.

Per similem methodum demonstratur,
$-7$ esse non-residuum cuiusvis numeri, qui ipsius $7$ sit non-residuum.

Ex inductione vero concludi potest,
$-7$ esse residuum cuiusvis numeri primi, qui ipsius $7$ sit residuum.

At hoc a nemine hactenus rigorose demonstratum. Pro iis quidem residuis ipsius $7$, quae sunt formae $4n-1$, facilis est demonstratio; etenim per methodum ex praecc. abunde notam ostendi potest, $+7$ semper esse talium numerorum primorum non-residuum, adeoque $-7$ residuum. Sed parum hinc lucramur: reliqui enim casus per hanc methodum tractari nequeunt. Unum quidem adhuc casum simili modo ut artt. 119, 123 absolvere possumus. Scilicet si $p$ est numerus primus formae $7n+1$, atque $a$ pro modulo $p$ ad exponentem $7$ pertinens, facile perspicitur ${\tfrac {4(a^{7}-1)}{a-1}}=(2a^{3}+a^{2}-a-2)^{2}+7(a^{2}+a)^{2}$ per $p$ divisibilem, adeoque $-7(a^{2}+a)^{2}\!$ ipsius $p$ residuum fore. At $(a^{2}+a)^{2}\!$, tamquam quadratum, ipsius $p$ residuum est, insuperque per $p$ non divisibile; quum enim $a$ ad exponentem $7$ pertinere supponatur, neque $\equiv 0$, neque $\textstyle \equiv -1{\pmod {p}}$ esse potest, i. e. neque $a$ neque $a+1$ per $p$ divisibilis erit, adeoque etiam quadratum $(a+1)^{2}a^{2}\!$. Unde manifesto etiam $7$ ipsius $p$ residuum erit. Q. E. D. — At primi numeri formae In $7n+2$ vel $7n+4$ omnes methodos hucusque traditas eludunt. Ceterum etiam haec demonstratio ab ill. La Grange primum est detecta l. c. — Infra Sect. VII. docebimus generaliter, expressionem ${\tfrac {4(x^{p}-1)}{x-1}}$ semper ad formam $X^{2}\mp pY^{2}$ reduci posse, (ubi signum superius est accipiendum, quando $p$ est numerus primus formae $4n+1$, inferius, quando est formae $4n+3$), denotantibus $X$, $Y$ functiones rationales ipsius $x$, a fractionibus liberas. Hanc discerptionem ill. La Grange ultra casum $p=7$ non perfecit v. l. c. p. 352.

Praeparatio ad disquisitionem generalem.

125.

Quoniam igitur methodi praecedentes ad demonstrationes generales stabiliendas non sufficiunt, iam tempus est, aliam ab hoc defectu liberam exponere. Initium facimus a theoremate, cuius demonstratio satis diu operam nostram elusit, quamvis primo aspectu tam obvium videatur, ut quidam ne necessitatem quidem demonstrationis intellexerint. Est vero hoc: Quemvis numerum, praeter quadrata positive sumta, aliquorum numerorum primorum non-residuum esse. Quia vero hoc theoremate tantummodo tamquam auxiliari ad alia demonstranda usuri sumus, alios casus hic non explicamus quam quibus ad hunc finem indigemus. De reliquis casibus postea sponte idem constabit. Ostendemus itaque, quemvis numerum primum formae $4n+1$, sive positive sive negative accipiatur^[6], non-residuum esse aliquorum numerorum primorum, et quidem (si $>5$) talium qui ipso sint minores.

Primo, quando numerus primus $p$, formae $4n+1$ ($>17$, sed $-13N3$, $-17N5$), negative sumendus proponitur, sit $2a$ numerus par proxime maior quam $\surd {p}$, tum facilis perspicitur, $4aa$ semper fore $<2p$ sive $4aa-p<p$. At $4aa-p$ est formae $4n+3$, $+p$ autem residuum quadraticum ipsius $4aa-p$ (quoniam $\textstyle p\equiv 4aa{\pmod {4aa-p}}$); quodsi igitur $4aa-p$ est numerus primus, $-p$ ipsius non-residuum erit; sin minus, necessario factor aliquis ipsius $4aa-p$ formae $4n+3$ erit; et quum $+p$ etiam huius residuum esse debeat, $-p$ ipsius non-residuum erit. Q. E. D.

Pro numeris primis positive sumendis duos casus distinguimus. Primo sit $p$ numerus primus formae $8n+5$. Sit $a$ numerus quicunque positivus $<\surd {\scriptstyle {\frac {1}{2}}}p$. Tum $8n+5-2aa$ erit numerus positivus formae $8n+5$ vel $8n+3$ (prout $a$ par vel impar) adeoque necessario per numerum aliquem primum formae $8n+3$ vel $8n+5$ divisibilis, productum enim ex quotcunque numeris formae $8n+1$ et $8n+7$ neque formam $8n+3$ neque hanc $8n+5$ habere potest. Sit hic $q$, eritque $\textstyle 8n+5\equiv 2a^{2}\!{\pmod {q}}$. At $2$ ipsius $q$ non-residuum erit (art. 112), adeoque etiam $2a^{2}$^[7] et $8n+5$. Q. E. D.

126.

Sed numerum quemvis primum formae $8n+1$ positive acceptum semper alicuius numeri primi ipso minoris non-residuum esse, per artificia tam obvia demonstrari nequit. Quum autem haec veritas maximi sit momenti, demonstrationem rigorosam, quamvis aliquantum prolixa sit, praeterire non possumus. Praemittimus sequens

Lemma. Si habentur duae series numerorum, $A,B,C,\mathrm {etc.} \ldots \mathrm {(I)}$, $\quad A',B',C',\mathrm {etc.} \ldots \mathrm {(II)}$ (utrum terminorum multitudo in utraque eadem sit necne, nihil interest) ita comparatae, ut, denotante $p$ numerum quemcunque primum aut numeri primi potestatem, terminum aliquem secundae seriei (sive etiam plures) metientem, totidem ad minimum termini in serie prima sint per $p$ divisibiles, quot sunt in secunda: tum dico productum ex omnibus numeris $\mathrm {(I)}$ divisibile fore per productum ex omnibus numeris $\mathrm {(II)}$.

Exempl. Constet $\mathrm {(I)}$ e numeris 12, 18, 45; $\mathrm {(II)}$ ex his 3, 4, 5, 6, 9. Tum divisibiles erunt per 2, 4, 3, 9, 5 in $\mathrm {(I)}$ 2, 1, 3, 2, 1 termini, in $\mathrm {(II)}$ 2, 1, 3, 1, 1 termini, respective; productum autem omnium terminorum $\mathrm {(I)}$ = 9720 divisibile est per productum omnium terminorum $\mathrm {(II)}$, 3240.

Demonstr. Sit productum ex omnibus terminis $\mathrm {(I)}$, $=Q$, productum omnium terminorum seriei $\mathrm {(II)}$, $=Q'\!$. Patet quemvis numerum primum, qui sit divisor ipsius $Q'\!$, etiam ipsius $Q$ divisorem fore. Iam ostendemus quemvis factorem primum ipsius $Q'\!$, in $Q$ totidem ad minimum dimensiones habere, quot habeat in $Q'\!$. Esto talis divisor $p$, ponaturque, in serie $\mathrm {(I)}$ $a$ terminos esse per $p$ divisibiles, $b$ terminos per $p^{2}\!$ divisibiles, $c$ terminos per $p^{3}\!$ divisibiles etc., similia denotent literae $a'\!$, $b'\!$, $c'\!$ etc. pro serie $\mathrm {(II)}$, perspicieturque facile, $p$ in $Q$ habere $a+b+c+$ etc. dimensiones, in $Q'\!$ vero $a'+b'+c'+$ etc. At $a'\!$ certe non maior quam $a$, $b'\!$ non maior quam $b$ etc. (hyp.); quare $a'+b'+c'\!$ etc. certo non erit $>a+b+c$ etc. — Quum itaque nullus numerus primus in $Q'\!$ plures dimensiones habere possit, quam in $Q$, $Q$ per $Q'\!$ divisibilis erit (art. 17). Q. E. D.

127.

Lemma. In progressione $1$, $2$, $3$, $4$, $\ldots$ $n$, plures termini esse nequeunt per numerum quemcunque $h$ divisibiles, quam in hac $a$, $a+1$, $a+2$ $\ldots$ $a+n-1$ ex totidem terminis constante.

Nullo enim negotio perspicitur, si $n$ fuerit multiplum ipsius $h$, in utraque progressione ${\tfrac {n}{h}}$ terminos fore per $h$ divisibiles; sin minus, ponatur $n=eh+f$, ita ut $f$ sit $<h$, eruntque in priori serie $e$ termini per $h$ divisibiles, in posteriori autem vel toti dem vel $e+1$.

Hinc tamquam Coroll. sequitur propositio ex numerorum figuratorum theoria nota, sed a nomine, ni fallimur, hactenus directe demonstrata, $a\ .\ a+1\ .\ a+2\ldots a+n-1 \over 1\quad .\quad 2\quad .\quad 3\quad \ldots \quad n\quad$ semper esse numerum integrum.

Denique Lemma hoc generalius ita proponi potuisset:

In progressione $a$