Kongruenz lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Berechne alle Lösungen der Kongruenz [mm] 27x\equiv72 [/mm] (mod 900). |
Hallo!
Ich habe bis jetzt folgendes gemacht:
Mit Hilfe des euklidischen Algorithmus den ggT(27,135) ausgerechnet:
900=33*27+9
27=3*9 [mm] \Rightarrow [/mm] ggT(27,135)=9
Jetzt hab ich geteilt:
27x [mm] \equiv [/mm] 72 (mod 900) [mm] \Leftrightarrow [/mm] 3x [mm] \equiv [/mm] 8 (mod 10)
Wenn ich jetzt wieder den ggT ausrechne, also ggT(3,10)
10=3*3+1
3=1*3+0 [mm] \Rightarrow [/mm] ggT(3,10)=1 (da 3 prim)
Allerdings weiß ich nicht wirklich, was ich jetzt machen soll.
Kann mir jemand helfen?
Liebe Grüße,
Kate-Mary
|
|
| |
|
Hallo Kate-Mary,
da sind Fehler drin, die ich mir nicht erklären kann. Hast Du zwei Aufgaben vermischt?
> Berechne alle Lösungen der Kongruenz [mm]27x\equiv72[/mm] (mod
> 900).
> Hallo!
>
> Ich habe bis jetzt folgendes gemacht:
> Mit Hilfe des euklidischen Algorithmus den ggT(27,135)
> ausgerechnet:
Wozu? Woher kommt die 135? Da 135=5*27 ist, ist der ggT(27,135)=27.
> 900=33*27+9
> 27=3*9 [mm]\Rightarrow[/mm] ggT(27,135)=9
Interessant ist hier doch der ggT(27,72,900)=9.
> Jetzt hab ich geteilt:
> 27x [mm]\equiv[/mm] 72 (mod 900) [mm]\Leftrightarrow[/mm] 3x [mm]\equiv[/mm] 8 (mod
> 10)
Wieso mod 10? Das müsste doch mod 100 heißen.
> Wenn ich jetzt wieder den ggT ausrechne, also ggT(3,10)
> 10=3*3+1
> 3=1*3+0 [mm]\Rightarrow[/mm] ggT(3,10)=1 (da 3 prim)
Das ist ein unnötiger Schritt, wenn Du vorher den ggT(27,900) richtig bestimmt hast. Dann muss hier ja auf jeden Fall 1 herauskommen.
> Allerdings weiß ich nicht wirklich, was ich jetzt machen
> soll.
Löse [mm] 3x\equiv 8\mod{(100)}.
[/mm]
Bilde dazu das multiplikativ Inverse von [mm] 3\mod{(100)}. [/mm] Wahrscheinlich sollst Du das hier ganz formal tun; man kann es ja auch ganz leicht per Kopfrechnung finden.
> Kann mir jemand helfen?
Na, hoffentlich. 
Grüße
reverend
|
|
|
| |
|
Ups...okay, erst zu blöd zum abschreiben, weil ich verrutscht bin und dann auch noch zu blöd zum rechnen...
also es muss natürlich ggT(27,900)=9 heißen und 900/9 ist natürlich auch 100...
> >
> > Ich habe bis jetzt folgendes gemacht:
> > Mit Hilfe des euklidischen Algorithmus den ggT(27,135)
> > ausgerechnet:
>
> Wozu? Woher kommt die 135? Da 135=5*27 ist, ist der
> ggT(27,135)=27.
>
> > 900=33*27+9
> > 27=3*9 [mm]\Rightarrow[/mm] ggT(27,135)=9
>
> Interessant ist hier doch der ggT(27,72,900)=9.
>
...
>
> Wieso mod 10? Das müsste doch mod 100 heißen.
>
>
>
> Löse [mm]3x\equiv 8\mod{(100)}.[/mm]
> Bilde dazu das multiplikativ
> Inverse von [mm]3\mod{(100)}.[/mm] Wahrscheinlich sollst Du das hier
> ganz formal tun; man kann es ja auch ganz leicht per
> Kopfrechnung finden.
Kannst du mir erklären, warum ich das multiplikativ Inverse zu 3 mod (100) bilden muss? Weil da wär ich selber von nie drauf gekommen.
Aber hier schon mal meine Lösung (ich hoffe diesmal ohne Fehler ;) )
1. ggT(3,100):
100=33*3+1
3=3*1+0 [mm] \Rightarrow [/mm] ggT(3,100)=1
2. Umkehrung:
1=100-33*3
Aber irgendwie seh ich immernoch nicht wirklich, was mir das helfen soll. Oder hab ich das Inverse falsch berechnet??
|
|
|
| |
|
Hallo Kate-Mary,
> Ups...okay, erst zu blöd zum abschreiben, weil ich
> verrutscht bin und dann auch noch zu blöd zum rechnen...
>
> also es muss natürlich ggT(27,900)=9 heißen und 900/9 ist
> natürlich auch 100...
>
> > >
> > > Ich habe bis jetzt folgendes gemacht:
> > > Mit Hilfe des euklidischen Algorithmus den
> ggT(27,135)
> > > ausgerechnet:
> >
> > Wozu? Woher kommt die 135? Da 135=5*27 ist, ist der
> > ggT(27,135)=27.
> >
> > > 900=33*27+9
> > > 27=3*9 [mm]\Rightarrow[/mm] ggT(27,135)=9
> >
> > Interessant ist hier doch der ggT(27,72,900)=9.
> >
> ...
> >
> > Wieso mod 10? Das müsste doch mod 100 heißen.
> >
>
> >
> >
> > Löse [mm]3x\equiv 8\mod{(100)}.[/mm]
> > Bilde dazu das
> multiplikativ
> > Inverse von [mm]3\mod{(100)}.[/mm] Wahrscheinlich sollst Du das hier
> > ganz formal tun; man kann es ja auch ganz leicht per
> > Kopfrechnung finden.
>
> Kannst du mir erklären, warum ich das multiplikativ
> Inverse zu 3 mod (100) bilden muss? Weil da wär ich selber
> von nie drauf gekommen.
>
Weil 3 multipliziert mit dem multiplikativ
Inversen zu 3 den 100er 1 lässt.
> Aber hier schon mal meine Lösung (ich hoffe diesmal ohne
> Fehler ;) )
> 1. ggT(3,100):
>
> 100=33*3+1
> 3=3*1+0 [mm]\Rightarrow[/mm] ggT(3,100)=1
>
> 2. Umkehrung:
> 1=100-33*3
>
> Aber irgendwie seh ich immernoch nicht wirklich, was mir
> das helfen soll. Oder hab ich das Inverse falsch
> berechnet??
>
Multipliziere doch die Ausgangsgleichung mit diesem multiplikativ Inversen zu 3.
Dann hast Du da stehen: [mm]x\equiv 8*3^{-1}\mod{(100)}[/mm]
[mm]3^{-1}[/mm] ist das multiplikativ Inverse zu 3.
Gruss
MathePower
|
|
|
| |
|
Also irgendwie steh ich grad ziemlich auf dem Schlauch:
Nach Umformung der ursprünglichen Gleichung hab ich [mm] 3x\equiv [/mm] 8 mod (100) herausbekommen.
Logisch ist, dass ich jetzt diese Gleichung lösen muss.
reverend hat mir dazu den Tipp gegeben, dass ich das Multiplikative von 3 mod (100) berechnen soll.
Die Erklärung
>
> Weil 3 multipliziert mit dem multiplikativ
> Inversen zu 3 den 100er 1 lässt.
>
versteh ich irgendwie nicht so ganz :(
>
> Multipliziere doch die Ausgangsgleichung mit diesem
> multiplikativ Inversen zu 3.
>
> Dann hast Du da stehen: [mm]x\equiv 8*3^{-1}\mod{(100)}[/mm]
>
> [mm]3^{-1}[/mm] ist das multiplikativ Inverse zu 3.
>
soll ich da jetzt für 3^-1 noch was einsetzen oder wie ist das zu verstehen?
LG
|
|
|
| |
|
Hallo Kate-Mary,
> Also irgendwie steh ich grad ziemlich auf dem Schlauch:
>
> Nach Umformung der ursprünglichen Gleichung hab ich
> [mm]3x\equiv[/mm] 8 mod (100) herausbekommen.
> Logisch ist, dass ich jetzt diese Gleichung lösen muss.
> reverend hat mir dazu den Tipp gegeben, dass ich das
> Multiplikative von 3 mod (100) berechnen soll.
> Die Erklärung
> >
> > Weil 3 multipliziert mit dem multiplikativ
> > Inversen zu 3 den 100er 1 lässt.
> >
> versteh ich irgendwie nicht so ganz :(
>
Nun Du hast weiter unten das multiplikativ Inverse zu 3 mit -33 berechnet.
3*(-33)=-99=-100+1.
Damit lässt dies den 100er Rest 1.
Daher lautet jetzt die neue Gleichung:
[mm]3*(-33) x \equiv 1*x \equiv 8*(-33) \ \operatorname{mod} \left(100\right)[/mm]
> >
> > Multipliziere doch die Ausgangsgleichung mit diesem
> > multiplikativ Inversen zu 3.
> >
> > Dann hast Du da stehen: [mm]x\equiv 8*3^{-1}\mod{(100)}[/mm]
> >
> > [mm]3^{-1}[/mm] ist das multiplikativ Inverse zu 3.
> >
> soll ich da jetzt für 3^-1 noch was einsetzen oder wie ist
> das zu verstehen?
>
Setze für [mm]3^{-1}[/mm] das berechnete multiplikativ Inverse -33 ein.
> LG
>
Grus
MathePower
|
|
|
| |
|
Okay, soweit versteh ich das jetzt,
wenn ich jetzt in [mm] x\equiv 8*3^{-1} [/mm] mod (100) für [mm] 3^{-1} [/mm] -33 einsetze und dass ausrechne, dann kommt
[mm] x\equiv [/mm] -264 mod 100 raus.
Und das soll jetzt die Lösung sein?
Geb ich die Lösung dann folgendermaßen angeben?
[mm] \IL= [/mm] { -264+100z; [mm] z\in \IZ [/mm] }
LG
|
|
|
| |
|
Hallo Kate-Mary,
> Okay, soweit versteh ich das jetzt,
>
> wenn ich jetzt in [mm]x\equiv 8*3^{-1}[/mm] mod (100) für [mm]3^{-1}[/mm]
> -33 einsetze und dass ausrechne, dann kommt
> [mm]x\equiv[/mm] -264 mod 100 raus.
>
> Und das soll jetzt die Lösung sein?
Ja, das ist die Lösung.
> Geb ich die Lösung dann folgendermaßen angeben?
> [mm]\IL=\{ -264+100z; \ z \in \IZ \}[/mm]
>
Ja.
> LG
>
Gruss
MathePower
|
|
|
| |
|
| Aufgabe | | Berechne alle Lösungen 9x [mm] \equiv [/mm] 12 mod 12 |
Danke.
Oben steht noch eine zweite Aufgabe, die analog laufen sollte. Ich hab das mal schnell durchgerechnet.
Kannst du mir sagen, ob das so richtig ist?
9x [mm] \equiv [/mm] 12 mod 12
ggT (9,12)
12=1*9+3
9=3*3+0 [mm] \Rightarrow [/mm] ggT(9,12)=3
9x [mm] \equiv [/mm] 12 mod 12 [mm] \Leftrightarrow [/mm] 3x [mm] \equiv [/mm] 4 mod 4
Multiplikativ Inverses zu 3 mod 4:
4=1*3+1
3=3*1+0 [mm] \Rightarrow [/mm] ggT(3,4)=1
[mm] \Rightarrow [/mm] 1=4-3*1
[mm] \Rightarrow x\equiv [/mm] 4*(-4) mod 4 =-12 mod 4
[mm] \Rightarrow \IL= [/mm] {-12+4z ; [mm] z\in \IZ [/mm] }
LG
|
|
|
| |
|
Hallo Kate-Mary,
> Berechne alle Lösungen 9x [mm]\equiv[/mm] 12 mod 12
> Danke.
>
> Oben steht noch eine zweite Aufgabe, die analog laufen
> sollte. Ich hab das mal schnell durchgerechnet.
> Kannst du mir sagen, ob das so richtig ist?
>
> 9x [mm]\equiv[/mm] 12 mod 12
>
> ggT (9,12)
> 12=1*9+3
> 9=3*3+0 [mm]\Rightarrow[/mm] ggT(9,12)=3
>
> 9x [mm]\equiv[/mm] 12 mod 12 [mm]\Leftrightarrow[/mm] 3x [mm]\equiv[/mm] 4 mod 4
>
> Multiplikativ Inverses zu 3 mod 4:
> 4=1*3+1
> 3=3*1+0 [mm]\Rightarrow[/mm] ggT(3,4)=1
> [mm]\Rightarrow[/mm] 1=4-3*1
>
> [mm]\Rightarrow x\equiv[/mm] 4*(-4) mod 4 =-12 mod 4
>
> [mm]\Rightarrow \IL=[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{-12+4z ; [mm]z\in \IZ[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
>
Oder besser, da -12 ein Vielfaches von 4 ist:
[mm]\IL=\{4z ; z\in \IZ \}[/mm]
> LG
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:20 So 26.05.2013 | | Autor: | abakus |
> Berechne alle Lösungen 9x [mm]\equiv[/mm] 12 mod 12
> Danke.
>
> Oben steht noch eine zweite Aufgabe, die analog laufen
> sollte. Ich hab das mal schnell durchgerechnet.
> Kannst du mir sagen, ob das so richtig ist?
>
> 9x [mm]\equiv[/mm] 12 mod 12
Hallo,
Es gilt doch 12 [mm]\equiv[/mm] 0 mod 12.
Daraus folgt also 9x [mm]\equiv[/mm] 0 mod 12 oder
"9x ist durch 12 teilbar".
Da 9 durch 3 teilbar ist, muss x einfach nur durch 4 teilbar sein.
Gruß Abakus
>
> ggT (9,12)
> 12=1*9+3
> 9=3*3+0 [mm]\Rightarrow[/mm] ggT(9,12)=3
>
> 9x [mm]\equiv[/mm] 12 mod 12 [mm]\Leftrightarrow[/mm] 3x [mm]\equiv[/mm] 4 mod 4
>
> Multiplikativ Inverses zu 3 mod 4:
> 4=1*3+1
> 3=3*1+0 [mm]\Rightarrow[/mm] ggT(3,4)=1
> [mm]\Rightarrow[/mm] 1=4-3*1
>
> [mm]\Rightarrow x\equiv[/mm] 4*(-4) mod 4 =-12 mod 4
>
> [mm]\Rightarrow \IL=[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{-12+4z ; [mm]z\in \IZ[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
>
> LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:01 So 26.05.2013 | | Autor: | Marcel |
Hi Abakus,
> > 9x [mm]\equiv[/mm] 12 mod 12
>
> Hallo,
> Es gilt doch 12 [mm]\equiv[/mm] 0 mod 12.
> Daraus folgt also 9x [mm]\equiv[/mm] 0 mod 12 oder
> "9x ist durch 12 teilbar".
ich würde sowieso gerne mal generell drauf hinweisen:
Für $a,b,p,q [mm] \in \IZ$ [/mm] und $n [mm] \in \IN$ [/mm] gilt
$$a [mm] \equiv [/mm] b [mm] \mod [/mm] n$$
[mm] $$\iff [/mm] a+p*n [mm] \equiv [/mm] b+q*n [mm] \mod [/mm] n$$
> Da 9 durch 3 teilbar ist, muss x einfach nur durch 4
> teilbar sein.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:02 So 26.05.2013 | | Autor: | Kate-Mary |
Ja, das ist klar. Ich wollte aber die Aufgabe analog zur vorherigen lösen, um zu schaun, ob ich alle skapiert habe. Trotzdem Danke.
Danke auch an MathePower!!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:08 So 26.05.2013 | | Autor: | Marcel |
Hallo,
> ... um zu schaun, ob ich
> alle skapiert habe.
ich hoffe, Du wolltest nicht alle [mm] ska$\red{\ell}$pieren [/mm] ^^
Gruß,
Marcel
|
|
|
|
