Mostra la font per a Petit teorema de Fermat

[[Fitxer:Pierre de Fermat.jpg|miniatura|[[Pierre de Fermat]].]]
El '''petit teorema de [[Pierre de Fermat|Fermat]]''' és un dels [[teorema|teoremes]] clàssics de [[teoria de nombres]] relacionat amb la [[divisibilitat]]. Es formula de la següent manera:

{{teorema
|1=Si ''p'' és un [[nombre primer]], aleshores, per cada [[nombre natural]] ''a'', ''a''<sup>p</sup> ≡ ''a'' (mod ''p'') 
|2=[[Pierre de Fermat]], 1636
}}

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

{{teorema
|1=Si ''p'' és un [[nombre primer]], aleshores, per cada [[nombre natural]] ''a'' [[coprimer]] amb ''p'', ''a''<sup>p-1</sup> ≡ 1 (mod ''p'') 
|2=[[Pierre de Fermat]], 1636
}}

<!--
'''Formalment:'''
<br />
:::''Sigui'' <math>a, \, p \in \mathbb{N} \; / \; p \mbox{ és primer } \wedge \; p \nmid a, ''aleshores...''
:::<math>\exist n \in \mathbb{N} \; / \; n | (p-1) \; \wedge \; p | (a^{\frac{(p-1)}{n}}-1)</math>.
<br />
-->
Això vol dir que, si s'eleva un nombre ''a'' a la ''p''-èsima [[potenciació|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 [[test de primalitat|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]].<ref>{{ref-publicació| autor = Wiles, Andrew; Taylor, Richard|títol= Modular elliptic curves and Fermat last theorem.|any= 1995|publicació= Annals of Mathematics|volum= 3|exemplar= 141| id = p. 443-551
| url = http://math.stanford.edu/~lekheng/flt/wiles.pdf}}</ref>

== Història ==

La civilització xinesa sembla que fou la primera cultura en estar interessada en l'[[aritmètica modular]].<ref>Sun Zi ''Sunzi suanjing'' Manual de matemàtica de [[Sun Zi (matemàtic)|Sun Zi]] del [[segle III]].</ref> Existeix una hipòtesi,<ref>[[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</ref> documentada per [[Joseph Needham]], segons la qual els nombres de la forma 2<sup>p</sup> - 2 foren estudiats per aquesta civilització.

Així doncs, [[matemàtica xinesa|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<sup>p</sup> ≡ 2 (mod ''p'') (on el símbol ≡ significa [[congruència]] segons el ''mòdul'' indicat). És veritat que, si ''p'' és primer, aleshores 2<sup>p</sup> ≡ 2 (mod ''p'') (aquest és un cas especial del petit teorema de Fermat), però el [[recíproc]] (si 2<sup>p</sup> ≡ 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|s}}. 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 [[Bernard Frenicle de Bessy|Frénicle de Bessy]], datada el [[18 d'octubre]] del [[1640]], amb el següent text: ''p'' divideix ''a''<sup>p-1</sup> - 1 quan ''p'' sigui primer i ''a'' sigui [[coprimer]] amb ''p''.<ref name="carta">{{ref-web|url = http://www.cs.utexas.edu/users/wzhao/fermat2.pdf|títol = Carta de Pierre de Fermat a Frénicle de Bessy|consulta = 3 de maig|autor = David Zhao|any = 2004}}(traducción paral·lela del francès a l'anglès)</ref>

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]]''.<ref name="Gauss">{{ref-llibre| autor = Gauss, Carl Friedrich|capítol= Cap.3 Powers' residues|títol= Disquisitiones Arithmeticae|any= 1965| editorial = Yale University Press| id = {{ISBN|0-300-09473-6}}}}. [http://www.cimm.ucr.ac.cr/da/files/sec3arts45-93.pdf (traducció al castellà)]</ref> El terme ''petit teorema de Fermat'', tal com es coneix actualment, fou utilitzat per primera vegada pel [[matemàtic]] [[Alemanya|alemany]] [[Kurt Hensel]] el 1913 al seu llibre ''Zahlentheorie''.<ref>{{ref-web| url = http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Hensel.html| títol = Biografia de Kurt Hensel 
|consulta = 3 de maig | autor = School of Mathematics and Statistics, University of St Andrews, Scotland| any = 2006}}</ref>
{{cita|1=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.
|2=Kurt Hensel
}}

== Demostració ==
{{principal|Demostracions del petit teorema de Fermat}}

[[Fermat]] establí tal resultat en una carta a [[Bernard Frénicle de Bessy|Frénicle de Bessy]], però com a era habitual en ell, n'ometé la prova:<ref name="carta"></ref>
{{cita|1=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.
|col2=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.|2=Pierre de Fermat}}

