Fermats lilla sats
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2016-08) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
Fermats lilla sats säger att om p är ett primtal 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 ä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 , så och satsen gäller. Antag att satsen gäller för alla . Då har vi att . Om nu , så är
- Nu till koefficienten .
- Om p är ett primtal är inga av faktorerna i k! eller (p - k)! delare till p.
- Eftersom är ett heltal måste då vara ett heltal.
- Om p är ett primtal är inga av faktorerna i k! eller (p - k)! delare till p.
, om p är ett primtal
det vill säga , 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 ä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:
Om båda sidor multipliceras med a fås:
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
Externa länkar
- Wikimedia Commons har media som rör Fermats lilla sats.
Media som används på denna webbplats
Författare/Upphovsman: Tkgd2007, Licens: CC BY-SA 3.0
A new incarnation of Image:Question_book-3.svg, which was uploaded by user AzaToth. This file is available on the English version of Wikipedia under the filename en:Image:Question book-new.svg