Mersenneprimtal

Hej!

Uppgift:

Låt a och n vara positiva heltal med $n \neq 1$ . Bevisa att om $a^{n} - 1$ är ett primtal så är $a = 2$ och n ett primtal.

Lösning:

Det är uppenbart att a > 1 eftersom 0 inte är ett primtal. Men att a inte kan vara större än 2 är inte lika uppenbart. När jag kollar på påståendet att n måste vara ett primtal så börjar jag kolla såhär:

Om n inte är ett primtal så kan vi skriva att $a^{n} - 1 = a^{x * y} - 1 = (a^{x})^{y} - 1 d ä r x, y \in {2, 3, 4, . . .}$ .

Men längre än så kommer jag inte.

Vilka primtal kan skrivas som $a^n-1$ ? 2 fungerar inte, 3 fungerar, 5 fungerar inte, 7 fungerar... Kolla några till! Vilka värden har du på a och n när det stämmer?

Detta är inget bevis, men det är lättare att komma fram till något om man vet vad man letar efter.

Tricket är väl att lägga märke till att polynomet $x^m - 1$ , där $m$ är ett positivt heltal, har roten $x = 1$ , dvs $x - 1$ är en faktor till polynomet. Se om du kan utnyttja detta för att bevisa båda påståendena.

Stokastisk skrev :
Tricket är väl att lägga märke till att polynomet $x^m - 1$ , där $m$ är ett positivt heltal, har roten $x = 1$ , dvs $x - 1$ är en faktor till polynomet. Se om du kan utnyttja detta för att bevisa båda påståendena.

Menar du att polynomet $x^{m} - 1 = 0$ ?

Well, tekniskt sett så är det där en ekvation. Det jag menar är polynomet $x^m - 1$ som jag skrev, är du med på att $x - 1$ delar detta polynom?

Kan ju också skriva vad kvoten är, eftersom det blir relevant.

Det gäller att $\frac{x^{m} - 1}{x - 1} = x^{m - 1} + x^{m - 2} + \dots + x + 1$ .

Stokastisk skrev :
Kan ju också skriva vad kvoten är, eftersom det blir relevant.
Det gäller att $\frac{x^{m} - 1}{x - 1} = x^{m - 1} + x^{m - 2} + \dots + x + 1$ .

Ja, när du skriver det så så ser jag att x-1 är en faktor till polynomet. Men inte hur jag ska använda det.

smaragdalena skrev :
Vilka primtal kan skrivas som $a^n-1$ ? 2 fungerar inte, 3 fungerar, 5 fungerar inte, 7 fungerar... Kolla några till! Vilka värden har du på a och n när det stämmer?
Detta är inget bevis, men det är lättare att komma fram till något om man vet vad man letar efter.

Varenda gång jag kan skriva ett primtal på formen som ges av uppgiften så är a=2 och n ett primtal. Alla andra gånger så har jag $2^{x} * b$ där b är ett positivt heltal. Ser dock inte hur jag ska bevisa det hela trots detta.

Om du låter $x = a$ och $m = n$ i polynomet, då har du att

$a^n - 1 = (a - 1)(a^{n - 1} + a^{n - 2} + \cdots + a + 1)$

Vad säger detta om $a$ om nu $a^n - 1$ är ett primtal?

Om $n = rs$ kan du då låta $x$ vara något för att kunna säga något om $r$ och $s$ ?

Stokastisk skrev :
Om du låter $x = a$ och $m = n$ i polynomet, då har du att
$a^n - 1 = (a - 1)(a^{n - 1} + a^{n - 2} + \cdots + a + 1)$
Vad säger detta om $a$ om nu $a^n - 1$ är ett primtal?

Om $n = rs$ kan du då låta $x$ vara något för att kunna säga något om $r$ och $s$ ?

Om $a^{n} - 1$ är ett primtal och eftersom $a^{n} - 1 = (a - 1) (a^{n - 1} + a^{n - 2} + \dots + a + 1)$ så måste $a - 1 = 1 \Rightarrow a = 2$ eftersom det annars inte är ett primtal.

Men jag kommer inte på något om $r$ och $s$ .

Japp, då vet du att a måste vara 2. Vad får du då om du låter $x = a^r$ då $n = rs$ ?

Stokastisk skrev :
Japp, då vet du att a måste vara 2. Vad får du då om du låter $x = a^r$ då $n = rs$ ?

Att $a^{r} = a^{\frac{n}{s}}$ ? Men varför låta $x = a^{r}$ ?

Får att $a^{n} = a^{r s} = x^{s}$

Man får att

$a^n - 1 = (a^r)^s - 1 = (a^r - 1)((a^r)^{s - 1} + (a^r)^{s - 2} + \cdots + a^r + 1)$

Stokastisk skrev :
Man får att
$a^n - 1 = (a^r)^s - 1 = (a^r - 1)((a^r)^{s - 1} + (a^r)^{s - 2} + \cdots + a^r + 1)$

Just det och då måste $a^{r} = 2 \Rightarrow r = 1 \Rightarrow$ n är ett primtal.

Jag undrar om det är så här det är tänkt att man ska lösa det. Finns ingen som helst ledtråd i boken. Finns inget enklare sätt tro?

Svara

Visa senaste svar