Fermats lilla sats
Wikipedia
Fermats lilla sats säger att om p är ett primtal, så gäller för varje heltal a att
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ämdes 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.
[redigera] 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å
och satsen gäller. - Antag att satsen gäller för alla
. Då har vi att 
. - Om nu a = n + 1, så är
- ap = (n + 1)p
,
- ap = (n + 1)p
- det vill säga
, och satsen gäller.
[redigera] Generaliseringar
Fermats lilla sats kan generaliseras till Eulers sats, vilken kan ytterligare generaliseras till Carmichaels sats.
[redigera] 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.
