Petit teorema de Fermat

Pierre de Fermat.

El petit teorema de Fermat és un dels teoremes clàssics de teoria de nombres relacionat amb la divisibilitat. Es formula de la següent manera:

Si p és un nombre primer, aleshores, per cada nombre natural a, ap ≡ a (mod p) Pierre de Fermat, 1636

Tot i que són equivalents, el teorema sol ser presentat d'aquesta altra forma:

Si p és un nombre primer, aleshores, per cada nombre natural a coprimer amb p, ap-1 ≡ 1 (mod p) Pierre de Fermat, 1636

Això vol dir que, si s'eleva un nombre a a la p-èsima potència i al resultat se li resta a, el que queda és divisible per p (vegeu aritmètica modular). El seu interès principal rau en la seva aplicació al problema del primalitat i en criptografia.

Aquest teorema no té res a veure amb el llegendari últim teorema de Fermat, que fou només una conjectura durant 350 anys i finalment fou demostrat per Andrew Wiles el 1995.

Història

La civilització xinesa sembla que fou la primera cultura en estar interessada en l'aritmètica modular. Existeix una hipòtesi, documentada per Joseph Needham, segons la qual els nombres de la forma 2^p - 2 foren estudiats per aquesta civilització.

Així doncs, matemàtics xinesos formularen la hipòtesi (a vegades coneguda com a "hipòtesi xinesa") que p és primer si i només si 2^p ≡ 2 (mod p) (on el símbol ≡ significa congruència segons el mòdul indicat). És veritat que, si p és primer, aleshores 2^p ≡ 2 (mod p) (aquest és un cas especial del petit teorema de Fermat), però el recíproc (si 2^p ≡ 2 (mod p), aleshores p és primer) no ho és, per la qual cosa la hipòtesi és falsa.

Es creu àmpliament que la hipòtesi xinesa fou desenvolupada 2.000 anys abans del treball de Fermat al segle xvii. Encara que la hipòtesi sigui parcialment incorrecta, és notable que pugui haver estat coneguda pels matemàtics de l'antiguitat. Alguns, tanmateix, sostenen que la creença que aquesta hipòtesi fos coneguda fa tant de temps és fruit d'un error de comprensió, i que es desenvolupà realment el 1872. Per a més informació sobre aquest assumpte, consulteu (Ribenboim, 1995).

Al voltant del 1636, Pierre de Fermat enuncià el teorema. Apareix en una de les seves cartes al seu confident Frénicle de Bessy, datada el 18 d'octubre del 1640, amb el següent text: p divideix a^p-1 - 1 quan p sigui primer i a sigui coprimer amb p.

Tot i que actualment se'l coneix com petit teorema de Fermat, el cert és que fins al segle xx fou conegut com teorema de Fermat, com ho recull per exemple Carl Friedrich Gauss al seu llibre Disquisitiones arithmeticae. El terme petit teorema de Fermat, tal com es coneix actualment, fou utilitzat per primera vegada pel matemàtic alemany Kurt Hensel el 1913 al seu llibre Zahlentheorie.

«	Heus aquí el teorema fonamental que es compleix a cada grup finit, anomenat habitualment petit teorema de Fermat, perquè Fermat fou el primer en provar-ne una part especial.	»
— Kurt Hensel

Demostració

Fermat establí tal resultat en una carta a Frénicle de Bessy, però com a era habitual en ell, n'ometé la prova:

«	Tout nombre premier mesure infailliblement une des puissances -1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné -1. (...) Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.	Tot nombre primer mesura una de les potències menys un de qualsevol progressió en què l'exponent és un múltiple del primer donat menys un. (...) I aquesta proposició és generalment certa per totes les progressions i tots els nombres primers; li n'enviaria la prova, si no temés ser massa llarg.	»
— Pierre de Fermat

Leonhard Euler donaria la primera demostració formal del teorema el 1736.

La primera demostració publicada es deu a Leonhard Euler el 1736 en un article titulat Theorematum Quorundam a Numeros Primos Spectantium Demonstratio. En donaria dues més al llarg de la seva vida, tot i que era la primera de totes elles la mateixa que hi havia en un manuscrit personal de Gottfried Leibniz, escrit vers el 1683 i que mai no arribà a publicar. Gauss publicaria una altra prova més al seu llibre Disquisitiones arithmeticae el 1801.

