Fermats lilla sats

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif
icon_anmal.gif
rp-wp-sv.gif

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

a^p \equiv a\ (\operatorname{mod}\ p)

Detta betyder att om man tar ett tal a, multiplicerar det med sig självt p gånger och subtraherar a så ä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 ap-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.

Innehåll

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.

Här är ett induktionsbevis för satsen:

Om a = 1, så 1^p \equiv 1\ (\operatorname{mod}\ p) och satsen gäller.
Antag att satsen gäller för alla a \leq n. Då har vi att n^p \equiv n\ (\operatorname{mod}\ p).
Om nu a = n + 1, så är
ap = (n + 1)p
\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
\equiv n^p + p \cdot n^{p-1} + p \cdot { (p-1)! \over 2!(p-2)!} \cdot n^{p-2} + ... + p \cdot n^1 + 1 \pmod p
\equiv n^p + 1 \pmod p
\equiv n + 1 \pmod p ,
det vill säga a^p\equiv a\ (\operatorname{mod}\ p), och satsen gäller.

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 ap-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

Hämtad från "https://sv.rilpedia.org/wiki/Fermats_lilla_sats"
Personliga verktyg