Fermats lilla sats

Gottfried Wilhelm von Leibniz bevisade satsen.

Fermats lilla sats säger att om p är ett primtal gäller för varje heltal a att

<math>a^p \equiv a\ (\operatorname{mod}\ p)</math>

Detta betyder att om man tar ett tal a, multiplicerar det med sig självt p gånger och subtraherar a är resultatet delbart med p (se modulär aritmetik). Satsen kallas för Fermats lilla sats för att skilja den från Fermats stora sats. Pierre de Fermat upptäckte satsen runt 1636. Den nämndes i ett av hans brev, daterat 18 oktober 1640, i följande ekvivalenta form: p delar a^{p -1} - 1 närhelst p är ett primtal och a och p är relativt prima. Fallet för a = 2 var känt av de forntida kineserna.

Bevis

Fermat förklarade sin sats utan bevis. Den första som gav ett bevis var Gottfried Wilhelm Leibniz i ett manuskript utan datum, i vilket han också skrev att han kände till ett bevis före 1683.

Induktionsbevis

Fermats lilla sats kan bevisas med matematisk induktion.

Om <math>a = 1</math>, så <math>1^p \equiv 1\ (\operatorname{mod}\ p)</math> och satsen gäller. Antag att satsen gäller för alla <math>a \leq n</math>. Då har vi att <math>n^p \equiv n\ (\operatorname{mod}\ p)</math>. Om nu <math>a = n+1</math>, så är

<math>\equiv n^p + {p \choose 1}n^{p-1} \cdot 1 + {p \choose 2}n^{p-2} \cdot 1^2 + ... + {p \choose p-1}n^1 \cdot 1^{p-1} + 1^p \pmod p</math><math>\equiv n^p + \sum_{k=1}^{p-1} { p! \over k!(p-k)!} \cdot n^{p-k} + 1 \equiv n^p + p\sum_{k=1}^{p-1} { p! \over k!(p-k)!\cdot p} \cdot n^{p-k} + 1 \pmod p</math>

Nu till koefficienten <math> { p! \over k!(p-k)!\cdot p} </math>.

Om p är ett primtal är inga av faktorerna i k! eller (p - k)! delare till p.

Eftersom <math> { p! \over k!(p-k)!} </math> är ett heltal måste då <math> { p! \over k!(p-k)!\cdot p} </math>vara ett heltal.

<math>\equiv n^p + 1 \pmod p </math>, om p är ett primtal

<math>\equiv n + 1 \pmod p </math>

det vill säga <math>a^p\equiv a\ (\operatorname{mod}\ p)</math>, och satsen gäller.

Gruppteoretiskt bevis

Fermats lilla sats kan även bevisas med hjälp av gruppteori:

Låt p vara ett primtal och G vara gruppen bestående av elementen 1, 2, ..., p - 1 under operationen multiplikation modulo p. Gruppen har då ordningen p - 1. Ta nu ett element a i G (dvs, a ligger mellan 1 och p - 1) och låt k vara a:s ordning (dvs det minsta k så att <math>a^k</math> är 1).

Enligt Lagranges sats är k en delare i G:s ordning, p - 1, dvs p - 1 = kn, för något heltal n. Man får att:

<math>a^{p-1} \equiv a^{kn} \equiv \left( a^k \right)^n \equiv 1^n \equiv 1 \pmod p.</math>

Om båda sidor multipliceras med a fås:

<math>a^p \equiv a \pmod p.</math>

Generaliseringar

Fermats lilla sats kan generaliseras till Eulers sats, vilken kan ytterligare generaliseras till Carmichaels sats.

Pseudoprimtal

Om a och p är relativt prima tal sådana att a^{p -1} - 1 är delbart med p, då behöver inte p vara ett primtal. Om det inte är ett primtal kallas p ett pseudoprimtal till basen a. Ett tal p som är ett pseudoprimtal till basen a för varje a relativt primt med p kallas ett Carmichaeltal.

Se även

Fermats stora sats

Externa länkar

Fil:Commons-logo.svg Wikimedia Commons har media som rör Fermats lilla sats.
Bilder & media