Anzahl Potenzreste < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:09 Mo 18.02.2013 | | Autor: | rollroll |
| Aufgabe | | Bestimme die Anzahl der 15-ten Potenzreste modulo p für p=31 und p=37. |
Hallo,
will nur wissen, ob ich die Formal richtig vesrtanden habe.
Es gibt ja stets ggT(n,p-1) Lösungen.
a) ggT(30,15)=15 Lösungen
b) ggT(15,36)=3 Lösungen.
Stimmt das so?
Könnte mir mal jemand ein Beispiel für einen 15-ten Potenzrest modulo 31 geben (außer 1)?
Danke schonmal!
|
|
| |
|
Hallo rollroll,
> Bestimme die Anzahl der 15-ten Potenzreste modulo p für
> p=31 und p=37.
> Hallo,
>
> will nur wissen, ob ich die Formal richtig vesrtanden
> habe.
>
> Es gibt ja stets ggT(n,p-1) Lösungen.
Oops?
Diese Formel gilt, wenn p prim ist. Dann gibt es für jeden existierenden Potenzrest n (teilerfremd zu p) [mm] \ggT{(n,p-1)} [/mm] Lösungen.
> a) ggT(30,15)=15 Lösungen
> b) ggT(15,36)=3 Lösungen.
>
> Stimmt das so?
Zu a: Es gibt nur die Potenzreste 1 und -1, z.B. [mm] 3^{15}\equiv -1\mod{31}; [/mm] jeder davon gilt für 15 Restklassen.
Und natürlich den Potenzrest 0, den aber nur einmal.
Zu b: Das ist schwieriger. Die Potenzreste 0,8,28 gibt es jeweils sechsmal, die Potenzreste 1,9,17,19,27,35 jeweils dreimal.
> Könnte mir mal jemand ein Beispiel für einen 15-ten
> Potenzrest modulo 31 geben (außer 1)?
Ja, einer steht schon oben. Hier noch zwei: [mm] 11^{15}\equiv -1\mod{31} [/mm] und [mm] 7^{15}\equiv 1\mod{31}
[/mm]
> Danke schonmal!
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:27 Mo 18.02.2013 | | Autor: | rollroll |
Vielen Dank schonmal!
Also nochmal zur Formel: In diesem Fall dürfte man sie doch dann anwenden, weil ja p=31 und p=37 prim sind. Oder?
Und wie kommt man denn auf die ganzen Potenzreste, die du angegeben hast?
|
|
|
| |
|
Hallo nochmal,
> Also nochmal zur Formel: In diesem Fall dürfte man sie
> doch dann anwenden, weil ja p=31 und p=37 prim sind. Oder?
Pardon. Mein Fehler. Ich habe 31 und 36 gelesen...
> Und wie kommt man denn auf die ganzen Potenzreste, die du
> angegeben hast?
Nachrechnen? Zugegeben, mit technischer Hilfe, hier Excel. Es empfiehlt sich, nicht gleich die 15. Potenz auszurechnen, da strecken Rechner zu schnell die Segel. Ich habe erst die 3. Potenz berechnet und die entsprechende Restklasse bestimmt, dann diese in die 5. Potenz erhoben und wieder die Restklasse bestimmt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:46 Mo 18.02.2013 | | Autor: | rollroll |
Gut, also die Potenzreste explizit zu bestimmen von Hand zu Fuß, würde (z.B. in einer Klausur) also eher nicht verlangt werden, oder?
|
|
|
| |
|
Hallo,
> Gut, also die Potenzreste explizit zu bestimmen von Hand zu
> Fuß, würde (z.B. in einer Klausur) also eher nicht
> verlangt werden, oder?
Na, in diesem Fall vielleicht schon. Herauszufinden, dass es [mm] \mod{31} [/mm] als 15.Potenzreste nur 1 und -1 gibt (bei teilerfremden Restklassen), ist ja nicht schwer.
Aufwändiger wäre es, alle x zu bestimmen, für die [mm] x^{15}\equiv 1\mod{31} [/mm] ist. Das würde man wohl eher nicht verlangen.
Grüße
reverend
|
|
|
|
