Page 1 of 1
Generell form - primtall?
Posted: 12/08-2015 23:04
by Drezky
Hei, dersom alle partall og oddetall oppfyller henholdsvis 2n og 2n+1 på generell form, der [tex]\mathbb{N}[/tex] er et naturlig tall.
Finnes det en generell form man kan skrive primtall på? Jeg har vært borti et par funksjoner som til slutt spyr ut primtall, men med noen unnlatelser.
Dersom jeg skulle for eksempel utført et bevis som involverer bruk av primtall, hvordan ville jeg da skrevet primtallet?
takker for svar
Re: Generell form - primtall?
Posted: 12/08-2015 23:16
by Fibonacci92
Det er nok ingen god generell form man kan skrive primtall på.
Husk at alle primtall utenom 2 er oddetall, så da kan vi skrive dem som 2n+1 akkurat som oddetallene, men det betyr ikke at alle tall på formen 2n+1 er primtall, så her må man passe seg.
I tillegg kan alle primtall > 3 skrives som enten 6n+1 eller 6n+5, klarer du å se hvorfor? Igjen betyr ikke dette at alle tall som er på formen 6n+1 eller 6n+5 er primtall.
Re: Generell form - primtall?
Posted: 13/08-2015 00:49
by Drezky
Fibonacci92 wrote:Det er nok ingen god generell form man kan skrive primtall på.
Husk at alle primtall utenom 2 er oddetall, så da kan vi skrive dem som 2n+1 akkurat som oddetallene, men det betyr ikke at alle tall på formen 2n+1 er primtall, så her må man passe seg.
I tillegg kan alle primtall > 3 skrives som enten 6n+1 eller 6n+5, klarer du å se hvorfor? Igjen betyr ikke dette at alle tall som er på formen 6n+1 eller 6n+5 er primtall.
Dersom x er et primtall større en 3 og man deler tallet på 6 får man [tex]x=6*y+r[/tex] der y er et helt tall 0 større eller lik y mindre eller lik 6 - siden det ikke blir primtall. Må ikke da r være enten 1 eller 5, siden den er delbar på 2 med 0, 2 og 4 som r, og den kan ikke være 3 fordi da måtte x være delelig på 3. Således er r enten 1 eller 5.
[tex]x=6*y+1[/tex] / [tex]x=6*y+5[/tex]
der y er et helt tall
[tex]x=6*y+5 \Leftrightarrow x=6*y+6-1\Leftrightarrow x=6(y+1)-1\Leftrightarrow 6(z)-1[/tex]
der z=y+1.
men dette betyr ikke at tall skrevet på formen 6n-1 og 6n+1 er primtall? med unntak av 2 og 3? dette stemmer jo fordi for eksempel hvis y=6, da får man i 6*6-1 = 35
og dette er delelig med 5..
Re: Generell form - primtall?
Posted: 13/08-2015 22:05
by Drezky
Noen som kunne greie ut om dette?

Re: Generell form - primtall?
Posted: 14/08-2015 00:04
by Norm
Er ikke mitt fagfelt dette, men primtallene lar seg tilsynelatende ikke skrive på lukket form. De er tilsynelatende tilfeldige, og det er derfor det brukes kraftige maskiner som står på døgnet rundt for å finne de neste primtallene. Man antar at de er uendelige, noe som faktisk er bevist av Euclid omkring 300 f. Kristus. Summen av inverse primtall skal visstnok divergere ifølge
https://en.wikipedia.org/wiki/Divergenc ... the_primes. Primtall brukes blant annet i RSA-algoritmen, som er en krypteringsalgoritme. Å finne faktoriseringen av et stort, tilfeldig tall i primtall er visstnok en treg affære. Tekstbokmetoden er
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Det er dette som utnyttes i kryptering. Når jeg tok et kurs i tallteori, sa foreleseren at hvis vi fant en rask, generell metode til å finne primtallsfaktoriseringen av et stort, tilfeldig heltall, kunne vi forvente oss at menn kledd i mørke frakker ville komme for å ta oss med bort. Ellers vet jeg ikke mer om saken

Re: Generell form - primtall?
Posted: 15/08-2015 00:00
by Drezky
Fibonacci92 wrote:Det er nok ingen god generell form man kan skrive primtall på.
Husk at alle primtall utenom 2 er oddetall, så da kan vi skrive dem som 2n+1 akkurat som oddetallene, men det betyr ikke at alle tall på formen 2n+1 er primtall, så her må man passe seg.
I tillegg kan alle primtall > 3 skrives som enten 6n+1 eller 6n+5, klarer du å se hvorfor? Igjen betyr ikke dette at alle tall som er på formen 6n+1 eller 6n+5 er primtall.
Dersom x er et primtall større en 3 og man deler tallet på 6 får man x=6∗y+r der y er et helt tall 0 større eller lik y mindre eller lik 6 - siden det ikke blir primtall. Må ikke da r være enten 1 eller 5, siden den er delbar på 2 med 0, 2 og 4 som r, og den kan ikke være 3 fordi da måtte x være delelig på 3. Således er r enten 1 eller 5.
x=6∗y+1 / x=6∗y+5
der y er et helt tall
x=6∗y+5⇔x=6∗y+6−1⇔x=6(y+1)−1⇔6(z)−1
der z=y+1.
men dette betyr ikke at tall skrevet på formen 6n-1 og 6n+1 er primtall? med unntak av 2 og 3? dette stemmer jo fordi for eksempel hvis y=6, da får man i 6*6-1 = 35
og dette er delelig med 5..
Men jeg skjønner ikke helt hvorfor du velger å dividere med 6 i første omgang fibonacci92?

Re: Generell form - primtall?
Posted: 15/08-2015 00:08
by Fibonacci92
Altså, dette er ikke noe man bruker noe særlig ofte, men jeg tenkte jeg kunne gi deg eksempel siden du først foreslo en slik form. Jeg kan også nevne formene 3t+1 eller 3t +2 for primtall større enn 3, eller formene 4t+1 og 4t+3 for primtall større enn 2.
Du kan også tenke over om det finnes uendelig mange primtall på formen 4t+1? Finnes det uendelig mange på formen 4t+3?
Se f.eks. Dirichlet's theorem on arithmetic progressions eller Green-Tao Theorem.