Euklids setning i bok XI sier at: Hvis 2[sup]n[/sup]-1 er et primtall, så er 2[sup]n-1[/sup] ( 2[sup]n[/sup]-1) et perfekt tall.
Vis at hvis 2[sup]n[/sup]-1 skal være et primtall, så må n være et primtall. (Hint: Vis at hvis ikke n er et primtall, så kan 2[sup]n[/sup]-1 faktoriseres).
Primtall, Euklids setning
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
Legger ut en oppgave for ninacath:
Tror denne er ganske grei:
Hvis n ikke er et primtall er n delelig med et tall p > 1. Da er det ganske lett å innse at 2[sup]n[/sup] - 1 er delelig med 2[sup]p[/sup] - 1 ved polynomdivisjon (vi velger senere at x=2):
(x[sup]n[/sup] - 1) : (x[sup]p[/sup] - 1) = x[sup]n-p[/sup] + x[sup]n-2p[/sup] + .... + x[sup]p[/sup] + 1
(At denne formelen stemmer ser du lettest ved å multiplisere med (x[sup]p[/sup]-1) på begge sider og se at alle x-faktorene i "midten" av rekka forsvinner ved den såkalte "teleskop"-effekten)
Vi ser her at hvis x=2 er svaret et helt tall, altså er (2[sup]n[/sup] - 1 ) delelig med (2[sup]p[/sup] - 1), et tall større enn 1, dersom n er delelig med p > 1. Vi har da vist at hvis 2[sup]n[/sup]-1 er et primtall må også n være et primtall.
Hvis n ikke er et primtall er n delelig med et tall p > 1. Da er det ganske lett å innse at 2[sup]n[/sup] - 1 er delelig med 2[sup]p[/sup] - 1 ved polynomdivisjon (vi velger senere at x=2):
(x[sup]n[/sup] - 1) : (x[sup]p[/sup] - 1) = x[sup]n-p[/sup] + x[sup]n-2p[/sup] + .... + x[sup]p[/sup] + 1
(At denne formelen stemmer ser du lettest ved å multiplisere med (x[sup]p[/sup]-1) på begge sider og se at alle x-faktorene i "midten" av rekka forsvinner ved den såkalte "teleskop"-effekten)
Vi ser her at hvis x=2 er svaret et helt tall, altså er (2[sup]n[/sup] - 1 ) delelig med (2[sup]p[/sup] - 1), et tall større enn 1, dersom n er delelig med p > 1. Vi har da vist at hvis 2[sup]n[/sup]-1 er et primtall må også n være et primtall.
-
Kjartan Mikkelsen
- Pytagoras
- Innlegg: 11
- Registrert: 10/12-2002 12:58
- Sted: Rælingen
Kan ikke se at den oppgaven hadde noe med perfekte tall å gjøre, hva på den siden der er det man kan bruke her? 
Det eneste jeg viste var at 2[sup]n[/sup] - 1 var delelig med 2[sup]p[/sup] - 1 dersom n var delelig med p, og det var dette oppgaven gikk ut på (å vise at 2[sup]n[/sup]-1 da ikke er et primtall)
Men ettersom oppgaven i starten nevner perfekte tall er det kanskje noe herfra som kan brukes også?
Det eneste jeg viste var at 2[sup]n[/sup] - 1 var delelig med 2[sup]p[/sup] - 1 dersom n var delelig med p, og det var dette oppgaven gikk ut på (å vise at 2[sup]n[/sup]-1 da ikke er et primtall)
Men ettersom oppgaven i starten nevner perfekte tall er det kanskje noe herfra som kan brukes også?
-
Kjartan Mikkelsen
- Pytagoras
- Innlegg: 11
- Registrert: 10/12-2002 12:58
- Sted: Rælingen
Neida, Thomas du har helt rett. Oppgaven spurte ikke etter perfekte tall, og ditt resonnement er selvfølgelig helt fint.
Tenkte bare at en link med litt info alltid er bra å ha. Siden sier litt om perfekte tall og deres relasjon til Mersenne tall som det jo var spørsmål om i oppgaven.
Og hvorfor n må være et primtall for at 2[sup]n[/sup]-1 skal være et primtall finner du hvis du klikker litt rundt på siden (Mersenne primes).
Sorry,
Kjartan
Tenkte bare at en link med litt info alltid er bra å ha. Siden sier litt om perfekte tall og deres relasjon til Mersenne tall som det jo var spørsmål om i oppgaven.
Og hvorfor n må være et primtall for at 2[sup]n[/sup]-1 skal være et primtall finner du hvis du klikker litt rundt på siden (Mersenne primes).
Sorry,
Kjartan
