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]
Primtallsoppgave
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- 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.
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.