Matematik

Et par opgaver om primtal

24. september 2005 af Epsilon (Slettet)

Nedenfor er et par opgaver omhandlende primtal, som gerne skulle være til at angribe for gymnasieelever med et passende niveau i matematik. Men først den relevante definition og et par bemærkninger, som frit må benyttes.

Definition
Et heltal p > 1 kaldes et primtal, hvis div(p) = {1,p}, dvs. hvis p kun har de naturlige divisorer 1 og p.

Ethvert heltal, n >= 1 er et produkt af primtal; en sådan primfaktorisering er endda entydig (op til omordning af faktorerne). Et positivt heltal, der ikke er et primtal, kaldes et sammensat tal.

OPGAVE 1
Et tal på formen M_n = 2^n - 1 kaldes et Mersenne-tal. Specielt hvis 2^n - 1 er et primtal, kaldes tallet et Mersenne-primtal.

a)
Vis, at hvis Mersenne-tallet M_n er et primtal, så er n et primtal.

Vink: antag, at n er sammensat og søg en modstrid.

b)
Er M_n et primtal, hvis n er et primtal?

OPGAVE 2
Det n'te Fermat-tal F_n, n >= 0, er defineret som

F_n = 2^(2^n) + 1

a)
Vis, at F_0, F_1 og F_2 er primtal.

Følgen af Fermat-tal vokser meget hurtigt; allerede fra og med n = 3 bliver det hurtigt surt at undersøge, om F_n er et primtal. Fermat påstod selv i 1650, at ethvert F_n er et primtal. Næsten et århundrede senere, i 1739, påviste Euler som den første, at F_5 ikke er et primtal. Den dag i dag vides det ikke, om der findes et Fermat-tal F_n, n > 4, som er et primtal.

b)
Vis, at F_5 = 2^32 + 1 ikke er et primtal ved at bruge følgende vink:

1) 5^4 + 2^4 = 1 + 5(2^7)
2) F_5 = (5^4 + 2^4)(2^7)^4 + "noget"

Til dem, som bare ikke kan få nok af opgaver, er her en lille tillægsopgave i tilknytning til opgave 1 ovenfor.

Lad a,n > 1 være heltal.

1c)
Vis, at hvis a^n - 1 er et primtal, så er a = 2, og n er et primtal.

Hvis ikke der i tråden indløber forslag til besvarelse af opgaverne, regner jeg med at poste vejledende forslag, når weekenden er ved at være omme, eventuelt en dag eller to senere. Og nu ikke noget med at snyde (kontaktpersoner mv.); det er sjovest selv at løse opgaverne :-)

God fornøjelse!

//Epsilon

Brugbart svar (0)

Svar #1
25. september 2005 af fixer (Slettet)

Såfremt opgaverne udelukkende er tiltænkt gymnasiaster skal jeg undskylde mit indlæg. Men det er da for skægt til at lade ligge, dog nøjes jeg i forsigtighed med opgave 1:

a) Antag M_n er et primtal, altså at div(M_n)={1,M_n}.

Antag dernæst at n ikke er et primtal. Da vil n have divisorer p og q, begge forskellige fra 1 og n, således at

n=pq

Men da

M_n = 2^n-1 <=>
M_n = 2^(pq)-1 <=>
M_n = ((2^p-1)+(2^p-1)2^q+(2^p-1)2^(2q)+...+(2^p-1)2^(p(q-1))) <=>
M_n = (2^p-1)(1+2^q+2^(2q)+...+2^(p(q-1))

ses at M_n har divisorerne (2^p-1) og (1+2^q+2^(2q)+...+2^(p(q-1))) i strid med antagelsen om at div(M_n)={1,M_n}.

Under forudsætning af, at M_n er et primtal, fører antagelsen om at n ikke er et primtal således til en modstrid. Heraf slutter vi at hvis M_n er et primtal, da er n ligeså.

b) Nej. Til eksempel er M_11=2047=89*23.

Svar #2
25. september 2005 af Epsilon (Slettet)

#1:
Korrekt. Opgaverne var nu ganske rigtigt oprindeligt tiltænkt gymnasieelever, så hvis universitetsfolk vil løse opgaverne, bedes de holde sig i baggrunden og vente, til eleverne har haft en chance.

//Epsilon

Svar #3
25. september 2005 af Epsilon (Slettet)

Eftersom OPGAVE 1 nu reelt er løst (dog med undtagelse af 1c)), må jeg hellere indføje en ny opgave;

