Sistem complet și redus de reziduuri, matematică, care îmi place

10. completă și sistem redus de reziduuri

Definiția. Numerele formează un sistem complet de reziduuri modulo dacă orice număr întreg modulo congruent cu unul și numai unul dintre aceste numere.

Orice sistem complet de Modulo reziduuri este format din numere care sunt reciproc modulo congruente.

Teorema. Să - un sistem complet de modulo reziduuri. Să - un număr întreg, care este relativ prim sa. Apoi, - de asemenea, un sistem complet de reziduuri modulo.

Dovada. Trebuie să demonstreze că numărul de Modulo congruente pairwise. Să presupunem contrariul. lăsa

Deoarece GCD, ceea ce contrazice.

Teorema. Să - un sistem complet de modulo reziduuri. Să - număr întreg. Apoi, - de asemenea, un sistem complet de reziduuri modulo.

Lema. În cazul în care, apoi GCD GCD.

a-b = km, \ k "title =" o \ echiv b \ pmod \ Longrightarrow a-b \ vdots m \ Longrightarrow
a-b = km, \ k "style =" vertical-align: -4px; frontieră: none; „> - număr întreg.

Aici. Orice divizor comun și un divizor. De aici GCD GCD.

Definiția. Numerele formează redus modulo sistem de reziduuri în cazul în care acestea sunt cu orice prime între ele întreg cu comparabile prime între ele cu unul și numai unul dintre aceste numere este modulo.

Exemplu. Sistem redus de reziduuri modulo 10: 1,3,7,9.

Lema. Toate sistemul de reziduuri Modulo constau din același număr de numere, care este desemnat - funcția Euler.

Dovada. Într-adevăr, să presupunem că există două modulo sistem redus de reziduuri constând dintr-un număr diferit de numere:

Apoi, din moment ce forma sistemului redus de reziduuri modulo, fiecare dintre numerele comparabile cu unul și numai unul dintre aceste numere. De atunci, principiul colț retras, cel puțin două dintre numerele sunt comparabile cu unele număr, și, prin urmare, va fi modulo congruente. Dar acest lucru contrazice faptul că - sistemul redus de reziduuri modulo. Înseamnă.

Demonstrăm acum asta. De fapt, numere mai mici și relativ prime pentru a forma sistemul redus de reziduuri modulo. Acest lucru rezultă din lema.

Definiția. funcția Euler (sau totient) reprezintă numărul de numere întregi mai mici și relativ la prim.

Teorema. În cazul în care - sistem redus de reziduuri modulo și - număr prim cu, apoi - sistem a redus, de asemenea, a reziduurilor modulo.

În cazul în care - simplu, atunci.

Lema. În cazul în care - simplu, atunci.

Dovada. Într-adevăr, numerele mai simple și au un divizor comun cu el, totul.

Lema. Să GCD. Apoi. Funcția multiplicativ Euler.

Dovada. Să ne scrie toate numerele de la 1 la urmează:
123 \ ldotsa \\
a + 1a + 2a + 3 \ ldots2a \\
2a + 12a + 22a + 3 \ ldots3a \\
\ Ldots \\
(B-1) a + 1 (b-1) a + 2 (b-1) a + 3 \ ldotsab
\ End "title =" \ începe
123 \ ldotsa \\
a + 1a + 2a + 3 \ ldots2a \\
2a + 12a + 22a + 3 \ ldots3a \\
\ Ldots \\
(B-1) a + 1 (b-1) a + 2 (b-1) a + 3 \ ldotsab
\ End "style =" vertical-align: -49px; frontieră: none; „>

Numerele din fiecare rând formează un sistem complet de modulo reziduuri. Deci, prim-una dintre ele. Cu toate acestea, aceste numere sunt aranjate în coloane - una sub alta, deoarece fiecare coloană sunt modulo congruente numerele.

Numerele din fiecare coloană formează un sistem complet de modulo reziduurilor. Într-adevăr, coloana-lea se obține prin luarea numărul, formează un sistem complet de reziduuri Modulo, le înmulțește cu numărul de prim-cu, și adăugate la fiecare dintre ele.

