Primtallsoppgave

[Knuta]

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

$p=\frac{m^n-1}{m-1}$

[Bogfjellmo]

Lureoppgave, det finnes ikke.

[Ice]

Kan du bevise det?
(det kan nemlig ikke jeg)

[Bogfjellmo]

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.

$\frac{m^{ap}-1}{m-1}=1+m+m^2+...+m^{ap-1}$
$=(1+m+...+m^{p-1})+m^p(1+m+...+m^{p-1})+...+m^{(a-1)p}(1+m+m^{p-1})$
$=(1+m^p+m^{2p}+...+m^{(a-1)p})(1+m+...+m^{p-1})$

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

Ergo er $\frac{m^n-1}{m-1}$ aldri primtall når n ikke er prim.

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

$\frac{m^{ap}-1}{m-1}=\frac{m^{ap}-1}{m^p-1}\cdot \frac{m^p-1}{m-1}$

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