Teorema mică a lui Fermat

Teorema mică a lui Fermat spune că dacă $p$ ${\ displaystyle p}$ $p$ este un număr prim , apoi pentru orice număr întreg $la$ ${\ displaystyle a}$ $la$ :

a^{p}\equiv a{\pmod {p}}

{\ displaystyle a ^ {p} \ equals {\ pmod {p}}}

a ^ p \ este egal cu \ pmod {p}

Aceasta înseamnă că dacă luați orice număr $la$ ${\ displaystyle a}$ $la$ , se înmulțește de la sine $p$ ${\ displaystyle p}$ $p$ ori și scade $la$ ${\ displaystyle a}$ $la$ , rezultatul este divizibil cu $p$ ${\ displaystyle p}$ $p$ (vezi aritmetica modulară ). Se exprimă adesea sub forma echivalentă: dacă $p$ ${\ displaystyle p}$ $p$ este prim și $la$ ${\ displaystyle a}$ $la$ este un coprime întreg cu $p$ ${\ displaystyle p}$ $p$ , asa de:

a^{p-1}\equiv 1{\pmod {p}}

{\ displaystyle a ^ {p-1} \ equiv 1 {\ pmod {p}}}

a ^ {p-1} \ equiv 1 \ pmod {p}

Trebuie remarcat faptul că prima expresie este într-un anumit sens mai generală: este de fapt valabilă pentru numere întregi arbitrare, cum ar fi sau multipli ai $p$ ${\ displaystyle p}$ $p$ , care, pe de altă parte, nu se încadrează în ipotezele celei de-a doua.

Se numește mica teoremă a lui Fermat pentru a o diferenția de „ Ultima teoremă a lui Fermat .

Micuța teoremă a lui Fermat este baza testului de primărie Fermat .

Istorie

Pierre de Fermat a enunțat teorema în jurul anului 1636 ^{[ fără sursă ]} . Apare într-una din scrisorile sale, datată 18 octombrie 1640, confidențialului său Frenicle sub forma: $p$ ${\ displaystyle p}$ $p$ împarte $a^{p-1}-1$ ${\ displaystyle a ^ {p-1} -1}$ $a ^ {p-1} -1$ de sine $p$ ${\ displaystyle p}$ $p$ este primul și $la$ ${\ displaystyle a}$ $la$ Și $p$ ${\ displaystyle p}$ $p$ sunt coprimă.

Matematicienii chinezi au făcut independent ipoteza aferentă (numită uneori ipoteza chineză) că $p$ ${\ displaystyle p}$ $p$ este primul dacă și numai dacă $2^{p}=2{\pmod {p}}$ ${\ displaystyle 2 ^ {p} = 2 {\ pmod {p}}}$ $2 ^ p = 2 \ pmod {p}$ . Este adevărat că dacă $p$ ${\ displaystyle p}$ $p$ este mai întâi, apoi $2^{p}=2{\pmod {p}}$ ${\ displaystyle 2 ^ {p} = 2 {\ pmod {p}}}$ $2 ^ p = 2 \ pmod {p}$ (este un caz special al teoremei lui Fermat), dar invers (dacă $2^{p}=2{\pmod {p}}$ ${\ displaystyle 2 ^ {p} = 2 {\ pmod {p}}}$ $2 ^ p = 2 \ pmod {p}$ asa de $p$ ${\ displaystyle p}$ $p$ este prim) și, prin urmare, ipoteza în general, este falsă (de ex. $341=11\cdot 31$ ${\ displaystyle 341 = 11 \ cdot 31}$ $341 = 11 \ cdot 31$ este un pseudoprime vezi mai jos).

Este larg recunoscut faptul că ipoteza chineză a fost dezvoltată cu aproximativ 2.000 de ani înainte de lucrarea lui Fermat în anii 1600. Deși ipoteza este parțial greșită, este de remarcat faptul că era cunoscută matematicienilor antici. Unii, cu toate acestea, susțin că credința pe scară largă că ipoteza a fost răspândită atât de mult timp s-a născut dintr-o neînțelegere și că, de fapt, a fost dezvoltată în 1872 .

Demonstrații

Fermat și-a expus teorema fără o dovadă. Primul care a dovedit-o a fost Gottfried Wilhelm Leibniz într-un manuscris datat, unde a scris, de asemenea, că știe o demonstrație încă dinainte de 1683 .

Vedeți demonstrații ale teoremei lui Fermat .

Generalizări

O mică generalizare a teoremei, care urmează imediat din aceasta, este următoarea: dacă $p$ ${\ displaystyle p}$ $p$ este prim și $m$ ${\ displaystyle m}$ $m$ Și $n$ ${\ displaystyle n}$ $n$ sunt numere întregi pozitive cu $m\equiv n{\pmod {p-1}}$ ${\ displaystyle m \ equiv n {\ pmod {p-1}}}$ $m \ equiv n \ pmod {p-1}$ , asa de $a^{m}\equiv a^{n}{\pmod {p}}$ ${\ displaystyle a ^ {m} \ este egal cu ^ {n} {\ pmod {p}}}$ $a ^ m \ equiv a ^ n \ pmod p$ pentru fiecare număr întreg $la$ ${\ displaystyle a}$ $la$ . În această formă, teorema justifică cheia publică a sistemului de criptare RSA .

