Her er en oppgave for de som kjenner til grupper.
Hvor mange n'te potensrester finnes det i [tex]\mathbb{Z}_p[/tex], hvor [tex]p[/tex] er et primtall?
Dere kan bruke at [tex](\mathbb{Z}_{p}/ \{ 0 \}, \cdot)[/tex] er en syklisk gruppe.
Eksempel: 0,1,4 er de kvadratiske restene modulo 5, og 0,1,6 er de kubiske restene modulo 7.
n'tepotensrester
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Siden [tex](\mathbb{Z}_p/\{ 0 \} )[/tex] er en syklisk gruppe finnes det en [tex]r[/tex] slik at [tex]\{r, r^2, r^3 \ldots r^{p-1} \}[/tex] er et komplett sett med restklasser (unntatt 0) mod [tex]p[/tex]. Da kan alle tall i [tex](\mathbb{Z}_p/\{ 0 \} )[/tex]skrives på formen [tex]r^k[/tex], og vi ser at [tex]p-1[/tex] er det minste tallet slik at [tex]r^k \equiv 1 \pmod p[/tex] (som, om jeg ikke misbruker terminologien, kan formuleres som at ordenen til [tex]r[/tex] mod [tex]p[/tex] er [tex]p-1[/tex]). Anta så at [tex]B[/tex] er slik at det finnes [tex]x[/tex] slik at [tex]X^n \equiv B \pmod p[/tex], og la [tex]X=r^x[/tex] og [tex]B=r^b[/tex]. Vi har da at [tex]r^{nx} \equiv r^b \pmod B[/tex], som ved å gange med [tex](r^b)^{-1}[/tex] på begge sider (som eksisterer av at [tex]p[/tex] er et primtall) gir at [tex]r^{nx-b} \equiv 1 \pmod p[/tex], som av at ordenen til [tex]r[/tex] er [tex]p-1[/tex] gir at [tex]nx \equiv b \pmod {(p-1)}[/tex].
Denne kongruensen har kun løsninger dersom [tex]G=gcd(p-1,n)|b[/tex]. Da må vi altså ha at [tex]b \equiv 0 \pmod G[/tex], som åpenbart har [tex]\frac {p-1} G[/tex] distinkte løsninger mod p-1, og det finnes da [tex]\frac {p-1} G[/tex] rester mod [tex]p[/tex] [tex]B[/tex] slik at kongruensen [tex]x^n \equiv B \pmod p[/tex] er løsbar. Husker vi på at 0 alltid er en n'tepotensrest modulo [tex]p[/tex] som vi så langt har ignorert betyr dette at antallet n'tepotensrester mod [tex]p[/tex] er lik [tex]\frac {p-1} {\gcd(p-1,n)} + 1[/tex].
Denne kongruensen har kun løsninger dersom [tex]G=gcd(p-1,n)|b[/tex]. Da må vi altså ha at [tex]b \equiv 0 \pmod G[/tex], som åpenbart har [tex]\frac {p-1} G[/tex] distinkte løsninger mod p-1, og det finnes da [tex]\frac {p-1} G[/tex] rester mod [tex]p[/tex] [tex]B[/tex] slik at kongruensen [tex]x^n \equiv B \pmod p[/tex] er løsbar. Husker vi på at 0 alltid er en n'tepotensrest modulo [tex]p[/tex] som vi så langt har ignorert betyr dette at antallet n'tepotensrester mod [tex]p[/tex] er lik [tex]\frac {p-1} {\gcd(p-1,n)} + 1[/tex].