Primtall på formen 7k + 1

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.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Hege Baggethun2020
Noether
Noether
Innlegg: 37
Registrert: 13/06-2020 23:21

Gitt at [tex]N = \frac{x^{7}-1}{x-1} = x^{6} + x^{5} +..... + x + 1[/tex]
hvor [tex]x = 7p_{1}p_{2}.......p_{n}[/tex] og [tex]p_{1},p_{2},........,p_{n}[/tex] er primtall,
gi et bevis for at det eksisterer uendelig mange primtall på formen [tex]7k + 1[/tex].

Hint til løsning:
Anta at det finnes endelig mange primtall på formen [tex]7k + 1[/tex]. La [tex]p[/tex] være en primtallsdivisor for
[tex]N = \frac{x^{7}-1}{x-1} = x^{6} + x^{5} +..... + x + 1[/tex].

Kan [tex]p[/tex] være en av [tex]p_{1},p_{2},........,p_{n}[/tex]?
Sist redigert av Hege Baggethun2020 den 31/07-2020 15:52, redigert 2 ganger totalt.
[tex]\sum_{y<n\leq x}a(n)f(n) = A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f'(t)dt[/tex]
LAMBRIDA
Ramanujan
Ramanujan
Innlegg: 250
Registrert: 16/11-2011 19:50
Sted: Hjelmeland

Er det første primtallet på formen 7k+1 =29, og det 20-ende primtallet i denne rekken 701?
Hege Baggethun2020
Noether
Noether
Innlegg: 37
Registrert: 13/06-2020 23:21

LAMBRIDA skrev:Er det første primtallet på formen 7k+1 =29, og det 20-ende primtallet i denne rekken 701?
Heisann,

ja, det stemmer!

Hilsen
Hege.
[tex]\sum_{y<n\leq x}a(n)f(n) = A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f'(t)dt[/tex]
Kake med tau
Dirichlet
Dirichlet
Innlegg: 159
Registrert: 05/02-2013 14:12
Sted: Fetsund

Anta at [tex]p_1,p_2,\ldots,p_n[/tex] er en liste over alle primtall på formen [tex]7k+1[/tex], og at [tex]p\mid N[/tex]. Vi har at [tex]p\not\mid x[/tex], så [tex]p[/tex] er ikke på listen. Vi kan anta at [tex]x-1\not\equiv_p 0[/tex], siden vi da ville hatt [tex]N\equiv_p 7\Rightarrow p\mid 7[/tex].

Vi får [tex]x^7\equiv_p 1[/tex], så [tex]7\mid p-1\Rightarrow p=7k+1[/tex].
"If you really want to impress your friends and confound your enemies, you can invoke tensor products… People run in terror from the $\otimes$ symbol." - en professor ved Standford
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Ser riktig ut det. Bør kanskje påpeke at den siste implikasjonen er en konsekvens av Lagranges teorem: ordenen til x må dele ordenen til den multiplikative gruppen modulo p.

Oppfølger: Vis at det fins uendelig mange primtall kongruent med 1 modulo n for alle positive heltall n.
lfe
Pytagoras
Pytagoras
Innlegg: 13
Registrert: 30/11-2023 16:16
Sted: Trondheim

Vi kan bruke syklotomiske polynomer. La [tex]\Phi _{n}(x)[/tex] være det n-te syklotomiske polynomer.
Det n-te syklotomiske polynomet er definert som minimalpolynomet der røttene er de n-te primitive enhetsrøttene.
[tex]\Phi _{n}(x)=\prod_{1\leq k\leq n, gcd(k,n)=1}^{}(x-e^{2i\pi \frac{k}{n}})[/tex]
Det betyr at [tex]x^{n}-1=\prod_{d|n}^{}\Phi _{d}(x)[/tex].
Vi beviser først et lemma:
La m være en ekte divisor av n. [tex]\Phi _{n}(x)[/tex] og [tex]x^{m}-1[/tex] har ingen like røtter modulo p, der p er et primtall.
Bevis:
Anta for motsigelsens skyld at a er en felles rot for [tex]\Phi _{n}(x)[/tex] og [tex]x^{m}-1[/tex].
Det betyr at gcd(a,p)=1.
Videre har vi at [tex]x^{n}-1=\Phi _{n}(x)\prod_{d|n, d<n}^{}\Phi _{d}(x)[/tex].
Siden alle røttene til [tex]x^{m}-1[/tex] også er røtter av[tex]\prod_{d|n, d<n}^{}\Phi _{d}(x)[/tex], er a en dobbelrot av [tex]x^{n}-1[/tex] modulo p.
Det er et kjent resultat at dersom et polynom har en dobbelrot r, så er også r en rot av den deriverte til polynomet.
Det betyr at [tex]na^{n-1}\equiv 0 (mod\:p)[/tex].
Men p deler hverken a eller n, en motsigelse.

Vi kan nå begynne på hovedresultatet: det eksisterer uendelig mange primtall kongruent med 1 modulo n for alle positive heltall n.
Anta for motsigelsens skyld at det eksisterer endelig mange primtall med rest 1 når vi deler på n. La disse primtallene være [tex]p_{1},p_{2},...,p_{N}[/tex]. La[tex]m=\prod_{i=1}^{N}p_{i}[/tex].
Dersom vi velger et stort nok heltall k, er [tex]\Phi _{n}(knm)>1[/tex] fordi syklotomiske polinomer er moniske. Det betyr at det eksisterer et primtall p slik at [tex]p|\Phi _{n}(knm)[/tex].
Siden konstantleddet til alle syklotomiske polynomer, unntatt [tex]\Phi _{1}(x)=x-1[/tex], er lik 1, har vi at [tex]gcd(p,knm)=1[/tex], fordi kmn deler alle andre ledd. Det betyr at p ikke kan være lik [tex]p_{i}[/tex] for noen i.
Vi valgte p slik at [tex]\Phi _{n}(x)\equiv 0(mod\:p)[/tex]. Det betyr at [tex](kmn)^{n}\equiv 1(mod\:p)[/tex].
Fra lemmaet vårt får vi dermed [tex]ord_{p}(kmn)=n\Rightarrow n|p-1\Rightarrow p\equiv 1(mod\:n)[/tex].
Dette motsier antagelsen om at det eksisterer en endelig mengde primtall kongruent med 1 modulo n.
Dermed eksisterer det uendelig med primtall kongruent med 1 modulo n for alle positive heltall n.
lfe
Pytagoras
Pytagoras
Innlegg: 13
Registrert: 30/11-2023 16:16
Sted: Trondheim

Noen kommentarer:
Polynomet i det første innlegget er det syvende syklotomiske polynomet [tex]\Phi _{7}(x)=\frac{x^7-1}{x-1}[/tex].

Beviset mitt utelater en del detaljer. For eksempel at konstantleddet til [tex]\Phi _{i}(x)[/tex] er lik 1 for i større enn 1 og at [tex]ord_{p}(n)|p-1[/tex] for alle primtall p og heltall n hvor [tex]gcd(p,n)=1[/tex]. Disse resultatene er ikke helt trivielle og kan være verdt å se på.

Er det noen andre elementære bevis for at det eksisterer uendelig mange primtall kongruent med 1 modulo n som ikke bruker syklotomiske polynomer?
Svar