Teorema mică a lui Fermat este generalizată de teorema lui Euler : pentru fiecare modul $n$ ${\ displaystyle n}$ $n$ și fiecare întreg $la$ ${\ displaystyle a}$ $la$ coprimă cu privire la $n$ ${\ displaystyle n}$ $n$ , avem:

a^{\varphi (n)}\equiv 1{\pmod {n}}

{\ displaystyle a ^ {\ varphi (n)} \ equiv 1 {\ pmod {n}}}

a ^ {\ varphi (n)} \ equiv 1 \ pmod {n}

Unde este $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ $\ varphi (n)$ Acesta indică funcția phi a lui Euler , care numără numărul întreg între $1$ ${\ displaystyle 1}$ $1$ și $n$ ${\ displaystyle n}$ $n$ acoperă-mă cu privire la $n$ ${\ displaystyle n}$ $n$ . Este o generalizare în faptul că dacă $n=p$ ${\ displaystyle n = p}$ $n = p$ este un număr prim, atunci $\varphi (p)=p-1$ ${\ displaystyle \ varphi (p) = p-1}$ $\ varphi (p) = p-1$ .

Acest lucru poate fi generalizat în continuare cu funcția Carmichael .

Teorema are o generalizare frumoasă și în câmpurile finite .

Pseudo-primul

De sine $la$ ${\ displaystyle a}$ $la$ Și $p$ ${\ displaystyle p}$ $p$ sunt numere coprimă astfel încât $a^{p-1}-1$ ${\ displaystyle a ^ {p-1} -1}$ $a ^ {p-1} -1$ este divizibil cu $p$ ${\ displaystyle p}$ $p$ , nu este necesar ca. $p$ ${\ displaystyle p}$ $p$ este un număr prim. Dacă nu este, atunci $p$ ${\ displaystyle p}$ $p$ Se numește pseudoprime Off Base $la$ ${\ displaystyle a}$ $la$ . În 1820 F. Sarrus a descoperit că $341=11\cdot 31$ ${\ displaystyle 341 = 11 \ cdot 31}$ $341 = 11 \ cdot 31$ este una dintre primele pseudoprime în raport cu baza $2$ ${\ displaystyle 2}$ $2$ .

Un număr $p$ ${\ displaystyle p}$ $p$ care este pseudoprimo în raport cu baza $la$ ${\ displaystyle a}$ $la$ pentru fiecare $la$ ${\ displaystyle a}$ $la$ coprimo cu privire la $p$ ${\ displaystyle p}$ $p$ Se numește numărul lui Carmichael . Un exemplu al numărului lui Carmichael este $561$ ${\ displaystyle 561}$ $561$ .

Bibliografie

H. Davenport, top Arithmetic, Editura Wadsworth, 1994, ISBN 88-08-09154-6 - Capitolul II.3

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe teorema lui Fermat Small

linkuri externe

(EN) Teorema lui Fermat ^{[ Link rupt ]} pe cut-the-knot.org.
(EN) Funcția și teorema Euler ^{[ Link rupt ]} pe cut-the-knot.org.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

V · D · M Teoria numerelor
Cele mai utilizate numere	Natural · Întreg · Par și impar
Principii generale	Principiul inducției · Principiul unei bune ordonări · Relația de echivalență
Secvențe de numere întregi	Factorial · Fibonacci · Număr de catalană · Număr Perrin · Număr de Euler · Secvență Mian-Chowla · Succesiunea lui Thue-Morse
Caracteristicile numerelor prime	Primul număr · lema lui Euclid · Teorema infinitate de numere prime · ciurul Eratostene · teste primality · Teorema fundamentală a aritmeticii · Total acoperire mine · Bézout Identitate · MCD · mcm · algoritmul lui Euclid · Teorema de Prime Numbers
Funcții aritmetice	Funcție multiplicativă · funcție aditivă · Convoluție Dirichlet · Funcția Euler Euler · Funcția Möbius · funcția tau pe pozitiv · funcția sigmoidă · Funcția Liouville · Funcția Mertens
Aritmetica modulară	Teorema a restului chinez · teorema lui Fermat mici · teorema lui Euler · Criterii de divizibilitate · teorema lui Fermat pe sume de două pătrate · Wilson Teorema · reciprocitatea pătratică
Conjecturi	Conjectura lui Goldbach · Conjectura Polignac · Guess abc · conjectura primelor gemene · Conjectura lui Legendre · Noua conjectură Mersenne · Conjectura Collatz · Ipoteza Riemann
Alte	Problema lui Waring
Principalii teoreticieni	Fibonacci · Fermat · Gauss · Euler · Legendre · Riemann · Dirichlet
Disciplinele conexe	Teoria algebrică a numerelor · Teoria analitică a numerelor · Criptografie · Teoria computațională a numerelor