Sammansatt tal, test

Fermats lilla sats (se wiki) säger:

• Om $n$ är ett primtal, så gäller att  $a^n \equiv a (\mod n)$ för alla heltal $a$.

Det kontrapositiva påståendet (som är ekvivalent med satsen ovan) lyder:

• Om det finns ett heltal $a$ sådant att $a^n \not\equiv a (\mod n)$, så är $n$ inte ett primtal.

I din fråga är alltså $a = 2$ och man kan formulera det kontrapositiva påståendet:

• Om $2^n \not\equiv 2 (\mod n)$, så är $n$ inte ett primtal, d.v.s. $n$ är ett sammansatt tal.

Hur blir det med (n-1) i exponenten?

Fermats lilla sats har en ekvivalent formulering med n-1 i exponenten (se wiki som jag länkat ovan):

• Om $n$ och $a$ är relativt prima heltal och samtidigt $n$ är ett primtal, så gäller att  $a^{n-1} \equiv 1 (\mod n)$.

Det ekvivalenta kontrapositiva påståendet lyder då:

• Om $a^{n-1} \not\equiv 1 (\mod n)$, så är $n$ inte ett primtal eller så är $n$ och $a$ inte relativt prima.

I din fråga är $a=2$, så om $2^{n-1} \not\equiv 1 (\mod n)$, så är antingen $n$ inte ett primtal, eller så är $2$ och $n$ inte relativt prima. Frågan är vad det egentligen innebär att $2$ och $n$ inte är relativt prima...

Eftersom $2$:an är ett primtal, så innebär det att $n$ är delbart med $2$.

Slutsats:

Om $2^{n-1} \not\equiv 1 (\mod n)$ så gäller:

• antingen $n=2$,
• eller så är $n$ ett sammansatt tal.

ytrewq skrev:

Edit: tror jag hittade det nu, detta test är 100% säkert för att identifiera att något är ett sammansatt tal:

$2^{n-1}\not\equiv 1 (mod n)$

Dock så är $2^{n-1}\equiv 1 (mod n)$ inte ett 100% säkert test för att identifiera att något är ett primtal. 

Låter det korrekt? :)

Detta stämmer. Det finns tal som kallas för carmichael tal. Dessa är sammansatta tal som uppfyller fermats lilla sats för alla tal $a$. Ställer lite problem för primtalstalstester eftersom de ofta förlitar sig på fermats lilla sats! 

Tack för detta, då är jag med på banan! :)