mod < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:24 Di 26.11.2013 | | Autor: | kRAITOS |
| Aufgabe | b) Bestimmen Sie für p [mm] \in [/mm] {23,53,89} die ganze Zahl x [mm] \in [/mm] {0, ..., p−1}, für die
13 · x ≡ 1 mod p
gilt.
c) Bestimmen Sie jeweils die ganze Zahl x [mm] \in \IZ [/mm] mit den geforderten Eigenschaften:
• [mm] 5^3 [/mm] ≡ x mod3, 0 ≤ x ≤ 2,
• [mm] 4^5 [/mm] ≡ x mod5, 0 ≤ x ≤ 4,
• [mm] 11^7 [/mm] ≡ x mod7, 0 ≤ x ≤ 6,
• 9^11 ≡ x mod11, 0 ≤ x ≤ 10,
• 2^12 ≡ x mod13, 0 ≤ x ≤ 12. |
Hallo.
Kann mir jemand sagen, was ich hier machen muss? Habe gerade das Internet durchsucht aber ich finde irgendwie nichts passendes, was mir hier weiterhilft.
Danke schonmal.
|
|
| |
|
Hallo,
> b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x [mm]\in[/mm]
> {0, ..., p−1}, für die
> 13 · x ≡ 1 mod p
> gilt.
>
>
> c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit den
> geforderten Eigenschaften:
>
> • 53 ≡ x mod3, 0 ≤ x ≤ 2,
> • 45 ≡ x mod5, 0 ≤ x ≤ 4,
> • 117 ≡ x mod7, 0 ≤ x ≤ 6,
> • 911 ≡ x mod11, 0 ≤ x ≤ 10,
> • 212 ≡ x mod13, 0 ≤ x ≤ 12.
> Hallo.
>
> Kann mir jemand sagen, was ich hier machen muss? Habe
> gerade das Internet durchsucht aber ich finde irgendwie
> nichts passendes, was mir hier weiterhilft.
Vllt findest du was in deiner Vorlesungsmitschrift?
Wieso bekommt ihr immer Aufgaben, von denen du noch nie vorher was gesehen hast? Hat eure Uni ein ganz besonderes Lernkonzept?
In a) gilt es jeweils die multiplikativ Inversen von 13 zu bestimmen mod 23, mod 53 und mod 89.
Schaue dir in diesem Zusammenhang mal den Euklidischen Algorithmus an ...
Hast du gesehen, dass alle Moduln prim sind?
Bei c)
Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
Wenn dir das nicht klar ist, kannst du die Aufgaben nicht lösen ...
Also mache dich in deiner VL-Mitschrift schlau. Ohne Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix ...
>
>
> Danke schonmal.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:16 Di 26.11.2013 | | Autor: | kRAITOS |
> Hallo,
>
> > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> [mm]\in[/mm]
> > {0, ..., p−1}, für die
> > 13 · x ≡ 1 mod p
> > gilt.
> >
> >
> > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit
> den
> > geforderten Eigenschaften:
> >
> > • 53 ≡ x mod3, 0 ≤ x ≤ 2,
> > • 45 ≡ x mod5, 0 ≤ x ≤ 4,
> > • 117 ≡ x mod7, 0 ≤ x ≤ 6,
> > • 911 ≡ x mod11, 0 ≤ x ≤ 10,
> > • 212 ≡ x mod13, 0 ≤ x ≤ 12.
> > Hallo.
> >
> > Kann mir jemand sagen, was ich hier machen muss? Habe
> > gerade das Internet durchsucht aber ich finde irgendwie
> > nichts passendes, was mir hier weiterhilft.
>
> Vllt findest du was in deiner Vorlesungsmitschrift?
>
> Wieso bekommt ihr immer Aufgaben, von denen du noch nie
> vorher was gesehen hast? Hat eure Uni ein ganz besonderes
> Lernkonzept?
>
> In a) gilt es jeweils die multiplikativ Inversen von 13 zu
> bestimmen mod 23, mod 53 und mod 89.
>
> Schaue dir in diesem Zusammenhang mal den Euklidischen
> Algorithmus an ...
Danke für die Information.
> Hast du gesehen, dass alle Moduln prim sind?
>
> Bei c)
>
> Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
>
> Wenn dir das nicht klar ist, kannst du die Aufgaben nicht
> lösen ...
>
> Also mache dich in deiner VL-Mitschrift schlau. Ohne
> Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix
> ...
>
>
> >
> >
> > Danke schonmal.
>
> Gruß
>
> schachuzipus
In meinen Skripten steht leider nichts zu diesem Thema..
Aber ich habe ein paar schöne Definitionen gefunden.
2 Zahlen a,b [mm] \in \IZ [/mm] heißen kongruent modulo m wenn gilt:
a [mm] \equiv [/mm] b mod m.
Das heißt, beide Zahlen lassen durch teilen von m denselben Rest.
Desweiteren ist a [mm] \equiv [/mm] b mod m [mm] \gdw [/mm] (a-b) = 0
Also muss ich quasi ein x suchen aus dem gegebenen Definitionsbereich.
[mm] 5^3 [/mm] ≡ x mod3, 0 ≤ x ≤ 2
[mm] \gdw 5^3 [/mm] - x = 0 mod 3
[mm] \gdw [/mm] 125-x mod 3 = 0
und mit x=2 wäre
125-2 mod 3 = 0 [mm] \gdw [/mm] 123 mod 3 = 0
Also ist das gesuchte x =2.
Jetzt habe ich aber noch eine Verständnisfrage:
9^11 ≡ x mod11, 0 ≤ x ≤ 10
9^11 = 31381059609
Gibt es hier irgendeinen Kniff, diese Aufgabe zu vereinfachen?
|
|
|
| |
|
Hallo nochmal,
> > Hallo,
> >
> > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> > [mm]\in[/mm]
> > > {0, ..., p−1}, für die
> > > 13 · x ≡ 1 mod p
> > > gilt.
> > >
> > >
> > > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit
> > den
> > > geforderten Eigenschaften:
> > >
> > > • 53 ≡ x mod3, 0 ≤ x ≤ 2,
> > > • 45 ≡ x mod5, 0 ≤ x ≤ 4,
> > > • 117 ≡ x mod7, 0 ≤ x ≤ 6,
> > > • 911 ≡ x mod11, 0 ≤ x ≤ 10,
> > > • 212 ≡ x mod13, 0 ≤ x ≤ 12.
> > > Hallo.
> > >
> > > Kann mir jemand sagen, was ich hier machen muss?
> Habe
> > > gerade das Internet durchsucht aber ich finde
> irgendwie
> > > nichts passendes, was mir hier weiterhilft.
> >
> > Vllt findest du was in deiner Vorlesungsmitschrift?
> >
> > Wieso bekommt ihr immer Aufgaben, von denen du noch nie
> > vorher was gesehen hast? Hat eure Uni ein ganz besonderes
> > Lernkonzept?
> >
> > In a) gilt es jeweils die multiplikativ Inversen von 13 zu
> > bestimmen mod 23, mod 53 und mod 89.
> >
> > Schaue dir in diesem Zusammenhang mal den Euklidischen
> > Algorithmus an ...
>
>
> Danke für die Information.
>
>
> > Hast du gesehen, dass alle Moduln prim sind?
> >
> > Bei c)
> >
> > Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
> >
>
> > Wenn dir das nicht klar ist, kannst du die Aufgaben nicht
> > lösen ...
> >
> > Also mache dich in deiner VL-Mitschrift schlau. Ohne
> > Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix
> > ...
> >
> >
> > >
> > >
> > > Danke schonmal.
> >
> > Gruß
> >
> > schachuzipus
>
>
> In meinen Skripten steht leider nichts zu diesem Thema..
>
> Aber ich habe ein paar schöne Definitionen gefunden.
>
> 2 Zahlen a,b [mm]\in \IZ[/mm] heißen kongruent modulo m wenn gilt:
>
> a [mm]\equiv[/mm] b mod m.
Das ist nur eine Schrweibweise ...
>
> Das heißt, beide Zahlen lassen durch teilen von m
> denselben Rest.
![[ok]](/images/smileys/ok.gif "[ok]") Aha!
>
> Desweiteren ist a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] (a-b) = 0
>
>
> Also muss ich quasi ein x suchen aus dem gegebenen
> Definitionsbereich.
>
>
> [mm]5^3[/mm] ≡ x mod3, 0 ≤ x ≤ 2
>
> [mm]\gdw 5^3[/mm] - x = 0 mod 3
> [mm]\gdw[/mm] 125-x mod 3 = 0
>
> und mit x=2 wäre
>
> 125-2 mod 3 = 0 [mm]\gdw[/mm] 123 mod 3 = 0
>
> Also ist das gesuchte x =2.
Jo, hier kannst du das per Hand ausrechnen.
>
> Jetzt habe ich aber noch eine Verständnisfrage:
>
>
> 9^11 ≡ x mod11, 0 ≤ x ≤ 10
>
> 9^11 = 31381059609
>
> Gibt es hier irgendeinen Kniff, diese Aufgabe zu
> vereinfachen?
Na klar, es gibt ja Reihenweise Rechenregeln für die Kongruenzrechnung ...
Kennst du die Eulersche Phi-Funktion? Weißt du, was [mm] $\varphi(11)$ [/mm] ist?
Hier auch ein Stichwort: Satz von Fermat/Euler ("kleiner Fermat")
Dann ist es ganz einfach mit [mm] $9^{11}=9^{10}\cdot{}9$ [/mm] und den "basic" Rechenregeln für Kongruenzen...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:38 Di 26.11.2013 | | Autor: | kRAITOS |
> Hallo nochmal,
>
>
> > > Hallo,
> > >
> > > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze
> Zahl x
> > > [mm]\in[/mm]
> > > > {0, ..., p−1}, für die
> > > > 13 · x ≡ 1 mod p
> > > > gilt.
> > > >
> > > >
> > > > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm]
> mit
> > > den
> > > > geforderten Eigenschaften:
> > > >
> > > > • 53 ≡ x mod3, 0 ≤ x ≤ 2,
> > > > • 45 ≡ x mod5, 0 ≤ x ≤ 4,
> > > > • 117 ≡ x mod7, 0 ≤ x ≤ 6,
> > > > • 911 ≡ x mod11, 0 ≤ x ≤ 10,
> > > > • 212 ≡ x mod13, 0 ≤ x ≤ 12.
> > > > Hallo.
> > > >
> > > > Kann mir jemand sagen, was ich hier machen muss?
> > Habe
> > > > gerade das Internet durchsucht aber ich finde
> > irgendwie
> > > > nichts passendes, was mir hier weiterhilft.
> > >
> > > Vllt findest du was in deiner Vorlesungsmitschrift?
> > >
> > > Wieso bekommt ihr immer Aufgaben, von denen du noch
> nie
> > > vorher was gesehen hast? Hat eure Uni ein ganz
> besonderes
> > > Lernkonzept?
> > >
> > > In a) gilt es jeweils die multiplikativ Inversen von
> 13 zu
> > > bestimmen mod 23, mod 53 und mod 89.
> > >
> > > Schaue dir in diesem Zusammenhang mal den
> Euklidischen
> > > Algorithmus an ...
> >
> >
> > Danke für die Information.
> >
> >
> > > Hast du gesehen, dass alle Moduln prim sind?
> > >
> > > Bei c)
> > >
> > > Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
>
> > >
> >
> > > Wenn dir das nicht klar ist, kannst du die Aufgaben
> nicht
> > > lösen ...
> > >
> > > Also mache dich in deiner VL-Mitschrift schlau. Ohne
> > > Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst
> nix
> > > ...
> > >
> > >
> > > >
> > > >
> > > > Danke schonmal.
> > >
> > > Gruß
> > >
> > > schachuzipus
> >
> >
> > In meinen Skripten steht leider nichts zu diesem
> Thema..
> >
> > Aber ich habe ein paar schöne Definitionen gefunden.
> >
> > 2 Zahlen a,b [mm]\in \IZ[/mm] heißen kongruent modulo m wenn
> gilt:
> >
> > a [mm]\equiv[/mm] b mod m.
>
> Das ist nur eine Schrweibweise ...
>
> >
> > Das heißt, beide Zahlen lassen durch teilen von m
> > denselben Rest.
>
> Aha!
>
> >
> > Desweiteren ist a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] (a-b) = 0
> >
> >
> > Also muss ich quasi ein x suchen aus dem gegebenen
> > Definitionsbereich.
> >
> >
> > [mm]5^3[/mm] ≡ x mod3, 0 ≤ x ≤ 2
> >
> > [mm]\gdw 5^3[/mm] - x = 0 mod 3
> > [mm]\gdw[/mm] 125-x mod 3 = 0
> >
> > und mit x=2 wäre
> >
> > 125-2 mod 3 = 0 [mm]\gdw[/mm] 123 mod 3 = 0
> >
> > Also ist das gesuchte x =2.
>
> Jo, hier kannst du das per Hand ausrechnen.
>
> >
> > Jetzt habe ich aber noch eine Verständnisfrage:
> >
> >
> > 9^11 ≡ x mod11, 0 ≤ x ≤ 10
> >
> > 9^11 = 31381059609
> >
> > Gibt es hier irgendeinen Kniff, diese Aufgabe zu
> > vereinfachen?
>
> Na klar, es gibt ja Reihenweise Rechenregeln für die
> Kongruenzrechnung ...
>
> Kennst du die Eulersche Phi-Funktion? Weißt du, was
> [mm]\varphi(11)[/mm] ist?
Noch nicht aber das kann man ja schnell nachholen. Auf jeden Fall habe ich nun ruckzuck auch die anderen Aufgaben gelöst. Danke dir.
>
> Hier auch ein Stichwort: Satz von Fermat/Euler ("kleiner
> Fermat")
>
> Dann ist es ganz einfach mit [mm]9^{11}=9^{10}\cdot{}9[/mm] und den
> "basic" Rechenregeln für Kongruenzen...
>
> Gruß
>
> schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:10 Do 28.11.2013 | | Autor: | kRAITOS |
> > Jetzt habe ich aber noch eine Verständnisfrage:
> >
> >
> > 9^11 ≡ x mod11, 0 ≤ x ≤ 10
> >
> > 9^11 = 31381059609
> >
> > Gibt es hier irgendeinen Kniff, diese Aufgabe zu
> > vereinfachen?
>
> Na klar, es gibt ja Reihenweise Rechenregeln für die
> Kongruenzrechnung ...
>
> Kennst du die Eulersche Phi-Funktion? Weißt du, was
> [mm]\varphi(11)[/mm] ist?
>
> Hier auch ein Stichwort: Satz von Fermat/Euler ("kleiner
> Fermat")
>
> Dann ist es ganz einfach mit [mm]9^{11}=9^{10}\cdot{}9[/mm] und den
> "basic" Rechenregeln für Kongruenzen...
>
> Gruß
>
> schachuzipus
Also verstanden habe ich das ganze... Nur hat 9^11 [mm] \equiv [/mm] x mod 11 2 Lösungen...
Ich habe das wie folgt gemacht: (Natürlich vorher geraten.  )
[mm] 9^1^1 \equiv 9^1^0 [/mm] * 9 [mm] \equiv (-2)^1^0 [/mm] * (-2) [mm] \equiv (4)^5 [/mm] * (-2) [mm] \equiv 4^4 [/mm] * (-8) [mm] \equiv 16^2 [/mm] * 3 [mm] \equiv 5^2 [/mm] * 3 [mm] \equiv [/mm] 25 * 3 [mm] \equiv [/mm] 3*3 [mm] \equiv [/mm] 9 mod 11
Durch vorheriges Raten aber kam auch 1 als Lösung. Meine Frage daher: Wie würde ich jetzt sehen, dass eine Kongruenz mehrere Lösungen hat bzw wie würde ich hier auf gerade eben 1 als Lösung kommen?
|
|
|
| |
|
> Also verstanden habe ich das ganze... Nur hat 9^11 [mm]\equiv[/mm] x
> mod 11 2 Lösungen...
Hallo,
es kann keine zwei verschiedenen Lösungen zwischen 0 und 10 geben. Das würde ja bedeuten, daß man bei Division durch 11 zwei verschiedene Ergebnisse bekommt.
>
> Ich habe das wie folgt gemacht: (Natürlich vorher geraten.
> )
>
>
> [mm]9^1^1 \equiv 9^1^0[/mm] * 9 [mm]\equiv (-2)^1^0[/mm] * (-2) [mm]\equiv (4)^5[/mm]
> * (-2) [mm]\equiv 4^4[/mm] * (-8) [mm]\equiv 16^2[/mm] * 3 [mm]\equiv 5^2[/mm] * 3
> [mm]\equiv[/mm] 25 * 3 [mm]\equiv[/mm] 3*3 [mm]\equiv[/mm] 9 mod 11
Das sieht richtig aus.
>
> Durch vorheriges Raten aber kam auch 1 als Lösung.
Ich frage mich, wie man bei diesen Aufgaben Ergebnisse erraten kann.
Wie dem auch sei: 1 ist falsch.
Meine
> Frage daher: Wie würde ich jetzt sehen, dass eine
> Kongruenz mehrere Lösungen hat bzw wie würde ich hier auf
> gerade eben 1 als Lösung kommen?
Auf die 1kommt man gar nicht, und Kongruenzen der Gestalt
a=x mod b haben genau eine Lösung [mm] 0\le x\le [/mm] b-1.
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:00 Fr 29.11.2013 | | Autor: | kRAITOS |
Hallo.
Na wir wissen ja, dass a [mm] \equiv [/mm] b mod m [mm] \gdw [/mm] a-b mod m = 0
Würde man jetzt einsetzen, dann ist [mm] 9^1^1 [/mm] - 1 mod [mm] 11\equiv [/mm] 0 mod 11. Damit wäre diese Bedingung erfüllt.
Aber okay, mir reicht schon die Aussage, dass diese Aufgaben nur eine Lösung besitzen. 
Danke.
|
|
|
| |
|
> Hallo.
>
> Na wir wissen ja, dass a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] a-b mod m = 0
Hallo,
wenn a und b denselben Rest modulo m lassen, ist ihre Differenz ein Vielfaches von m, läßt also bei Division durch m den Rest 0.
>
> Würde man jetzt einsetzen, dann ist [mm]9^1^1[/mm] - 1 mod [mm]11\equiv[/mm]
> 0 mod 11. Damit wäre diese Bedingung erfüllt.
???
Du setzt dabei aber voraus, daß 9^11 bei Division durch 11 den Rest 1 läßt.
Das ist aber nicht der Fall!
Es bleibt der Rest 9.
Wie kommst Du bloß auf 1? Hmm - hast Du vielleicht den kl. Satz von Fermat falsch im Kopf?
Der kl. Fermat sagt:
wenn p eine Primzahl ist, ist [mm] a^{p-1}\equiv [/mm] 1 mod p ,
oder anders ausgedrückt
[mm] a^p\equiv [/mm] a mod p.
LG Angela
>
> Aber okay, mir reicht schon die Aussage, dass diese
> Aufgaben nur eine Lösung besitzen.
>
> Danke.
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:02 Fr 29.11.2013 | | Autor: | kRAITOS |
> > Hallo.
> >
> > Na wir wissen ja, dass a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] a-b mod m =
> 0
>
> Hallo,
>
> wenn a und b denselben Rest modulo m lassen, ist ihre
> Differenz ein Vielfaches von m, läßt also bei Division
> durch m den Rest 0.
>
> >
> > Würde man jetzt einsetzen, dann ist [mm]9^1^1[/mm] - 1 mod
> [mm]11\equiv[/mm]
> > 0 mod 11. Damit wäre diese Bedingung erfüllt.
>
> ???
> Du setzt dabei aber voraus, daß 9^11 bei Division durch
> 11 den Rest 1 läßt.
> Das ist aber nicht der Fall!
> Es bleibt der Rest 9.
>
> Wie kommst Du bloß auf 1? Hmm - hast Du vielleicht den kl.
> Satz von Fermat falsch im Kopf?
>
Ich hatte ihn gar nicht im Kopf. Aber hab ihn mir gerad angeshaut und nun schäme ich mich ja fast für meinen langen Rechnungsweg.
Das geht ja auch viel Kürzer:
[mm] 9^1^1 \equiv 9^1^0 [/mm] * 9 [mm] \equiv [/mm] 1*9 [mm] \equiv [/mm] 9 mod 11
Danke für diese Einsicht. :D
> Der kl. Fermat sagt:
> wenn p eine Primzahl ist, ist [mm]a^{p-1}\equiv[/mm] 1 mod p ,
> oder anders ausgedrückt
> [mm]a^p\equiv[/mm] a mod p.
>
> LG Angela
>
>
> >
> > Aber okay, mir reicht schon die Aussage, dass diese
> > Aufgaben nur eine Lösung besitzen.
> >
> > Danke.
> >
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:47 Do 28.11.2013 | | Autor: | kRAITOS |
> Hallo,
>
> > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> [mm]\in[/mm]
> > {0, ..., p−1}, für die
> > 13 · x ≡ 1 mod p
> > gilt.
> >
> >
> > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit
> den
> > geforderten Eigenschaften:
> >
> > • 53 ≡ x mod3, 0 ≤ x ≤ 2,
> > • 45 ≡ x mod5, 0 ≤ x ≤ 4,
> > • 117 ≡ x mod7, 0 ≤ x ≤ 6,
> > • 911 ≡ x mod11, 0 ≤ x ≤ 10,
> > • 212 ≡ x mod13, 0 ≤ x ≤ 12.
> > Hallo.
> >
> > Kann mir jemand sagen, was ich hier machen muss? Habe
> > gerade das Internet durchsucht aber ich finde irgendwie
> > nichts passendes, was mir hier weiterhilft.
>
> Vllt findest du was in deiner Vorlesungsmitschrift?
>
> Wieso bekommt ihr immer Aufgaben, von denen du noch nie
> vorher was gesehen hast? Hat eure Uni ein ganz besonderes
> Lernkonzept?
>
> In a) gilt es jeweils die multiplikativ Inversen von 13 zu
> bestimmen mod 23, mod 53 und mod 89.
>
> Schaue dir in diesem Zusammenhang mal den Euklidischen
> Algorithmus an ...
Hallo. Ich nochmal.
Ich verstehe nicht ganz den Zusammenhang vom euklidischen Algorithmus und Aufgabenteil b.
Vllt mag jemand kurz Licht reinbringen?
>
> Hast du gesehen, dass alle Moduln prim sind?
>
> Bei c)
>
> Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
>
> Wenn dir das nicht klar ist, kannst du die Aufgaben nicht
> lösen ...
>
> Also mache dich in deiner VL-Mitschrift schlau. Ohne
> Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix
> ...
>
>
> >
> >
> > Danke schonmal.
>
> Gruß
>
> schachuzipus
|
|
|
| |
|
Hallo nochmal,
kannst du bitte mal vernünftig zitieren ...
![[motz]](/images/smileys/motz.gif "[motz]")
> > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> > [mm]\in[/mm]
> > > {0, ..., p−1}, für die
> > > 13 · x ≡ 1 mod p
> > > gilt.
> Hallo. Ich nochmal.
>
> Ich verstehe nicht ganz den Zusammenhang vom euklidischen
> Algorithmus und Aufgabenteil b.
>
> Vllt mag jemand kurz Licht reinbringen?
>
zu p=23:
Berechne [mm]\ggT(13,23)=1[/mm] mit dem Euklidischen Algorithmus.
Dann von unten nach oben rückwärts rechnen und 1, also den [mm]\ggT(13,23)[/mm] als Linearkombination von 13 und 23 darstellen.
Also so:
[mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun erstmal ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:43 Do 28.11.2013 | | Autor: | kRAITOS |
> Hallo nochmal,
>
> kannst du bitte mal vernünftig zitieren ...
>
>
>
>
> > > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> > > [mm]\in[/mm]
> > > > {0, ..., p−1}, für die
> > > > 13 · x ≡ 1 mod p
> > > > gilt.
>
> > Hallo. Ich nochmal.
> >
> > Ich verstehe nicht ganz den Zusammenhang vom
> euklidischen
> > Algorithmus und Aufgabenteil b.
> >
> > Vllt mag jemand kurz Licht reinbringen?
> >
>
> zu p=23:
>
> Berechne [mm]\ggT(13,23)=1[/mm] mit dem Euklidischen Algorithmus.
>
> Dann von unten nach oben rückwärts rechnen und 1, also
> den [mm]\ggT(13,23)[/mm] als Linearkombination von 13 und 23
> darstellen.
>
> Also so:
>
> [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun
> erstmal ...
>
Da kam ich auf a=-7 und b = 4.
Muss ich jetzt das a nehmen, um die Kongruenz für
13 · x ≡ 1 mod 23
zu zeigen? Das würde ja nicht gehen, da das x laut Aufgabe ja [mm] \in \{0, ..., p-1\} [/mm] sein soll.
> Gruß
>
> schachuzipus
|
|
|
| |
|
> > Also so:
> >
> > [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun
> > erstmal ...
> >
>
> Da kam ich auf a=-7 und b = 4.
>
> Muss ich jetzt das a nehmen, um die Kongruenz für
>
> 13 · x ≡ 1 mod 23
>
> zu zeigen?
Hallo,
dann wäre die Aufgabe ohne die Einschränkung [mm] x\in \{0,1,...,22\} [/mm] auf jeden Fall richtig gelöst.
> Das würde ja nicht gehen, da das x laut Aufgabe
> ja [mm]\in \{0, ..., p-1\}[/mm] sein soll.
Ja, das stimmt.
Es ist [mm] -7\equiv [/mm] 16 mod 23,
und mit x=16 ist die gesuchte Lösung gefunden.
(Überzeuge Dich davon, daß es eine Lösung ist.)
LG Angela
>
>
> > Gruß
> >
> > schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:20 Fr 29.11.2013 | | Autor: | kRAITOS |
>
> > > Also so:
> > >
> > > [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun
> > > erstmal ...
> > >
> >
> > Da kam ich auf a=-7 und b = 4.
> >
> > Muss ich jetzt das a nehmen, um die Kongruenz für
> >
> > 13 · x ≡ 1 mod 23
> >
> > zu zeigen?
>
> Hallo,
>
> dann wäre die Aufgabe ohne die Einschränkung [mm]x\in \{0,1,...,22\}[/mm]
> auf jeden Fall richtig gelöst.
>
> > Das würde ja nicht gehen, da das x laut Aufgabe
> > ja [mm]\in \{0, ..., p-1\}[/mm] sein soll.
>
> Ja, das stimmt.
>
> Es ist [mm]-7\equiv[/mm] 16 mod 23,
>
> und mit x=16 ist die gesuchte Lösung gefunden.
>
> (Überzeuge Dich davon, daß es eine Lösung ist.)
-7 - 16 [mm] \equiv [/mm] -23 = 0 mod 23
Das ist klar. Aber wie kommt man auf die 16?
>
> LG Angela
> >
> >
> > > Gruß
> > >
> > > schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:33 Fr 29.11.2013 | | Autor: | abakus |
> >
> > > > Also so:
> > > >
> > > > [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne
> nun
> > > > erstmal ...
> > > >
> > >
> > > Da kam ich auf a=-7 und b = 4.
> > >
> > > Muss ich jetzt das a nehmen, um die Kongruenz für
> > >
> > > 13 · x ≡ 1 mod 23
> > >
> > > zu zeigen?
> >
> > Hallo,
> >
> > dann wäre die Aufgabe ohne die Einschränkung [mm]x\in \{0,1,...,22\}[/mm]
> > auf jeden Fall richtig gelöst.
> >
> > > Das würde ja nicht gehen, da das x laut Aufgabe
> > > ja [mm]\in \{0, ..., p-1\}[/mm] sein soll.
> >
> > Ja, das stimmt.
> >
> > Es ist [mm]-7\equiv[/mm] 16 mod 23,
> >
> > und mit x=16 ist die gesuchte Lösung gefunden.
> >
> > (Überzeuge Dich davon, daß es eine Lösung ist.)
>
> -7 - 16 [mm]\equiv[/mm] -23 = 0 mod 23
>
> Das ist klar. Aber wie kommt man auf die 16?
Hallo,
die Zahlen
..., -53, -30, -7, 16, 39,...
sind zueinander kongruent nach dem Modul 23, weil
1) die Differenz von zwei dieser Zahlen durch 23 teilbar ist
2) sie alle den selben Rest (nämlich 16) bei Teilung durch 23 lassen, denn es sind die Zahlen
..., (-3)*23+16, (-2)*23+16, (-1)*23+16, 0*23+16, 1*23+16,...
Gruß Abakus
>
>
> >
> > LG Angela
> > >
> > >
> > > > Gruß
> > > >
> > > > schachuzipus
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:35 Fr 29.11.2013 | | Autor: | kRAITOS |
Okay.
Also ich errechne mir x und y und davon brauche ich dann nur x.
Das setze ich ein in
13*x [mm] \equiv [/mm] 1 mod 13 mit x = -7
13*x [mm] \equiv [/mm] 1 mod 53 mit x = -4
13*x [mm] \equiv [/mm] 1 mod 89 mit x = -41
und dann schaue ich, zu welcher positiven Zahl das x kongruent ist, da die Menge, aus der das x kommen soll, ja positiv ist.
also ist -7 [mm] \equiv [/mm] 16, weil -7 +23 = 16
-4 [mm] \equiv [/mm] 49
-41 [mm] \equiv [/mm] 48
|
|
|
| |
|
> Okay.
>
> Also ich errechne mir x und y und davon brauche ich dann
> nur x.
Ja.
>
>
> Das setze ich ein in
>
> 13*x [mm]\equiv[/mm] 1 mod 13 mit x = -7
> 13*x [mm]\equiv[/mm] 1 mod 53 mit x = -4
> 13*x [mm]\equiv[/mm] 1 mod 89 mit x = -41
>
>
> und dann schaue ich, zu welcher positiven Zahl das x
> kongruent ist, da die Menge, aus der das x kommen soll, ja
> positiv ist.
>
> also ist -7 [mm]\equiv[/mm] 16, weil -7 +23 = 16
> -4 [mm]\equiv[/mm] 49
> -41 [mm]\equiv[/mm] 48
Genau.
LG Angela
>
>
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:40 Fr 29.11.2013 | | Autor: | leduart |
Hallo
-7=0+(-7)=23-7=16
immer_ -a mod p= p-amod p
Gruß leduart
|
|
|
| |
|
> > Es ist [mm]-7\equiv[/mm] 16 mod 23,
> >
> > und mit x=16 ist die gesuchte Lösung gefunden.
> >
> > (Überzeuge Dich davon, daß es eine Lösung ist.)
>
> -7 - 16 [mm]\equiv[/mm] -23 = 0 mod 23
>
> Das ist klar. Aber wie kommt man auf die 16?
Hallo,
lies -7 als "das Inverse der 7 bzgl der Addition modulo 23".
LG Angela
|
|
|
|
