Funcția Euler φ (a) este definită pentru toate numerele naturale a și reprezintă numărul de numere naturale care sunt relativ prime la a. și nu depășește a. Se presupune că φ (1) = 1. Această funcție este calculată din formula
unde
![Funcția Euler (rezolvă prin metoda lui Euler) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-ee0b8f4d.png)
Numărul de numere care compun sistemul redus de reziduuri este φ (m).
Proprietatea generală a unui sistem complet și redus de reziduuri
În cazul în care numerele
![Funcția Euler (această comparație are) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-bce2b776.png)
![Funcția Euler (euler) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-550149cd.png)
![Funcția Euler (sistem redus de reziduuri) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-8ab75323.png)
Arată că numerele 25, -20,16,46, -21,18,37, -17 constituie un sistem complet de reziduuri modulo 8.
Formăm întregul sistem de numere cu cel puțin ne-negativ
![Funcția Euler (această comparație are) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-2ea3f570.png)
![Funcția Euler (funcție) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-81439d26.png)
![Funcția Euler (această comparație are) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-7b182362.png)
Deci, aceste numere 0,1,2,3,4,5,6,7 formează un sistem complet de reziduuri modulo 8.
Teoremele Euler și Fermat
Lăsați x să treacă prin sistemul redus de reziduuri
![Funcția Euler (euler) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-90127185.png)
![Funcția Euler (euler) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-53d0c5f4.png)
![Funcția Euler (rezolvă prin metoda lui Euler) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-0b0a155c.png)
![Funcția Euler (funcție) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-290a74fa.png)
Pentru simplu p și a. nu divizibilă de p. noi avem
Această teoremă este un caz special al teoremei Euler, pentru m = p. Din (2) se poate obține cu ușurință o comparație foarte importantă
,
care este valabil pentru toate numerele întregi a. deoarece este valabil și pentru un multiplu de p.
Verificați teorema lui Euler pentru a = 5 și.
,
.
Găsiți restul diviziei
![Funcția Euler (sistem redus de reziduuri) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-f34bd2f6.png)
Pentru că, atunci. deoarece
![Funcția Euler (funcție) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-88697dc8.png)
.
Răspuns: restul necesar este de 32.
Comparațiile dintre gradul I (rezolvarea problemelor)
Rezolvați metoda de comparare a lui Euler. Verificați corectitudinea răspunsului înlocuind.
(3,5) = 1, atunci această comparație are o soluție unică (în sensul clasei de numere x mod m). Prin formula Euler,
![Funcția Euler (sistem redus de reziduuri) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-d4562b3e.png)
![Funcția Euler (această comparație are) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-56d5a578.png)
Rezolvați metoda de comparare a lui Euler.
(5.10) = 5, dar 7 nu este divizibil cu 5, deci această comparație nu are soluții.
Rezolvați metoda de comparare a lui Euler.
Deoarece (25.17) = 1, această comparație are o soluție. Această comparație este echivalentă cu comparația. Prin formula lui Euler avem.
![Funcția Euler (sistem redus de reziduuri) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-9ca3df1d.png)
.
Rezolvați o modalitate de a compara
(12,15) = 3. Prin urmare, această comparație are 3 soluții (în sensul claselor). Luați în considerare o comparație
care derivă din valoarea dată după o reducere de 3.
Prin formula lui Euler avem,.
Am găsit o soluție a congruenței (2). Soluția de comparație (1) este dată de formula, k = 0,1,2.
; ; .
Pentru a atribui dreptului la numărul 523 astfel de trei numere, astfel încât numărul rezultat din șase cifre să fie împărțit la 7.8.9.
Lăsați numărul x să fie atribuit. apoi, de unde. Valoarea x va fi un număr de trei cifre pentru t = 0 și t = 1. Avem
![Funcția Euler (euler) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-f7be1ba2.png)
![Funcția Euler (rezolvă prin metoda lui Euler) Funcția Euler](https://images-on-off.com/images/134/funktsiyaeylera-9532f06a.png)
523,152 împărțit la 7,8,9;
523656 este împărțit în 7,8,9.