Antall løsninger i Z_p
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Hvor mange løsninger til [tex]ad-bc=1[/tex] fins det modulo p der p er et primtall?
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Det stemmer. Jeg burde kanskje forstått argumentet fra måten du uttrykker svaret på, men trenger nok litt hjelp?
Jeg så først på mulige løsninger i den multiplikative gruppen [tex](Z_p-0,\cdot)[/tex].
[tex]ad=1+bc[/tex]
Høyresiden må være ulik 0 siden p er prim. [tex]b[/tex] kan ha [tex]p-1[/tex] verdier. For hver av disse kan [tex]c[/tex] ha [tex]p-2[/tex] verdier (én mindre fordi det er nøyaktig ett element c for hver b som vil gi [tex]bc=-1[/tex]).
Vi vet at [tex]d[/tex] har en invers i [tex](Z_p-0,\cdot)[/tex], og for alle de [tex](p-1)(p-2)[/tex] kombinasjonene av (b,c) fins det [tex]p-1[/tex] verdier av [tex]d[/tex]. For hver av disse [tex](p-2)(p-1)^2[/tex] verdiene er derfor [tex]a[/tex] bestemt fra [tex]a=(1+bc)d^{-1}[/tex].
Fra ligningen vil i tillegg nøyaktig én og to av variablene kunne være 0.
Hvis én av verdiene er 0 vil vi få et uttrykk på formen
[tex]ad=1[/tex] (eller ekvivalent -bc=1). For hver
[tex]d\in (Z_p-0,\cdot)[/tex] er [tex]a[/tex] gitt som den inverse til [tex]d[/tex] som kan ha [tex]p-1[/tex] verdier. Hvis b er 0 kan c ha [tex]p-1[/tex] verdier. Siden det er 4 tall som kan være 0, vil vi få [tex]4(p-1)^2[/tex] nye mulige kombinasjoner.
Til slutt er det 2 måter to av tallene kan være 0 på (a=d=0 eller b=c=0).
For hver av disse er det [tex]p-1[/tex] mulige kombinasjoner i [tex](Z_p-0,\cdot)[/tex], så vi får [tex]2(p-1)[/tex] nye muligheter.
Sum av de tre tilfellene gir [tex](p-2)(p-1)^2+4(p-1)^2+2(p-1)[/tex]
Litt tungvint å forklare slik kombinatorikk, og det er meget mulig at forklaringen er overtydelig, men antar du forstår:)
[tex]ad=1+bc[/tex]
Høyresiden må være ulik 0 siden p er prim. [tex]b[/tex] kan ha [tex]p-1[/tex] verdier. For hver av disse kan [tex]c[/tex] ha [tex]p-2[/tex] verdier (én mindre fordi det er nøyaktig ett element c for hver b som vil gi [tex]bc=-1[/tex]).
Vi vet at [tex]d[/tex] har en invers i [tex](Z_p-0,\cdot)[/tex], og for alle de [tex](p-1)(p-2)[/tex] kombinasjonene av (b,c) fins det [tex]p-1[/tex] verdier av [tex]d[/tex]. For hver av disse [tex](p-2)(p-1)^2[/tex] verdiene er derfor [tex]a[/tex] bestemt fra [tex]a=(1+bc)d^{-1}[/tex].
Fra ligningen vil i tillegg nøyaktig én og to av variablene kunne være 0.
Hvis én av verdiene er 0 vil vi få et uttrykk på formen
[tex]ad=1[/tex] (eller ekvivalent -bc=1). For hver
[tex]d\in (Z_p-0,\cdot)[/tex] er [tex]a[/tex] gitt som den inverse til [tex]d[/tex] som kan ha [tex]p-1[/tex] verdier. Hvis b er 0 kan c ha [tex]p-1[/tex] verdier. Siden det er 4 tall som kan være 0, vil vi få [tex]4(p-1)^2[/tex] nye mulige kombinasjoner.
Til slutt er det 2 måter to av tallene kan være 0 på (a=d=0 eller b=c=0).
For hver av disse er det [tex]p-1[/tex] mulige kombinasjoner i [tex](Z_p-0,\cdot)[/tex], så vi får [tex]2(p-1)[/tex] nye muligheter.
Sum av de tre tilfellene gir [tex](p-2)(p-1)^2+4(p-1)^2+2(p-1)[/tex]
Litt tungvint å forklare slik kombinatorikk, og det er meget mulig at forklaringen er overtydelig, men antar du forstår:)
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Ser fint ut. Det virker som du er kjent med gruppeteori, og da har du sikkert registrert at du nå har funnet ordenen til [tex]SL(2,\mathbb{Z}_p)[/tex]. Du kan jo prøve å utvide til 3*3-matriser om du vil.
Et litt kortere argument: Vi kan ikke ha a=b=0, så hvis vi først velger a og b fritt har vi p^2-1 valg for disse. Enten a eller b er nå ulik 0, si det er a. For hver av de p mulighetene for c er nå d entydig bestemt, så vi har (p^2-1)*p muligheter totalt.
Et litt kortere argument: Vi kan ikke ha a=b=0, så hvis vi først velger a og b fritt har vi p^2-1 valg for disse. Enten a eller b er nå ulik 0, si det er a. For hver av de p mulighetene for c er nå d entydig bestemt, så vi har (p^2-1)*p muligheter totalt.