La prova original d'Euler (i Leibniz) és senzilla en termes de comprensió lògica, car només utilitza mètodes elementals que una persona amb nocions bàsiques d'àlgebra pot entendre. La seva demostració es basa en el principi d'inducció, que consisteix en demostar que si certa propietat P dels nombres naturals es compleix per n i també es compleix per n+1, aleshores es compleix per tot n. És fàcil veure que si es compleix per n, i per n+1, també es compleix per n+2, n+3, etc. car, anomenant com n₁ a n+1, es compleix per n₁ i n₁+1, per tant, per n, n+1 i n+2, i així successivament.

Per la demostració també s'utilitza la propietat que si p és un nombre primer, aleshores el coeficient binomial $\textstyle {p \choose n}$ és divisible per p, per tot n, tal que 1 ≤ n < p. Això és així car el coeficient binomial es defineix com:

${p \choose n}={\frac {p!}{(p-n)!\cdot n!}}$

On el signe ! correspon al factorial d'un nombre, que indica la multiplicació de tots els nombres naturals menors o iguals a aquest nombre, per exemple, p! = p·(p-1)·(p-2)·...·2·1. Com que en el denominador, els factorials dels nombres impliquen nombres que són menors que el nombre primer p, aquests no poden contenir p ni dividir el nombre primer p del numerador, així doncs, el coeficient és divisible per p.

Dit això, la demostració consisteix en els següents passos:

• Suposant que $\textstyle {p\mid n^{p}-n}\,\!$

• S'utilitza el binomi de Newton per expandir la potència (n + 1)^p:

$(n+1)^{p}=\sum _{k=0}^{p}{p \choose k}n^{p-k}$

• Agrupant factors i reordenant la identitat:

$(n+1)^{p}-(n+1)=n^{p}-n+\sum _{k=1}^{p-1}{p \choose k}n^{p-k}$

• Per hipòtesi, s'ha suposat que n^p - n és divisible per p, i com que tots els termes del sumatori del membre de la dreta són divisibles per p, es troba que p divideix (n + 1)^p - (n + 1).

• Ara bé, 1^p - 1 és divisible per p, per tant 2^p - 2 també és divisible per p, i així successivament.

Q.E.D.

Exemples

A continuació es mostren alguns exemples del teorema:

• 5³ - 5 = 120 és divisible per 3.
• 7² - 7 = 42 és divisible per 2.
• 2⁵ - 2 = 30 és divisible per 5.
• (-3)⁷ + 3 = - 2.184 és divisible per 7.
• 2⁹⁷ - 2 = 158.456.325.028.528.675.187.087.900.670 és divisible per 97.

Aplicacions

Les aplicacions són nombroses, particularment en criptografia. Tanmateix, hi ha exemples clàssics d'aplicacions del teorema en matemàtiques pures, sobretot, relacionades amb el problema de la primalitat.

Aplicacions teòriques

El petit teorema de Fermat s'ha utilitzat històricament per analitzar la descomposició en producte de factors primers de certs sencers. Així, Fermat escrigué a Marin Mersenne:

«	Vostè em demana si el nombre 100.895.598.169 és primer o no, i un mètode per descobrir, en el termini d'un dia, si és primer o compost. A aquesta pregunta, jo li responc que aquest nombre és compost i que s'obté del producte d'aquests dos: 898.423 i 112.303, que són primers.	»
— Pierre de Fermat

Utilitzant un mètode anàleg, Euler invalidà l'única conjectura falsa de Fermat, és a dir, que els nombres de Fermat són tots primers.

Aquest teorema també s'ha utilitzat per demostrar resultats de la teoria de nombres algebraics, com el teorema de Herbrand-Ribet. Ha sobrepassat l'àmbit estricte de l'aritmètica, amb una utilització per l'estudi dels puntos fixos de l'endomorfisme de Frobenius, per exemple.

Criptografia asimètrica

Article principal: Criptografia asimètrica

La criptografia amb clau pública correspon a un codi que s'afegeix per assegurar la confidencialitat dels missatges amb l'ajuda de dues claus criptogràfiques. Una, que permet xifrar el missatge, és pública. L'altra, que té com a objectiu el desxifratge, és privada.

Una important família de codis asimètrics utilitza la tecnologia anomenada RSA. La clau secreta està determinada per la descomposició d'un nombre enter gran, sovint de diverses centenes de xifres. Aquest té dos factors primers. L'essencial de les tècniques industrials de principis del segle xxi es basa en el petit teorema de Fermat per generar grans nombres primers o per comprovar la primalitat d'un nombre natural.

