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.
Pierre de Fermat formulerade satsen. 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

a p ≡ a   ( mod ⁡   p ) {\displaystyle 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 ä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 a = 1 {\displaystyle a=1} , så 1 p ≡ 1   ( mod ⁡   p ) {\displaystyle 1^{p}\equiv 1\ (\operatorname {mod} \ p)} och satsen gäller. Antag att satsen gäller för alla a ≤ n {\displaystyle a\leq n} . Då har vi att n p ≡ n   ( mod ⁡   p ) {\displaystyle n^{p}\equiv n\ (\operatorname {mod} \ p)} . Om nu a = n + 1 {\displaystyle a=n+1} , så är

a p = ( n + 1 ) p {\displaystyle a^{p}=(n+1)^{p}} ≡ n p + ( p 1 ) n p − 1 ⋅ 1 + ( p 2 ) n p − 2 ⋅ 1 2 + . . . + ( p p − 1 ) n 1 ⋅ 1 p − 1 + 1 p ( mod p ) {\displaystyle \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}}} ≡ n p + ∑ k = 1 p − 1 p ! k ! ( p − k ) ! ⋅ n p − k + 1 ≡ n p + p ∑ k = 1 p − 1 p ! k ! ( p − k ) ! ⋅ p ⋅ n p − k + 1 ( mod p ) {\displaystyle \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}}} Nu till koefficienten p ! k ! ( p − k ) ! ⋅ p {\displaystyle {p! \over k!(p-k)!\cdot p}} . Om p är ett primtal är inga av faktorerna i k! eller (p - k)! delare till p. Eftersom p ! k ! ( p − k ) ! {\displaystyle {p! \over k!(p-k)!}} är ett heltal måste då p ! k ! ( p − k ) ! ⋅ p {\displaystyle {p! \over k!(p-k)!\cdot p}} vara ett heltal.

≡ n p + 1 ( mod p ) {\displaystyle \equiv n^{p}+1{\pmod {p}}} , om p är ett primtal

≡ n + 1 ( mod p ) {\displaystyle \equiv n+1{\pmod {p}}}

det vill säga a p ≡ a   ( mod ⁡   p ) {\displaystyle a^{p}\equiv a\ (\operatorname {mod} \ p)} , 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 a k {\displaystyle a^{k}} ä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:

a p − 1 ≡ a k n ≡ ( a k ) n ≡ 1 n ≡ 1 ( mod p ) . {\displaystyle a^{p-1}\equiv a^{kn}\equiv \left(a^{k}\right)^{n}\equiv 1^{n}\equiv 1{\pmod {p}}.}

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

a p ≡ a ( mod p ) . {\displaystyle a^{p}\equiv a{\pmod {p}}.}

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