[[Fitxer:Leonhard Euler 2.jpg|miniatura|[[Leonhard Euler]] donaria la primera [[demostració matemàtica|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''.<ref> {{ref-publicació| autor = Euler, Leonhard|títol= Theorematum Quorundam a Numeros Primos Spectantium Demonstratio|any= 1741
|publicació= Commentarii academiae scientiarum Petropolitanae|exemplar= 8| id = p. 141-146| url = http://www.cs.utexas.edu/users/wzhao/e054.pdf}}. (traducció paral·lela del llatí a l'anglès)</ref> En donaria dues més al llarg de la seva vida,<ref>{{ref-web| url = http://divulgamat.ehu.es/weborriak/historia/MateOspetsuak/Euler2.asp| títol = Historia de las Matemáticas. Biografía de Leonhard Euler| consulta = 3 de maig | autor = Santiago Fernández i Antonio Pérez Sanz| any = 2004}}</ref> 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.<ref>{{ref-web| url = http://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html| títol = Proof of Fermat's Little Theorem - The primes page.| consulta = 3 de maig | autor = Chris K. Caldwell| any = 1994}}</ref> [[Carl Friedrich Gauß|Gauss]] publicaria una altra prova més al seu llibre ''[[Disquisitiones arithmeticae]]'' el [[1801]].<ref name="Gauss"></ref><ref>{{ref-web| url = http://www.cimm.ucr.ac.cr/da/| títol = Disquisitiones Arithmeticae - Versió espanyola | consulta = 3 de maig | autor = Hugo Barrantes, Michael Josephy i Angel Ruiz| any = 2006}}</ref>

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ó matemática|demostració]] es basa en el [[inducció matemàtica|principi d'inducció]], que consisteix en demostar que si certa propietat ''P'' dels [[nombre natural|nombres naturals]] es compleix per ''n'' i també es compleix per ''n''+1, aleshores es compleix per tot ''n''.<ref>{{ref-web| url = http://mate.dm.uba.ar/~spuddu/inducc.pdf| títol = Números naturales, principio de inducción.| consulta = 6 de maig | autor = Dep. de matemàtica - Universitat de Buenos Aires| any = 2005}}</ref> É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''<sub>1</sub> a ''n''+1, es compleix per ''n''<sub>1</sub> i ''n''<sub>1</sub>+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]] <math>\textstyle{p \choose n}</math> és divisible per ''p'', per tot ''n'', tal que 1 ≤ ''n'' < ''p''.
Això és així car el [[coeficient binomial]] es defineix com:

:<math>{p \choose n} = \frac{p!}{(p-n)!\cdot n!}</math>

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 [[factorial]]s 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 <math>\textstyle{p \mid n^p-n} \,\!</math>

* S'utilitza el [[binomi de Newton]] per expandir la potència (''n'' + 1)<sup>p</sup>:

: <math>(n+1)^p=\sum_{k=0}^{p}{p \choose k}n^{p-k}</math>

* Agrupant factors i reordenant la identitat:

: <math>(n+1)^p-(n+1)=n^p-n+\sum_{k=1}^{p-1}{p \choose k}n^{p-k}</math>

* Per [[hipòtesi]], s'ha suposat que ''n''<sup>p</sup> - ''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)<sup>p</sup> - (''n'' + 1).

* Ara bé, 1<sup>p</sup> - 1 és divisible per ''p'', per tant 2<sup>p</sup> - 2 també és [[divisible]] per ''p'', i així successivament.

[[Quod erat demonstrandum|Q.E.D.]]

== Exemples ==
A continuació es mostren alguns exemples del teorema: 
* 5<sup>3</sup> - 5 = 120 és divisible per 3.
* 7<sup>2</sup> - 7 = 42 és divisible per 2.
* 2<sup>5</sup> - 2 = 30 és divisible per 5. 
* (-3)<sup>7</sup> + 3 = - 2.184 és divisible per 7.
* 2<sup>97</sup> - 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|matemàtiques pures]], sobretot, relacionades amb el [[test de primalitat|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]]:<ref>[[Pierre de Fermat]] ''Lettre à Marin Mersenne'' du 7 avril 1643 [http://primes.utm.edu/mersenne/LukeMirror/lit/lit_067s.htm llegiu-lo]</ref> 

{{cita|1=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. |2=Pierre de Fermat}}

Utilitzant un mètode anàleg, [[Euler]] invalidà l'única [[conjectura]] falsa de Fermat, és a dir, que els [[nombre primer de Fermat|nombres de Fermat]] no són tots primers.<ref>{{ref-publicació| autor = Euler, Leonhard|títol= Theoremata circa divisores numerorum|any= 1750|publicació= Commentarii academiae scientiarum Petropolitanae|exemplar= 1| id = p. 20-48| url = http://www.cs.utexas.edu/users/wzhao/e134.pdf}}. (traducció paral·lela del llatí a l'anglès)</ref>

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 [[endomorfisme de Frobenius#Punts fixos a l'endomorfisme de Frobenius|puntos fixos]] de l'[[endomorfisme de Frobenius]], per exemple.

=== Criptografía asimètrica ===
{{principal|Criptografia asimètrica}}
La criptografia amb clau pública correspon a un [[criptografia|codi]] que s'afegeix per assegurar la [[confidencialitat]] dels missatges amb l'ajuda de dues [[clau (criptografia)|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 [[Teorema fonamental de l'aritmètica|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 ===
{{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'', ''a''<sup>p-1</sup> - 1 sigui divisible per ''p'', o sigui, que ''a''<sup>p-1</sup> sigui [[congruència|congruent]] amb ''un'' mòdul ''p'' (en notació moderna com ''a''<sup>p - 1</sup> ≡ 1 (mod ''p'')). Aquest principi és la base del [[test de primalitat de Fermat]].<ref>
{{ref-web| url = http://primes.utm.edu/prove/prove2_2.html
| títol = Finding primes & proving primality
| consulta = 3 de maig | autor = Chris Caldwell
| any = 1994}}</ref> 
Aquest test, pel qual s'assumeix una entrada ''n'', consisteix en anar provant que ''a''<sup>n-1</sup> ≡ 1 (mod ''n'') per una sèrie de valors de ''a'', tals que siguin més petits que ''n''. Si ''n'' és [[nombre primer|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''' <math>j\,\!</math> des de <math>1\,\!</math> fins a <math>k\,\!</math> '''faci el següent:'''
## <math>a \gets</math> '''Funció''' genera un nombre aleatori comprès entre <math>1\,\!</math> i <math>n\,\!</math> (sense incloure'ls)
## '''Si''' <math>a^{n-1} \not \equiv 1 \pmod n </math> '''aleshores:'''
### '''Retorni''' COMPOST
# '''Retorni''' POSSIBLE PRIMER
}}

Existeixen nombroses variants [[algorisme|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 ===
{{principal|Nombre pseudoprimer}}
Els test precedents utilitzen una [[condició necessària]] però no suficient. Tant és així que existeixen nombres enters ''p'' [[nombre compost|compostos]] i [[coprimer]]s amb ''a'' tal que ''a'' <sup>p-1</sup> és congruent amb ''un'' mòdul ''p'', són els anomenats [[pseudoprimer]]s.<ref>
{{ref-web| url = http://mathworld.wolfram.com/Pseudoprime.html
| títol = Pseudoprime.
| consulta = 7 de maig
| autor = Mathworld.Wolfram.com 
| any = 2008}}</ref> 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 [[pseudoprimer]]s, per exemple, els que compleixen que ''a''<sup>p-1</sup> ≡ 1 (mod ''p'') per tots els valors de ''a'' que siguin [[coprimer]]s 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<sup>341-1</sup> ≡ 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 [[pseudoprimer]]s 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''<sup>m</sup> ≡ ''a''<sup>n</sup> (mod ''p'') per tots els enters ''a''.<ref name="Gauss"></ref> Expressat així, el teorema s'utilitza per justificar el [[criptografia|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é:
:<math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>
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é:

:<math>a^{\lambda (n)} \equiv 1 \pmod{n}</math>

on ara λ(''n'') és la [[funció de Carmichael]].<ref>{{ref-web| url = http://mathworld.wolfram.com/CarmichaelsTheorem.html| títol = Carmichel's theorem.| consulta = 7 de maig | autor = Mathworld.Wolfram.com| any = 2008}}</ref>

== Referències ==
{{referències}}

== Bibliografia ==

* {{ref-llibre|cognom= Ribenboim
|nom= Paul
|títol= The New Book of Prime Number Records (3a ed.)
|any= 1995
| editorial = Nova York: Springer-Verlag
| id = {{ISBN|0-387-94457-5}}
}}
* {{ref-llibre|cognom= Gauss
|nom= Carl Friedrich
|títol= Disquisitiones Arithmeticae, tr. Arthur A. Clarke
|any= 1965
| editorial = Yale University Press
| id = {{ISBN|0-300-09473-6}}
}}

{{ORDENA:Petit Teorema De Fermat}}

[[Categoria:Teoremes de teoria de nombres]]