OPGAVE 3

a)
Vis, at hvis 2^n + 1 er et primtal, så er n en potens af 2 (læs: n = 2^k for et heltalligt k >= 0).

Vink: se på n = rs, 1

Bemærk: ovennævnte (korrekte) påstand er den omvendte til Fermats påstand. Sidstnævnte er jo som bekendt falsk (F_5 er ikke et primtal, jf. opgave 2).

b)
Vis, at Fermat-tallene opfylder

F_n = F_0*F_1*F_2*...*F_(n-1) + 2 (*)

for ethvert n >= 1.

Vink: induktion. Husk, hvorledes F_n er defineret.

Anm:
(*) er et eksempel på en såkaldt rekurrensrelation; det n'te Fermat-tal kan beregnes af de foregående (rekursivt).

//Epsilon

Svar #4
26. september 2005 af Epsilon (Slettet)

Opdatering af tråd i fald, at nogle skulle have mod på at give deres bud på løsning af ét eller flere af opgavespørgsmålene i OPGAVE 2 eller OPGAVE 3 samt 1c). OPGAVE 2 skulle de fleste være i stand til at løse.

//Epsilon

Brugbart svar (0)

Svar #5
26. september 2005 af x^n+y^n=z^n (Slettet)

Jeg har ikke helt lært induktion endnu, (jeg går kun i 1. htx), men jeg prøvede 3b). Jeg går ud fra at:
F_n=F_0*F_1...*F_(n-1)+2 , dermed:
F_(n+1)=F_0*F_1...*F_n , og dermed må
F_(n+1)=(F_n-2)*F_n+2
F_(n+1)=(F_n)^2-2*F_n+2 (*)
Af formlen for Fermat-tal har man:
F_(n+1)=(2^(2^(n+1))+1)^2 ,og
F_n=2^(2^n)+1
og det kan udregnes at (*) passer

Brugbart svar (0)

Svar #6
26. september 2005 af fixer (Slettet)

#5 Man skal være meget omhyggelig med argumentationen når man udfører induktionsbeviser.

En genopfriskning er måske velanbragt:

Induktion er en bevisteknik oftest brugt til at bevise at et givet udsagn P(n) er sandt for all naturlige tal n.

Der findes generaliseringer af teknikken, men den helt simple, der tænkes anvendt her, har to trin.

a) Vis at P(n) er sand for n=0.
b) Vis at hvis P(n) er sand, så er P(n+1) også sand.

Beviset består altså i først at vise at udsagnet er sand for en given begyndelsesværdi (ikke nødvendigvis n=0), og dernæst vise at metoden hvorved man kommer fra een værdi til den følgende er gyldig.

Princippet kan illustreres med et eksempel.

Vi betragter potensrækken

s = sum[i=0->n]{a^i), a E R+

og vi ønsker at bevise at for all n>=0 er

s = (1-a^(n+1))/(1-a)

Hertil danner vi udsagnet

P(n) : s = (1-a^(n+1))/(1-a)

Det ses at P(0) er sand, thi

s=sum[i=0->0]{a^i} = a^0 = 1 = (1-a^(0+1))/(1-a)

Antag nu at P(n) er sand. Så gælder at

sum[i=0->n+1]{a^i}=
sum[i=0->n]+a^(n+1)=
(1-a^(n+1))/(1-a)+a^(n+1) =
(1-a^(n+1)+a^(n+1)-a^((n+1)+1)))/(1-a) =
(1-a^((n+1)+1)))/(1-a)

Men dette er udsagnet for P(n+1). Vi har ikke bevist at det er sandt; vi har vist, at under forudsætning af at P(n) er sand, så er P(n+1) også sand. Vi har altså vist at

P(n) => P(n+1) (*)

Men ifølge induktionsaksiomet kan vi af denne implikation medsamt beviset for at P(0) er sand slutte, at P(n) er sand for alle naturlige tal.

Induktionsaksiomet udtrykker blot følgende logiske kæde:

1) Vi ved at P(0) er sand, derfor er P(1) sand (*)
2) Vi ved at P(1) er sand, derfor er P(2) sand (*)
:
:

Brugbart svar (0)

Svar #7
26. september 2005 af x^n+y^n=z^n (Slettet)

Ja, ja.
F_0=3
F_1=5
og F_1=F_0+2
og dermed er a) bevist

