La n være et positivt heltall. Vis at det finnes uendelig mange primtall [tex]p[/tex] slik at den minste primitive roten mod p er større enn n.
(Blir en ubekvem av å snakke om størrelse mod p skal konklusjonen være at det finnes uendelig mange primtall p slik at ingen av tallene [tex]1, 2, 3, \ldots, n[/tex] er en primitiv rot mod p.)
Primitive røtter mod n
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Vi vil finne uendelig mange primtall p slik at 1,2,...,n er kvadratiske rester modulo p (>2), i så fall kan de ikke være primitive røtter. Dvs at vi ønsker at legendre-symbolet [tex]\left( \frac{k}{p} \right) =1[/tex] for alle [tex]k \leq n[/tex]. Siden [tex]\left( \frac{ab}{p} \right) =\left( \frac{a}{p} \right) \left( \frac{b}{p} \right)[/tex], holder det å vise at for primdivisorene [tex]\{q_i\}^r_1[/tex] av tallene 1,2,...n, så er [tex]\left( \frac{q_i}{p} \right) = 1[/tex]. Grunnen til dette er at hvis [tex]k \leq n[/tex], så kan k skrives som [tex]q_1^{s_1}...q_{r}^{s_r}[/tex], så [tex]\left( \frac{q_1^{s_1}...q_{r}^{s_r}}{p} \right)=\left( \frac{q_1}{p} \right)^{s_1}...\left( \frac{q_r}{p} \right)^{s_r}=1[/tex].
Det er kjent at for odde p,q primtall er [tex]\left( \frac{q}{p} \right)=\left( \frac{p}{q} \right)(-1)^{\frac{p-1}{2}}(-1)^{\frac{q-1}{2}}[/tex], og [tex]\left( \frac{2}{p} \right)=(-1)^{\frac{p^2-1}{8}}[/tex]. Vi betrakter nå primdivisorne [tex]q_1,q_2,...,q_{r-1}[/tex] som vi antar er odde (og [tex]q_r=2[/tex], for vi antar r>1 siden r=1 er trivielt). La [tex]a_i[/tex] være en tall som ikke er en kvadratisk rest modulo [tex]q_i[/tex] i<r. Et slikt tall finnes siden det er [tex]\frac{q_i+1}{2}[/tex] kvadratiske rester for odde primtall.
Vi krever at [tex]p \equiv 1 \pmod 8[/tex]. Dersom [tex]q_i \equiv 1 \pmod 4[/tex], krever vi [tex]p \equiv 1 \pmod {q_i}[/tex]. Dersom [tex]q_i \equiv 3 \pmod 4[/tex], krever vi [tex]p \equiv a_i \pmod 4[/tex]. Når vi setter inn i formelen over (1 er alltid en kvadratisk rest, [tex]a_i[/tex] er aldri) ser vi at dersom p tilfredsstiller disse kravene er [tex]q_i[/tex] kvadratiske rester modulo p.
Videre merker vi oss at [tex](-1)^{\frac{p^2-1}{8}}=1[/tex] dersom [tex]p \equiv 1 \pmod 8[/tex].
Siden [tex]8,q_1,q_2,...,q_{r-1}[/tex] er relativt primske, gir det kinesiske restteoremet at det finnes en restklasse r modulo [tex]M=8q_1...q_{r-1}[/tex] som tilfredsstiller kravene til p. Det følger av kravene vi har gitt p at r er relativt primsk med M. Det betyr at vi ønsker oss et uendelig antall primtall større enn 2 slik at [tex]p = r+Mn[/tex] for et heltall n der [tex]\gcd(r,M)=1[/tex]. Det følger av Dirichlets teorem om primtall i aritmetiske følger at vi har et uendelig antall slike.
Dette kan enkelt generaliseres til enhver endelig mengde heltall ved å betrakte mengden primdivisorer ved samme argument.
EDIT: rettet en liten feil: vi trenger generelt p lik 1 modulo 8 for at 2 skal være en kvadratisk rest modulo p.
Det er kjent at for odde p,q primtall er [tex]\left( \frac{q}{p} \right)=\left( \frac{p}{q} \right)(-1)^{\frac{p-1}{2}}(-1)^{\frac{q-1}{2}}[/tex], og [tex]\left( \frac{2}{p} \right)=(-1)^{\frac{p^2-1}{8}}[/tex]. Vi betrakter nå primdivisorne [tex]q_1,q_2,...,q_{r-1}[/tex] som vi antar er odde (og [tex]q_r=2[/tex], for vi antar r>1 siden r=1 er trivielt). La [tex]a_i[/tex] være en tall som ikke er en kvadratisk rest modulo [tex]q_i[/tex] i<r. Et slikt tall finnes siden det er [tex]\frac{q_i+1}{2}[/tex] kvadratiske rester for odde primtall.
Vi krever at [tex]p \equiv 1 \pmod 8[/tex]. Dersom [tex]q_i \equiv 1 \pmod 4[/tex], krever vi [tex]p \equiv 1 \pmod {q_i}[/tex]. Dersom [tex]q_i \equiv 3 \pmod 4[/tex], krever vi [tex]p \equiv a_i \pmod 4[/tex]. Når vi setter inn i formelen over (1 er alltid en kvadratisk rest, [tex]a_i[/tex] er aldri) ser vi at dersom p tilfredsstiller disse kravene er [tex]q_i[/tex] kvadratiske rester modulo p.
Videre merker vi oss at [tex](-1)^{\frac{p^2-1}{8}}=1[/tex] dersom [tex]p \equiv 1 \pmod 8[/tex].
Siden [tex]8,q_1,q_2,...,q_{r-1}[/tex] er relativt primske, gir det kinesiske restteoremet at det finnes en restklasse r modulo [tex]M=8q_1...q_{r-1}[/tex] som tilfredsstiller kravene til p. Det følger av kravene vi har gitt p at r er relativt primsk med M. Det betyr at vi ønsker oss et uendelig antall primtall større enn 2 slik at [tex]p = r+Mn[/tex] for et heltall n der [tex]\gcd(r,M)=1[/tex]. Det følger av Dirichlets teorem om primtall i aritmetiske følger at vi har et uendelig antall slike.
Dette kan enkelt generaliseres til enhver endelig mengde heltall ved å betrakte mengden primdivisorer ved samme argument.
EDIT: rettet en liten feil: vi trenger generelt p lik 1 modulo 8 for at 2 skal være en kvadratisk rest modulo p.