Petit teorema de Fermat

De Viquipèdia
Dreceres ràpides: navegació, cerca

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, apa (mod p)


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)


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.[1]

Història[modifica | modifica el codi]

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

Així doncs, matemàtics xinesos formularen la hipòtesi (a vegades coneguda com "hipòtesi xinesa") que p és primer si i només si 2p ≡ 2 (mod p) (on el símbol ≡ significa congruència segons el mòdul indicat). És veritat que, si p és primer, aleshores 2p ≡ 2 (mod p) (aquest és un cas especial del petit teorema de Fermat), però el recíproc (si 2p ≡ 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 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 ap-1 - 1 quan p sigui primer i a sigui coprimer amb p.[4]

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.[5] 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.[6]

« 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ó[modifica | modifica el codi]

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

« 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.[7] En donaria dues més al llarg de la seva vida,[8] 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.[9] Gauss publicaria una altra prova més al seu llibre Disquisitiones arithmeticae el 1801.[5][10]

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.[11] É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 n1 a n+1, es compleix per n1 i n1+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} \,\!
(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 np - 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é, 1p - 1 és divisible per p, per tant 2p - 2 també és divisible per p, i així successivament.

Q.E.D.

Exemples[modifica | modifica el codi]

A continuació es mostren alguns exemples del teorema:

  • 53 - 5 = 120 és divisible per 3.
  • 72 - 7 = 42 és divisible per 2.
  • 25 - 2 = 30 és divisible per 5.
  • (-3)7 + 3 = - 2.184 és divisible per 7.
  • 297 - 2 = 158.456.325.028.528.675.187.087.900.670 és divisible per 97.

Aplicacions[modifica | modifica el codi]

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[modifica | modifica el codi]

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:[12]

« 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 no són tots primers.[13]

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.

Criptografía asimètrica[modifica | modifica el codi]

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[modifica | modifica el codi]

Article principal: Test de primalitat

El petit teorema de Fermat dóna una condició necessària perquè un nombre p sigui primer. És necessari que, per tot nombre natural a més petit que p, ap-1 - 1 sigui divisible per p, o sigui, que ap-1 sigui congruent amb un mòdul p (en notació moderna com ap - 1 ≡ 1 (mod p)). Aquest principi és la base del test de primalitat de Fermat.[14] Aquest test, pel qual s'assumeix una entrada n, consisteix en anar provant que an-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.

  1. Per j\,\! des de 1\,\! fins a k\,\! faci el següent:
    1. a \gets Funció genera un nombre aleatori comprès entre 1\,\! i n\,\! (sense incloure'ls)
    2. Si a^{n-1} \not \equiv 1 \pmod n aleshores:
      1. Retorni COMPOST
  2. 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[modifica | modifica el codi]

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.[15] 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 ap-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 2341-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[modifica | modifica el codi]

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 mn (mod p-1), aleshores aman (mod p) per tots els enters a.[5] 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 de 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.[16]

Referències[modifica | modifica el codi]

  1. Wiles, Andrew; Taylor, Richard. «Modular elliptic curves and Fermat last theorem.». Annals of Mathematics, 3, 141, 1995. p. 443-551.
  2. Sun Zi Sunzi suanjing Manual de matemàtica de Sun Zi del segle III.
  3. Joseph Needham (Ed.) Mathematics and the Sciences of the Heavens and the Earth Science and Civilisation in China, Vol. 3 Ch. 19 Cambridge University Press, 1959
  4. 4,0 4,1 David Zhao. «Carta de Pierre de Fermat a Frénicle de Bessy», 2004. [Consulta: 3 de maig].(traducción paral·lela del francès a l'anglès)
  5. 5,0 5,1 5,2 Gauss, Carl Friedrich. «Cap.3 Powers' residues». A: Disquisitiones Arithmeticae. Yale University Press, 1965. ISBN 0-300-09473-6. . (traducció al castellà)
  6. School of Mathematics and Statistics, University of St Andrews, Scotland. «Biografia de Kurt Hensel», 2006. [Consulta: 3 de maig].
  7. Euler, Leonhard. «Theorematum Quorundam a Numeros Primos Spectantium Demonstratio». Commentarii academiae scientiarum Petropolitanae, 8, 1741. p. 141-146.. (traducció paral·lela del llatí a l'anglès)
  8. Santiago Fernández i Antonio Pérez Sanz. «Historia de las Matemáticas. Biografía de Leonhard Euler», 2004. [Consulta: 3 de maig].
  9. Chris K. Caldwell. «Proof of Fermat's Little Theorem - The primes page.», 1994. [Consulta: 3 de maig].
  10. Hugo Barrantes, Michael Josephy i Angel Ruiz. «Disquisitiones Arithmeticae - Versió espanyola», 2006. [Consulta: 3 de maig].
  11. Dep. de matemàtica - Universitat de Buenos Aires. «Números naturales, principio de inducción.», 2005. [Consulta: 6 de maig].
  12. Pierre de Fermat Lettre à Marin Mersenne du 7 avril 1643 llegiu-lo
  13. Euler, Leonhard. «Theoremata circa divisores numerorum». Commentarii academiae scientiarum Petropolitanae, 1, 1750. p. 20-48.. (traducció paral·lela del llatí a l'anglès)
  14. Chris Caldwell. «Finding primes & proving primality», 1994. [Consulta: 3 de maig].
  15. Mathworld.Wolfram.com. «Pseudoprime.», 2008. [Consulta: 7 de maig].
  16. Mathworld.Wolfram.com. «Carmichel's theorem.», 2008. [Consulta: 7 de maig].

Bibliografia[modifica | modifica el codi]

  • 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. 

Vegeu també[modifica | modifica el codi]