Primtallsoppgave

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Knuta
Galois
Galois
Innlegg: 568
Registrert: 31/05-2006 14:59
Sted: Oslo
Kontakt:

Bruk formelen og finn det laveste primtall der n og m ikke er er et primtall.

[tex] p=\frac{m^n-1}{m-1}[/tex]
Bogfjellmo
Cantor
Cantor
Innlegg: 142
Registrert: 29/10-2007 22:02

Lureoppgave, det finnes ikke.
Ice
Cayley
Cayley
Innlegg: 79
Registrert: 13/01-2006 23:34
Sted: Trøndelag

Kan du bevise det? :P
(det kan nemlig ikke jeg)
Èg er Islendingur :P
Bogfjellmo
Cantor
Cantor
Innlegg: 142
Registrert: 29/10-2007 22:02

Er ikke så vanskelig, kan vel også gjøre utsagnet noe sterkere, da det er uinteressant hvorvidt m er primtall.

Anta n ikke primtall, da har det en primtallsfaktor p, og kan skrives n=ap for a>1.

Ser nå på formelen, og gjenkjenner den som summen av en geometrisk rekke.

[tex]\frac{m^{ap}-1}{m-1}= 1 + m + m^2 + ... + m^{ap-1}[/tex]
[tex] = (1 + m + ... + m^{p-1}) + m^p (1 + m + ... + m^{p-1}) + ... + m^{(a-1)p}(1 + m + m^{p-1})[/tex]
[tex] = (1 + m^p + m^{2p} + ... + m^{(a-1)p})(1 + m + ... + m^{p-1})[/tex]

og vi har funnet to faktorer. (Som begge er ulik 1).

Ergo er [tex]\frac{m^n-1}{m-1}[/tex] aldri primtall når n ikke er prim.

Kan også gjøres raskere, men det ser noe umotivert ut:

[tex]\frac{m^{ap}-1}{m-1} = \frac{m^{ap}-1}{m^p-1} \cdot \frac{m^p-1}{m-1}[/tex]

Disse er heltall, da de er summer av geometriske rekker.
Svar