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.

Primtallsoppgave

Innlegg Knuta » 04/11-2007 23:30

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]
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Innlegg Bogfjellmo » 05/11-2007 23:28

Lureoppgave, det finnes ikke.
Bogfjellmo offline
Cantor
Cantor
Innlegg: 142
Registrert: 29/10-2007 22:02

Innlegg Ice » 06/11-2007 00:56

Kan du bevise det? :P
(det kan nemlig ikke jeg)
Èg er Islendingur :P
Ice offline
Cayley
Cayley
Innlegg: 79
Registrert: 13/01-2006 23:34
Bosted: Trøndelag

Innlegg Bogfjellmo » 06/11-2007 19:58

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.
Bogfjellmo offline
Cantor
Cantor
Innlegg: 142
Registrert: 29/10-2007 22:02

Hvem er i forumet

Brukere som leser i dette forumet: Google [Bot] og 3 gjester