Svar #8
26. september 2005 af Epsilon (Slettet)

#7:
Du mangler nu blot at bevise b) i #6. Lad os med P(n) betegne udsagnet:

P(n): F_n = F_0*F_1*F_2*...*F_(n-1) + 2 (*)

Vi ser, at P(1) gælder, idet

F_1 = 2^(2^1) + 1 = (2^(2^0) + 1) + 2 = F_0 + 2

(hvilket du har indset).

Lad os nu antage, at (*) gælder for et bestemt n; lad os sige n = k. Du skal nu under brug af denne antagelse vise, at

P(k) => P(k+1)

altså, at

F_(k+1) = F_0*F_1*F_2*...*F_(k) + 2 (**)

Prøv, om ikke du kan få vist (**). Opskriv F_(k+1) direkte ud fra definitionen og regn videre derudfra.

//Epsilon

Brugbart svar (0)

Svar #9
27. september 2005 af x^n+y^n=z^n (Slettet)

ok. Jeg går ud fra at:
F_(k)=F_0*F_1*F_2*...*F_(k-1)+2 , og
F_(k+1)=F_0*F_1*F_2*...*F_(k)+2
jeg erstater så F_0*F_1*F_2*...*F_(k-1) med (F_(k)-2):
F_(k+1)=(F_(k)-2)*F_(k)+2
F_(k+1)=(F_k)^2-2*(F_k)+2 (*)
det kan bevises at:
F_(k+1)=2^(2^(k+1))=(2^(2^(k)))^2
og vi ved at:
(F_k)^2=(2^(2^(k))+1)^2
(2^(2^(k))+1)^2=(2^(2^(k))^2+2*(2^(2^(k)))+2
og man kan nu se at (*) er sand

Brugbart svar (0)

Svar #10
27. september 2005 af x^n+y^n=z^n (Slettet)

opg. 1c)
(a^n)-1=(((a-1)+1)^n)-1
dette er lig med:
(k1*(a-1)^n+k2*(a-1)^(n-1)+...+1)-1
hvor k'erne er binomialkoefficienter. Det ses at a-1 går op i dette, og derfor skal a være 2, hvis (a^n)-1 skal være primtal.
Hvis n ikke er et primtal kan det skrives som produkt af to tal:
n=r*s, dermed har man:
((a^r)^s)-1, som (a^r)-1 går op i.
Derfor må a være 2, og n et primtal, hvis (a^n)-1 er et primtal.

Svar #11
27. september 2005 af Epsilon (Slettet)

#9:
Du er på rette vej, men det er ikke korrekt, at

F_(k+1) = (2^(2^k))^2

Du mener vel, at

F_(k+1) = (2^(2^k))^2 + 1

men dette følger umiddelbart af definitionen på det (k+1)'te Fermat-tal. Lad os regne på F_(k+1);

F_(k+1) =
2^(2^(k+1)) + 1 =
(2^(2^k))^2 + 1 =
(F_k - 1)^2 + 1 =
(F_k)(F_k - 2) + 2

Benyt nu induktionsantagelsen. Bemærk, at du faktisk var nået til netop dette skridt i #5.

#10:
Fremgangsmåden med binomialformlen er korrekt. Vi mangler nu blot et afsluttende argument for, at a = 2.

At n er et primtal, følger direkte af OPGAVE 1 a), da vi nu ved, at a = 2.

Man behøver ikke binomialformlen for at vise, at a = 2; men af hensyn til andre, som måske har fundet et meget nært beslægtet argument, venter jeg lidt med at nævne, hvad jeg havde i tankerne.

I øvrigt er der forhåbentlig nogle, som har mod på at byde ind på OPGAVE 2 eller OPGAVE 3 a).

//Epsilon

Brugbart svar (0)

Svar #12
27. september 2005 af allan_sim

#11. Hm... hvad er jeg egentlig? Universitetsmand eller gymnasiemand..... :-)

Brugbart svar (0)

Svar #13
27. september 2005 af Dominik Hasek (Slettet)

#12: Du er altmuligmand. :-)

Svar #14
27. september 2005 af Epsilon (Slettet)

