Multiplikatives Inverses < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:57 Mi 20.11.2013 | | Autor: | infaktor |
| Aufgabe | Im Folgenden seien Paare (a, b) mit a, b [mm] \in \IZ_{n} [/mm] gegeben.
Benennen Sie jeweils alle Werte für n für die gilt: [mm] a^{-1} \equiv [/mm] b (mod n).
(9; 13) |
Ich weiß nicht, wie ich auf ein Ergebnis kommen soll und ich weiß nicht mal einen Ansatz.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:57 Mi 20.11.2013 | | Autor: | felixf |
Moin!
> Im Folgenden seien Paare (a, b) mit a, b [mm]\in \IZ_{n}[/mm]
> gegeben.
> Benennen Sie jeweils alle Werte für n für die gilt:
> [mm]a^{-1} \equiv[/mm] b (mod n).
>
> (9; 13)
> Ich weiß nicht, wie ich auf ein Ergebnis kommen soll und
> ich weiß nicht mal einen Ansatz.
Wenn [mm] $a^{-1} \equiv [/mm] b [mm] \pmod{n}$ [/mm] ist, muss $a [mm] \cdot [/mm] b [mm] \equiv [/mm] 1 [mm] \pmod{n}$ [/mm] sein. Jetzt uebersetze das in eine Aussage fuer ganze Zahlen (hat was mit Teilbarkeit zu tun); damit solltest du recht einfach alle Loesungen $n$ finden koennen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:43 Do 21.11.2013 | | Autor: | infaktor |
Also in meinem Beispiel (9;13) gilt es 9*13 [mm] \equiv [/mm] 1 (mod n)
Mir leuchtet es immer noch nicht ein wie ich es dann die n berechne?
|
|
|
| |
|
Hallo infaktor,
> Also in meinem Beispiel (9;13) gilt es 9*13 [mm]\equiv[/mm] 1 (mod n)
> Mir leuchtet es immer noch nicht ein wie ich es dann die n
> berechne?
Finde alle $n>1$, für die die folgende Gleichung für irgendein [mm] k\in\IN [/mm] erfüllt ist:
$9*13=k*n+1$
Das läuft offenbar darauf hinaus, alle echten Teiler von 116 zu finden. Es gibt fünf davon.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:20 Do 21.11.2013 | | Autor: | infaktor |
Gut, langsam verstehe ich. Und wie finde ich die echte Teiler? Bzw. wie ist der echter Teile diffeniert? Gibts eine Formel wie ich nun die n ausrechnen kann. Es würde vielleicht mehr verständlich für mich wenn man es an einem Beispiel vorführt.
|
|
|
| |
|
Hallo,
> Gut, langsam verstehe ich. Und wie finde ich die echte
> Teiler? Bzw. wie ist der echter Teile diffeniert?
Na, die Teiler von 116 kannst du doch von Hand bestimmen ...
Ansonsten mache eine Primfaktorzerlegung und lies die Teiler ab.
Echte Teiler von 116 sind diejenigen Teiler, die [mm]\neq 1[/mm] und [mm]\neq 116[/mm] sind.
> Gibts
> eine Formel wie ich nun die n ausrechnen kann. Es würde
> vielleicht mehr verständlich für mich wenn man es an
> einem Beispiel vorführt.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:44 Do 21.11.2013 | | Autor: | infaktor |
Also zum Beispiel 5*23, also Antwort wäre für meine Aufgabe mod n und n= 5, 23...
Das mag sein dass es für 9 und 13 die primäfaktoren schnell finden kann. Und wie sieht es dann mit (1156;7333) soll ich primitiv nach primäfaktoren suchen, dass ist doch utopisch. Gibt's dafür ein trivialer Verfahren?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:04 Do 21.11.2013 | | Autor: | M.Rex |
> Also zum Beispiel 5*23,
Wieso 5?
Das Paar (9;13) fürht doch dazu, dass du die Teilermenge von [mm] 9\cdot13-1=116 [/mm] bestimmen sollst.
Die Teilermenge von 116 ist [mm] T_{116}=\{1;2;4;29;58;116\}
[/mm]
> also Antwort wäre für meine
> Aufgabe mod n und n= 5, 23...
??
> Das mag sein dass es für 9 und 13 die primäfaktoren
> schnell finden kann.
Nicht die Primfaktoren, die Teilermenge.
> Und wie sieht es dann mit (1156;7333)
Berechne die Teilermenge von [mm] 1156\cdot7333-1=8476947=3^{3}\cdot313961
[/mm]
Was ist denn dann wohl [mm] T_{8476947}
[/mm]
> soll ich primitiv nach primäfaktoren suchen, dass ist doch
> utopisch. Gibt's dafür ein trivialer Verfahren?
Das Zerlegen in Primfaktoren kannst du doch recht schnell machen, das geht mit dem Sieb des Erastothenes recht gut.
Marius
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:25 Do 21.11.2013 | | Autor: | infaktor |
jetzt bin total verwirrt. Es hieß vorhin "Ansonsten mache eine Primfaktorzerlegung und lies die Teiler ab. " T_116 = {1,2,4,29,58,116}
Wie kommst du auf diese Zahlen? Schreib bitte die Lösungsweg und
4,58,116 sind ja keine Primzahlen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:29 Do 21.11.2013 | | Autor: | chrisno |
Bitte informiere Dich über den Unterschied zischen Primfaktoren und Teilern.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:37 Do 21.11.2013 | | Autor: | infaktor |
Deswegen bin hier weil ich den unterschied kenne aber mir ist noch nicht den Rechenweg klar ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:49 Do 21.11.2013 | | Autor: | chrisno |
Du hast geschrieben:
> jetzt bin total verwirrt. Es hieß vorhin "Ansonsten mache eine Primfaktorzerlegung und lies die
> Teiler ab. " T_116 = {1,2,4,29,58,116}
> Wie kommst du auf diese Zahlen? Schreib bitte die Lösungsweg und
> 4,58,116 sind ja keine Primzahlen.
Damit gibst Du doch zu verstehen, das Du der Meinung bist, dass alle Teiler Primzahlen sein müssen. Wenn Du etwas anderes meinst, dann schreib das auch.
prüfe: Teilen 4, 58, 116 die Zahl 116?
also gibt es Teiler, die keine Primzahlen sind?
Führe durch: die Primfaktorzerlegung von 116:
Teilbar durch 2: ja
Teilbar durch 3: nein
Teilbar durch 5: ....
Bei welcher Primzahl darfst Du mit dem Prüfen aufhören?
Schreibe 116 als Produkt seiner Primfaktoren: $116 = [mm] 2^2 \cdot 29^1$.
[/mm]
Nun bestimme alle Teiler:
[mm] $2^0 \cdot 29^0$
[/mm]
[mm] $2^1 \cdot 29^0$
[/mm]
[mm] $2^2 \cdot 29^0$
[/mm]
[mm] $2^0 \cdot 29^1$
[/mm]
[mm] $2^1 \cdot 29^1$
[/mm]
[mm] $2^2 \cdot 29^1$
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:35 Do 21.11.2013 | | Autor: | reverend |
Hallo nochmal,
> ..., alle echten Teiler von
> 116 zu finden. Es gibt fünf davon.
Pardon.
Das hätte heißen müssen: alle Teiler [mm] \not=1 [/mm] von 116.
Die 116 selbst ist natürlich auch eine Lösung des Problems.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:37 Do 21.11.2013 | | Autor: | felixf |
Moin rev,
> > ..., alle echten Teiler von
> > 116 zu finden. Es gibt fünf davon.
>
> Pardon.
> Das hätte heißen müssen: alle Teiler [mm]\not=1[/mm] von 116.
> Die 116 selbst ist natürlich auch eine Lösung des
> Problems.
und ebenso 1, -1, -116, und alle sonstigen ganzen Zahlen, die 116 teilen :)
(Es sei denn, man setzt $n > 0$ voraus. Dann natuerlich nicht die negativen Zahlen.)
LG Felix
|
|
|
|