Astfel, fiecare coloană exact număr relativ prime pentru a.

Deoarece numărul este prim pentru a dacă și numai dacă este prim și un prim este de a, cantitatea de numere prime relativ la, oricum.

Dovada. Conform lema asupra funcției multiplicativ, lui Euler

p_n ^) = \ varphi (p_1 ^) \ varphi (p_2 ^) \ ldots \ varphi (p_n ^). "title =" \ varphi (p_1 ^ p_2 ^ \ ldots
p_n ^) = \ varphi (p_1 ^) \ varphi (p_2 ^) \ ldots \ varphi (p_n ^) "style =" vertical-align: -6px ;. frontieră: none; „>

Și apoi vom calcula fiecare dintre Lema privind calculul funcțiilor Euler pentru numere prime.

Teorema (Euler). În cazul în care - sunt numere prime relativ,

Să - orice sistem redus de reziduuri modulo. . Apoi - sistem a redus, de asemenea, a reziduurilor modulo. Prin urmare, fiecare dintre numerele de prima secvență este comparabilă cu una din a doua secvență de numere modulo, iar fiecare din al doilea număr de secvență este comparabilă cu una dintre primele numere de secventa. atunci

Din moment ce fiecare dintre numerele prime relativ la acestea, atunci ei au o comparație poate fi redusă:
x ^ k \ equiv1 \ pmod \\
x ^ \ equiv1 \ pmod.
\ End "title =" \ începe
x ^ k \ equiv1 \ pmod \\
x ^ \ equiv1 \ pmod.
\ End "style =" vertical-align: -16px; frontieră: none; „>

Corolar. Să - numere întregi - naturale. În cazul în care, GCD, atunci.

Dovada. Să. De atunci - un număr natural. atunci

Se spune că o zi în timp ce Euler insomnie calculat șase grade de primele 100 de numere, iar rezultatele sunt repetate în memorie, după mai multe zile. Alteori Euler testarea numărului care rezultă din ele, calculată în primele 20 de ore numărul de zecimale.

În 1741, Euler, la invitatia lui Frederick al II-lea, a sosit de la Sankt-Petersburg la Academia de Științe din Berlin. Oamenii de știință au luat cu mare onoare. Pe una dintre recepții regale la palatul mamei regelui a atras atenția asupra Euler, el îi spune monosilabic „da“ și „nu“. „De ce, nu vrei să vorbești cu mine?“ - a întrebat Euler. „Doamnă, - a spus omul de știință - Eu vin dintr-o țară în care cei care spun spânzurat.“ răspunsul lui Euler arată în cazul în care condițiile dificile a trebuit să lucreze în Academia St. Petersburg din timp.

Cunoscutul matematician francez Per Ferma (1601-1665) a fost un avocat de profesie. În teoria numerelor, numele său este asociat cu celebra teorema, teorema lui Fermat și Little Teorema lui Fermat. Geometria a fost predecesorul imediat agricole Descartes. El a jucat un rol important în ferma de naștere a teoriei probabilității. În lucrările lui Fermat au primit dezvoltare sistematică a diferențierii și integrării. Numele unității de principiu variational legate de ferma de sisteme optice geometrice.

1. Dovedește că, dacă - a redus sistem de reziduuri modulo, apoi.

2. Dovedește că, dacă - un număr prim, atunci (teorema lui Wilson).

3. Dovedește că, dacă - un număr prim, și apoi există un număr întreg, care este divizibil cu.

4. Dovedește că, dacă - număr întreg, și - un prim divizor de ciudat, atunci.

5. Dovedește că, dacă - a redus sistem de reziduuri modulo, apoi.

6. Dovedește că, dacă - sistem redus de reziduuri modulo există, astfel încât, atunci.

7. Găsiți resturile modulo.

8. Dovedește că, dacă - numere întregi și este divizibil cu 30, apoi împărțit la 30.

9. Să se arate că, dacă - numere întregi, și - un număr prim, atunci.

10. și - amorse distincte. Demonstrați că.

11. Să se arate că nu se divide deloc pe numărul.