#12:
Du er i hvert fald ikke gymnasieelev (cf. #2) ;-)

Men jeg vil nu erklære ballet åbent for alle, hvad angår de resterende opgaver; det ser alligevel ikke ud til, at andre har haft lyst til at byde ind de foregående dage.

//Epsilon

Brugbart svar (0)

Svar #15
28. september 2005 af DMUS (Slettet)

Til at starte med vil jeg tilføje at det er et flot stykke arbejde du har lavet... Meget spændende, har aldrig været god til beviser, men vil der gerne lære lidt. Så kaster mig ud i det.

Opgave 2 a:

Hvordan viser jeg at Fermat tallet F_0, F_1 og F_2 er primal?

F_n = 2^(2^n) + 1

F_0 = 2+1 = 3

F_1 = 2^2+1 = 5

F_2 = 2^4+1 = 17

Man kan jo ikke bare skrive at: Det ses at kun tallet 1, og tallet selv går op, hvilket slutter det er et primtal?

Opstiller man, et udtryk som godtgør at det ikke er normale tal der kan sammenskrives ved n=p*q, eller hvordan griber jeg det an?

Svar #16
28. september 2005 af Epsilon (Slettet)

#15:
De fleste ville nu nok godtage, at det umiddelbart ses, at 3,5 og 17 er primtal.

Men lad mig da bringe den præcise definition på banen:

Antag, at a = bc, hvor a,b,c E Z (a,b og c er hele tal). Så siger vi, at c går op i a *), og vi skriver dette således: c|a.

Vi skal vise, at div(F_n) = {1,F_n}, n = 0,1,2. Vi har

F_0 = 3 = bc
F_1 = 5 = b'c'
F_2 = 17 = b''c''

hvor 1 =

Men nu er det let; de eneste tal, c blandt 1,2 og 3, som dividerer F_0, er c = 1 og c = 3 = F_0. Så F_0 er et primtal. Tilsvarende går det med 5 og 17. Man tjekker ganske enkelt, at hvert af de tre F_n'er ikke kan skrives som et produkt af to positive heltal, som begge er mindre end F_n. Thi så må F_n jo være et primtal.

I denne anledning vil jeg lige omtale en smuk klassisk metode, som kaldes "Eratosthenes' si", hvormed man i princippet kan generere en liste af (små) primtal. Det er uhyre simpelt: start med at liste de naturlige tal > 1:

2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,...

Slet alle tallene, som er divisible med 2 (på nær 2 selv). Tag det næste tal i rækken, som ikke er slettet (3), slet derpå alle tal, som er divisible med 3 (på nær 3 selv) og så fremdeles. De resterende tal:

2,3,5,7,11,13,17,19,23,...

må da præcis være primtallene. Specielt ser vi, at 3,5 og 17 primtal.

*) Synonymt hermed siger man ofte, at c dividerer a eller, at c er en divisor i a.

//Epsilon

Svar #17
28. september 2005 af Epsilon (Slettet)

#16:
Det gik vist lidt hurtigt. Således;

" (...), hvormed man kan generere en liste over (små) primtal."

og

" Specielt ser vi, at 3,5 og 17 er primtal. "

//Epsilon

Brugbart svar (0)

Svar #18
28. september 2005 af DMUS (Slettet)

Ja, forstår det godt, også det jeg tænkte, med at man skulle kreere et udtryk at der ikke er tale om et primtal, altså et udtryk der kan skrivse som produkt af to reelle tal. :)

Har man nogen ide om hvordan euler viste at F_5 ikke var et primtal, eller er det metoden der knytter sig til opg. 2,b?

Svar #19
28. september 2005 af Epsilon (Slettet)

#18:
Det afgørende er, at F_n, n = 0,1,2 ikke kan skrives som produkt af to positive _heltal_, der begge er mindre end F_n. Definitionen på, at et tal går op i et andet (jf. #16), er knyttet til heltal. Vi skal ikke have rodet de reelle tal ind i den sag :-)

Jeg har ikke umiddelbart kunnet finde svar på, om det var præcis de i 2b) nævnte observationer, som Euler gjorde.

Men prøv ikke desto mindre at udnytte vinkene til at vise, at F_5 ikke er et primtal.

//Epsilon

Brugbart svar (0)

Svar #20
28. september 2005 af DMUS (Slettet)

Ja, okay.. To positive "heltal" mindre end F_n.. Jeg ska passe på hvad jeg siger.. :)

Jeg prøver lige at se på opgave 2b så, men sku ik sikkert jeg når så langt.. :P

Forrige 1 2 Næste

Der er 29 svar til dette spørgsmål. Der vises 20 svar per side. Spørgsmålet kan besvares på den sidste side. Klik her for at gå til den sidste side.