Test de primalitat

Article principal: Test de primalitat

El petit teorema de Fermat dona una condició necessària perquè un nombre p sigui primer. És necessari que, per tot nombre natural a més petit que p, a^p-1 - 1 sigui divisible per p, o sigui, que a^p-1 sigui congruent amb un mòdul p (en notació moderna com a^{p - 1} ≡ 1 (mod p)). Aquest principi és la base del test de primalitat de Fermat. Aquest test, pel qual s'assumeix una entrada n, consisteix en anar provant que a^n-1 ≡ 1 (mod n) per una sèrie de valors de a, tals que siguin més petits que n. Si n és primer, aleshores la congruència es complirá sempre (condició necessària del teorema) mentre que si n és compost, la congruència pot no complir-se. Si per algun valor de a (més petit que n) no es compleix la congruència, aleshores n és compost. Una descripció d'aquest test de forma general, en forma d'algorisme escrit en pseudocodi, podria ser la següent:

Algorisme Test de primalitat de Fermat.

entrada: Un nombre natural n>1, el nombre k de vegades que s'executa el test i determina la fiabilitat del test. Sortida: COMPOST si n és compost i POSSIBLE PRIMER si n és un possible primer. Per $j\,\!$ des de $1\,\!$ fins a $k\,\!$ faci el següent: $a\gets$ Funció genera un nombre aleatori comprès entre $1\,\!$ i $n\,\!$ (sense incloure'ls) Si $a^{n-1}\not \equiv 1{\pmod {n}}$ aleshores: Retorni COMPOST Retorni POSSIBLE PRIMER

Existeixen nombroses variants algorítmiques que utilitzen com base aquest test. Les més conegudes són el test de primalitat de Solovay-Strassen i sobretot el test de primalitat de Miller-Rabin.

Nombre pseudoprimer

Article principal: Nombre pseudoprimer

Els test precedents utilitzen una condició necessària però no suficient. Tant és així que existeixen nombres enters p compostos i coprimers amb a tal que a ^p-1 és congruent amb un mòdul p, són els anomenats pseudoprimers. Aquests nombres tenen la peculiaritat que poden passar el test de primalitat de Fermat algunes vegades, sent reconeguts com a falsos primers. Existeixen diverses classes de pseudoprimers, per exemple, els que compleixen que a^p-1 ≡ 1 (mod p) per tots els valors de a que siguin coprimers amb p, sent p compost es denominen nombres de Carmichael. El nombre 1.729 és un exemple de nombre de Carmichael. A més existeixen altres pseudoprimers que només es compleixen per una base a concreta, per exemple, si a és igual a 2, 341 compleix que 2^341-1 ≡ 1 (mod 341), sent tanmateix un nombre compost: 341 = 11⋅31.

Els tests indicats a la secció anterior són tots estadístics, en el sentit que existeix sempre una probabilitat, a vegades molt feble, que el nombre que ha passat el test no sigui primer, a causa dels pseudoprimers o el nombre de comprovacions.

Generalitzacions

Una petita generalització del teorema, que se'n segueix, diu el següent: si p és primer i m i n són enters positius amb m ≡ n (mod p-1), aleshores a^m ≡ aⁿ (mod p) per tots els enters a. Expressat així, el teorema s'utilitza per justificar el mètode de xifratge de clau pública RSA.

El petit teorema de Fermat es pot generalitzar mitjançant el teorema d'Euler; per qualsevol mòdul n i qualsevol enter a coprimer amb n, es té:

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

on f(n) és la funció f d'Euler que compta el nombre d'enters entre 1 i n coprimers amb n. Aquesta és de fet una generalització, car si n = p és un nombre primer, aleshores φ(p) = p - 1.

Tot i això, encara es pot generalitzar més, com es mostra al teorema de Carmichael. Com abans, per qualsevol mòdul n i qualsevol enter a coprimer amb n, es té:

$a^{\lambda (n)}\equiv 1{\pmod {n}}$

on ara λ(n) és la funció de Carmichael.

Bibliografia

• Ribenboim, Paul. The New Book of Prime Number Records (3a ed.). Nova York: Springer-Verlag, 1995. ISBN 0-387-94457-5. 
• Gauss, Carl Friedrich. Disquisitiones Arithmeticae, tr. Arthur A. Clarke. Yale University Press, 1965. ISBN 0-300-09473-6.