Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:05 Di 22.09.2009 | | Autor: | D-C |
| Aufgabe | a)
6x [mm] \equiv [/mm] 1 mod 11
Lösbar, wenn ja warum?
Wenn ja, Lösung bestimmen.
b)
Bestimmen Sie alle Lösungen der Kongruenz
[mm] x^2 \equiv [/mm] 8 mod 77. |
Zu a)
ax = b(m) ist ja genau dann lösbar, wenn ggT(a,m) teilt b.
Also:
6x [mm] \equiv [/mm] 1(11)
ggT(6,11)
11 = 1*6 + 5
6 = 1*5 + 1
5 = 5*1 + 0
=> ggT(6,11) = 1
1 teilt 1
=> ist eindeutig lösbar
Als Lösung soll herauskommen x [mm] \equiv [/mm] 2(11) .
Nur wie kommt man darauf?
zu b)
Wie geht man hier am besten vor?
Gruß
D-C
|
|
| |
|
Hallo D-C,
> a)
> 6x [mm]\equiv[/mm] 1 mod 11
>
> Lösbar, wenn ja warum?
> Wenn ja, Lösung bestimmen.
>
> b)
> Bestimmen Sie alle Lösungen der Kongruenz
> [mm]x^2 \equiv[/mm] 8 mod 77.
> Zu a)
>
> ax = b(m) ist ja genau dann lösbar, wenn ggT(a,m) teilt
> b.
>
> Also:
>
> 6x [mm]\equiv[/mm] 1(11)
> ggT(6,11)
> 11 = 1*6 + 5
> 6 = 1*5 + 1
> 5 = 5*1 + 0
>
> => ggT(6,11) = 1
> 1 teilt 1
> => ist eindeutig lösbar
>
>
> Als Lösung soll herauskommen x [mm]\equiv[/mm] 2(11) .
Wende den euklidischen Algorithmus rückwärts an:
[mm]1=1 \* 6 - 1 \* 5[/mm]
Ersetze nun die 5 aus
[mm]11=1 \* 6 +5[/mm]
Damit erigibt sich
[mm]1=1 \* 6 - 1 \* \left(1 \* 11 - 1 \* 6\right)=2 \* 6 - 1\* 11[/mm]
Somit ist 2 das Inverse von 6 modulo 11.
>
> Nur wie kommt man darauf?
>
>
> zu b)
>
> Wie geht man hier am besten vor?
>
>
> Gruß
>
> D-C
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:37 Di 22.09.2009 | | Autor: | D-C |
Stimmt da war ja noch die Möglichkeit, das Rückwärts anzuwenden, da hätte ich auch drauf kommen können, aber na ja manchmal sieht mans irgendwie einfach nicht... : )
Gruß
D-C
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:56 Mi 23.09.2009 | | Autor: | D-C |
> Wende den euklidischen Algorithmus rückwärts an:
>
> [mm]1=1 \* 6 - 1 \* 5[/mm]
>
> Ersetze nun die 5 aus
>
> [mm]11=1 \* 6 +5[/mm]
>
> Damit erigibt sich
>
> [mm]1=1 \* 6 - 1 \* \left(1 \* 11 - 1 \* 6\right)=2 \* 6 - 1\* 11[/mm]
>
> Somit ist 2 das Inverse von 6 modulo 11.
>
So, hab das nochmal für mich gerechnet und bin nun auch auf das Ergebnis gekommen.
Aber bei einer anderen Aufgabe scheine ich noch nen Fehler zu machen:
12x [mm] \equiv [/mm] 5 mod 17
ggT(12,17)
17 = 1*12 + 5
12 = 2*5 + 2
5 = 2*2 + 1
2 = 2*1 + 0
ggT(12,17) = 1 , 1 teilt 5 => eindeutig lösbar
Rückwärts:
1 =1*5 - 2*2
Ersetzen der 2
=1*5 - 2*(1*12 - 2*5)
=1*5 - 2*12 + 4*5
=5*5 - 2*12
Ersetzen der 5
=5*(1*17-1*12) - 2*12
=5*17 - 5*12 - 2*12
=5*17-7*12
Herauskommen soll x [mm] \equiv [/mm] 16 mod 17 ...
Und wie wäre es bei 3x [mm] \equiv [/mm] 19 mod 31
ggT(3,31)
31 = 10*3 + 1
3 = 3*1 + 0
Hier besteht der Rückwärtsschritt ja nur aus
1 = 1*31 - 10*3
Ersetzen kann ich hier ja dann nichts weiter..
Gruß
D-C
|
|
|
| |
|
Hallo D-C.
> > Wende den euklidischen Algorithmus rückwärts an:
> >
> > [mm]1=1 \* 6 - 1 \* 5[/mm]
> >
> > Ersetze nun die 5 aus
> >
> > [mm]11=1 \* 6 +5[/mm]
> >
> > Damit erigibt sich
> >
> > [mm]1=1 \* 6 - 1 \* \left(1 \* 11 - 1 \* 6\right)=2 \* 6 - 1\* 11[/mm]
>
> >
> > Somit ist 2 das Inverse von 6 modulo 11.
> >
>
> So, hab das nochmal für mich gerechnet und bin nun auch
> auf das Ergebnis gekommen.
>
> Aber bei einer anderen Aufgabe scheine ich noch nen Fehler
> zu machen:
>
> 12x [mm]\equiv[/mm] 5 mod 17
>
> ggT(12,17)
> 17 = 1*12 + 5
> 12 = 2*5 + 2
> 5 = 2*2 + 1
> 2 = 2*1 + 0
>
> ggT(12,17) = 1 , 1 teilt 5 => eindeutig lösbar
>
> Rückwärts:
> 1 =1*5 - 2*2
> Ersetzen der 2
> =1*5 - 2*(1*12 - 2*5)
> =1*5 - 2*12 + 4*5
> =5*5 - 2*12
> Ersetzen der 5
> =5*(1*17-1*12) - 2*12
> =5*17 - 5*12 - 2*12
> =5*17-7*12
![[ok]](/images/smileys/ok.gif "[ok]")
>
> Herauskommen soll x [mm]\equiv[/mm] 16 mod 17 ...
>
>
Es ist [mm]-7 \equiv 10[/mm] das Inverse von 12 modulo 17.
Daher ergibt sich [mm]x \equiv 5*12^{-1} = 5*10 =50 \equiv 16[/mm] modulo 17.
>
>
> Und wie wäre es bei 3x [mm]\equiv[/mm] 19 mod 31
>
> ggT(3,31)
> 31 = 10*3 + 1
> 3 = 3*1 + 0
>
> Hier besteht der Rückwärtsschritt ja nur aus
> 1 = 1*31 - 10*3
Hier ist [mm]-10 \equiv 21[/mm] das Inverse von 3 modulo 31.
Damit ergibt sich [mm]x \equiv 19*3^{-1}=19*21 \equiv 27[/mm] modulo 31.
>
> Ersetzen kann ich hier ja dann nichts weiter..
>
> Gruß
> D-C
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:00 Mi 23.09.2009 | | Autor: | D-C |
>5*17-7*12
>
>
>
> Es ist [mm]-7 \equiv 10[/mm] das Inverse von 12 modulo 17.
Soweit klar.
> Daher ergibt sich [mm]x \equiv 5*12^{-1} = 5*10 =50 \equiv 16[/mm]
> modulo 17.
Die Zeile ist mir auch klar, bis auf die 5, bzw. unten die 19 !?
> > 1 = 1*31 - 10*3
>
>
> Hier ist [mm]-10 \equiv 21[/mm] das Inverse von 3 modulo 31.
>
> Damit ergibt sich [mm]x \equiv 19*3^{-1}=19*21 \equiv 27[/mm] modulo
> 31.
Gruß´
D-C
|
|
|
| |
|
Hallo D-C,
> >5*17-7*12
> >
> >
> >
> > Es ist [mm]-7 \equiv 10[/mm] das Inverse von 12 modulo 17.
>
>
> Soweit klar.
>
> > Daher ergibt sich [mm]x \equiv 5*12^{-1} = 5*10 =50 \equiv 16[/mm]
> > modulo 17.
>
> Die Zeile ist mir auch klar, bis auf die 5, bzw. unten die
> 19 !?
Wir haben die Kongruenz
[mm]12*x \equiv 5 \ \left(17\right)[/mm]
zu lösen.
Multplizieren wir obige Gleichung mit dem Inversen von 12,
dann ergibt sich:
[mm]\blue{12^{-1}}*12*x \equiv \blue{12^{-1}}*5[/mm]
[mm]1*x \equiv \blue{12^{-1}}*5[/mm]
Da die Multiplikation kommutativ ist, gilt:
[mm]x \equiv \blue{12^{-1}}*5= 5*\blue{12^{-1}}[/mm]
Analog für die zweite Aufgabe.
>
>
> > > 1 = 1*31 - 10*3
> >
> >
> > Hier ist [mm]-10 \equiv 21[/mm] das Inverse von 3 modulo 31.
> >
> > Damit ergibt sich [mm]x \equiv 19*3^{-1}=19*21 \equiv 27[/mm] modulo
> > 31.
>
> Gruß´
>
> D-C
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:09 Mi 23.09.2009 | | Autor: | D-C |
> Analog für die zweite Aufgabe.
>
Habs mal ausführlich durchgerechnet:
1 = 1*31 - 10*3
Es ist -10 [mm] \equiv [/mm] 21 das Inverse von 19 mod 31
Daraus folgt für 3x [mm] \equiv [/mm] 19 mod 31:
[mm] 3^{-1} [/mm] * 3x [mm] \equiv 3^{-1} [/mm] *19
1x [mm] \equiv 3^{-1} [/mm] *19
x [mm] \equiv [/mm] 19 * [mm] 3^{-1}
[/mm]
x [mm] \equiv [/mm] 19 *21
x [mm] \equiv [/mm] 399
x [mm] \equiv [/mm] 27 mod 31
Das sollte dann jetzt so richtig sein hoffe ich !? : )
Gruß
D-C
|
|
|
| |
|
Hallo D-C,
> > Analog für die zweite Aufgabe.
> >
>
>
> Habs mal ausführlich durchgerechnet:
>
> 1 = 1*31 - 10*3
>
> Es ist -10 [mm]\equiv[/mm] 21 das Inverse von 19 mod 31
>
> Daraus folgt für 3x [mm]\equiv[/mm] 19 mod 31:
>
> [mm]3^{-1}[/mm] * 3x [mm]\equiv 3^{-1}[/mm] *19
>
> 1x [mm]\equiv 3^{-1}[/mm] *19
> x [mm]\equiv[/mm] 19 * [mm]3^{-1}[/mm]
> x [mm]\equiv[/mm] 19 *21
> x [mm]\equiv[/mm] 399
> x [mm]\equiv[/mm] 27 mod 31
>
> Das sollte dann jetzt so richtig sein hoffe ich !? : )
>
Ja.
>
> Gruß
>
> D-C
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:24 Mi 23.09.2009 | | Autor: | D-C |
Hi.
Schön,
dann danke für die ausführliche Hilfe : )
Gruß
D-C
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:33 Di 22.09.2009 | | Autor: | abakus |
> a)
> 6x [mm]\equiv[/mm] 1 mod 11
>
> Lösbar, wenn ja warum?
> Wenn ja, Lösung bestimmen.
>
> b)
> Bestimmen Sie alle Lösungen der Kongruenz
> [mm]x^2 \equiv[/mm] 8 mod 77.
> Zu a)
>
> ax = b(m) ist ja genau dann lösbar, wenn ggT(a,m) teilt
> b.
>
> Also:
>
> 6x [mm]\equiv[/mm] 1(11)
> ggT(6,11)
> 11 = 1*6 + 5
> 6 = 1*5 + 1
> 5 = 5*1 + 0
>
> => ggT(6,11) = 1
> 1 teilt 1
> => ist eindeutig lösbar
>
>
> Als Lösung soll herauskommen x [mm]\equiv[/mm] 2(11) .
>
> Nur wie kommt man darauf?
Mit einem endlichen Aufwand des Probierens von Möglichkeiten.
Vermutlich werden die Terme 6*1, 6*2, 6*3, ... 6*11 allesamt verschiedene Reste mod 11 liefern.
Da es nur 11 mögliche Reste gibt, hast du spätestens im 11. Versuch auch den gewünschten Rest 2.
Wenn man natürlich "sieht", dass 1 [mm] \equiv [/mm] 12 mod 11 ist und 12 durch 6 teilbar ist, kann man aus 6x [mm] \equiv [/mm] 1 mod 11 sofort auf 6x [mm] \equiv [/mm] 12 mod 11 und damit auf die Lösung schließen.
>
>
> zu b)
>
> Wie geht man hier am besten vor?
Spätestens im 77. Versuch hast du die Lösung.
Da allerdings 76 [mm] \equiv [/mm] -1 mod 77, 75 [mm] \equiv [/mm] -2 mod 77 usw gilt, ist [mm] 76^2 \equiv 1^2 [/mm] mod 77, [mm] 75^2 \equiv 2^2 [/mm] mod 77 usw.
Die Reste treten also paarweise auf, sodass du nur die Hälfte aller 77 Möglichkeiten testen musst.
Alternative: Addiere zu 8 so lange die Zahl 77, bis du eine Quadratzahl erhältst.
2. Alternative:
Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt, lässt bei Teilung durch 7 den Rest 1 und bei ilung durch 11 den Rest 8 (bzw. -3).
Gruß Abakus
>
>
> Gruß
>
> D-C
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:51 Di 22.09.2009 | | Autor: | D-C |
> >
> > zu b)
> >
> > Wie geht man hier am besten vor?
> Spätestens im 77. Versuch hast du die Lösung.
> Da allerdings 76 [mm]\equiv[/mm] -1 mod 77, 75 [mm]\equiv[/mm] -2 mod 77 usw
> gilt, ist [mm]76^2 \equiv 1^2[/mm] mod 77, [mm]75^2 \equiv 2^2[/mm] mod 77
> usw.
> Die Reste treten also paarweise auf, sodass du nur die
> Hälfte aller 77 Möglichkeiten testen musst.
> Alternative: Addiere zu 8 so lange die Zahl 77, bis du
> eine Quadratzahl erhältst.
> 2. Alternative:
> Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> lässt bei Teilung durch 7 den Rest 1 und bei ilung durch
> 11 den Rest 8 (bzw. -3).
> Gruß Abakus
> >
Ok, werde mir das morgen nochmal in Ruhe anschauen.
Hab mir nur schonmal die 1. Alternative angeschaut, da müsste die erste Quadratzahl dann 6400 sein...
Gruß
D-C
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:46 Mi 23.09.2009 | | Autor: | D-C |
> Mit einem endlichen Aufwand des Probierens von
> Möglichkeiten.
> Vermutlich werden die Terme 6*1, 6*2, 6*3, ... 6*11
> allesamt verschiedene Reste mod 11 liefern.
> Da es nur 11 mögliche Reste gibt, hast du spätestens im
> 11. Versuch auch den gewünschten Rest 2.
Ja, es lassen sich alle Elemente 1,2,...,10 darstellen. Der Rest 2 ergibt sich bei [mm] 6^9 [/mm] = 1007796 = 2 mod 11.
Nur woran erkennt man, dass das dann genau der gesuchte Rest ist?
> Wenn man natürlich "sieht", dass 1 [mm]\equiv[/mm] 12 mod 11 ist
> und 12 durch 6 teilbar ist, kann man aus 6x [mm]\equiv[/mm] 1 mod 11
> sofort auf 6x [mm]\equiv[/mm] 12 mod 11 und damit auf die Lösung
> schließen.
>
Also wenn man das "sieht", ist dann hier der Punkt, das aus der obigen Betrachtung und aus 12:6 die 2 als Ergebnis folgt?
Wie wäre es denn dann z.B. bei 12x [mm] \equiv [/mm] 5 mod 17 ?
Variante 1 wird durch Ausprobieren ab einer gewissen Größe ja ziemlich aufwendig. Lässt sich hier auch eine Alternative finden?
> > zu b)
> >
> > Wie geht man hier am besten vor?
> Spätestens im 77. Versuch hast du die Lösung.
> Da allerdings 76 [mm]\equiv[/mm] -1 mod 77, 75 [mm]\equiv[/mm] -2 mod 77 usw
> gilt, ist [mm]76^2 \equiv 1^2[/mm] mod 77, [mm]75^2 \equiv 2^2[/mm] mod 77
> usw.
> Die Reste treten also paarweise auf, sodass du nur die
> Hälfte aller 77 Möglichkeiten testen musst.
> Alternative: Addiere zu 8 so lange die Zahl 77, bis du
> eine Quadratzahl erhältst.
> 2. Alternative:
> Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> lässt bei Teilung durch 7 den Rest 1 und bei ilung durch
> 11 den Rest 8 (bzw. -3).
> Gruß Abakus
> >
> >
> > Gruß
> >
> > D-C
>
Selbst wenn man nur die Hälfte betrachtet, ist das ja schon recht viel,
da scheint mir auf den ersten Blick die 1. Alternative schneller.
Bin hier auf 6400 als erste Quadratzahl gekommen. Wie gehts denn dann weiter?
Die 2. Alternative hab ich noch nicht so ganz verstanden, wie mich das weiterbringt..
Gruß
D-C
|
|
|
| |
|
Hallo D-C,
> > Mit einem endlichen Aufwand des Probierens von
> > Möglichkeiten.
> > Vermutlich werden die Terme 6*1, 6*2, 6*3, ... 6*11
> > allesamt verschiedene Reste mod 11 liefern.
> > Da es nur 11 mögliche Reste gibt, hast du spätestens
> im
> > 11. Versuch auch den gewünschten Rest 2.
>
> Ja, es lassen sich alle Elemente 1,2,...,10 darstellen. Der
> Rest 2 ergibt sich bei [mm]6^9[/mm] = 1007796 = 2 mod 11.
>
> Nur woran erkennt man, dass das dann genau der gesuchte
> Rest ist?
>
Nun, weil 2 das Inverse von 6 modulo 11 ist.
>
> > Wenn man natürlich "sieht", dass 1 [mm]\equiv[/mm] 12 mod 11 ist
> > und 12 durch 6 teilbar ist, kann man aus 6x [mm]\equiv[/mm] 1 mod 11
> > sofort auf 6x [mm]\equiv[/mm] 12 mod 11 und damit auf die Lösung
> > schließen.
> >
>
> Also wenn man das "sieht", ist dann hier der Punkt, das aus
> der obigen Betrachtung und aus 12:6 die 2 als Ergebnis
> folgt?
Ja.
>
> Wie wäre es denn dann z.B. bei 12x [mm]\equiv[/mm] 5 mod 17 ?
> Variante 1 wird durch Ausprobieren ab einer gewissen
> Größe ja ziemlich aufwendig. Lässt sich hier auch eine
> Alternative finden?
>
Die Idee ist immer dieselbe.
Berechne hier das Inverse von 12 modulo 17.
Das kannst Du mit Hilfe des Euklidischen Algorithmus tun.
Dann ergibt sich die Lösung zu: [mm]x \equiv 5*12^{-1}[/mm]
[mm]12^{-1}[/mm] bezeichnet eben dieses Inverse von 12 modulo 17.
>
> > > zu b)
> > >
> > > Wie geht man hier am besten vor?
> > Spätestens im 77. Versuch hast du die Lösung.
> > Da allerdings 76 [mm]\equiv[/mm] -1 mod 77, 75 [mm]\equiv[/mm] -2 mod 77
> usw
> > gilt, ist [mm]76^2 \equiv 1^2[/mm] mod 77, [mm]75^2 \equiv 2^2[/mm] mod 77
> > usw.
> > Die Reste treten also paarweise auf, sodass du nur die
> > Hälfte aller 77 Möglichkeiten testen musst.
> > Alternative: Addiere zu 8 so lange die Zahl 77, bis du
> > eine Quadratzahl erhältst.
> > 2. Alternative:
> > Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> > lässt bei Teilung durch 7 den Rest 1 und bei ilung durch
> > 11 den Rest 8 (bzw. -3).
> > Gruß Abakus
> > >
> > >
> > > Gruß
> > >
> > > D-C
> >
>
> Selbst wenn man nur die Hälfte betrachtet, ist das ja
> schon recht viel,
> da scheint mir auf den ersten Blick die 1. Alternative
> schneller.
> Bin hier auf 6400 als erste Quadratzahl gekommen. Wie
> gehts denn dann weiter?
[mm]6400=80^{2}[/mm] läßt bei Division durch 77 nicht den Rest 8.
> Die 2. Alternative hab ich noch nicht so ganz verstanden,
> wie mich das weiterbringt..
Nun berechne für [mm]x \equiv 0 ... 6[/mm] das Quadrat modulo 7.
Dasselbe machst Du für [mm]x \equiv 0 ... 10[/mm] das Quadrat modulo 11.
>
> Gruß
>
> D-C
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:23 Mi 23.09.2009 | | Autor: | D-C |
Hi,
die a) ist mir dann soweit jetzt klar : )
> [mm]6400=80^{2}[/mm] läßt bei Division durch 77 nicht den Rest 8.
Dann hab ich mich da wohl irgendwo vertan....
> > Die 2. Alternative hab ich noch nicht so ganz verstanden,
> > wie mich das weiterbringt..
>
>
> Nun berechne für [mm]x \equiv 0 ... 6[/mm] das Quadrat modulo 7.
>
> Dasselbe machst Du für [mm]x \equiv 0 ... 10[/mm] das Quadrat
> modulo 11.
Meinst Du damit:
[mm] 0^2 [/mm] = 0 mod 7
[mm] 1^2 [/mm] = 1 mod 7
[mm] 2^2 [/mm] = 4 mod 7
[mm] 3^2 [/mm] = 2 mod 7
[mm] 4^2 [/mm] = 2 mod 7
[mm] 5^2 [/mm] = 4 mod 7
[mm] 6^2 [/mm] = 1 mod 7
und
[mm] 0^2 [/mm] = 0 mod 11
[mm] 1^2 [/mm] = 1 mod 11
[mm] 2^2 [/mm] = 4 mod 11
[mm] 3^2 [/mm] = 9 mod 11
[mm] 4^2 [/mm] = 5 mod 11
[mm] 5^2 [/mm] = 3 mod 11
[mm] 6^2 [/mm] = 3 mod 11
[mm] 7^2 [/mm] = 5 mod 11
[mm] 8^2 [/mm] = 9 mod 11
[mm] 9^2 [/mm] = 4 mod 11
[mm] 10^2 [/mm] = 1 mod 11
Am Anfang hieß es ja:
[mm] x^2 \equiv [/mm] 8 mod 77 soll bedeuten:
> Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> lässt bei Teilung durch 7 den Rest 1 und bei Teilung durch
> 11 den Rest 8 (bzw. -3).
Die 7 und die 11 kommen wohl von der Zerlegung der 77 in Primfaktoren oder?
Ist es dann immer so, dass ein Rest 1 und der andere wie "vor" dem "mod angegeben ist ?
Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie geht es weiter?
Gruß
D-C
|
|
|
| |
|
Hallo D-C,
> Hi,
>
> die a) ist mir dann soweit jetzt klar : )
>
>
> > [mm]6400=80^{2}[/mm] läßt bei Division durch 77 nicht den Rest 8.
>
> Dann hab ich mich da wohl irgendwo vertan....
>
>
>
> > > Die 2. Alternative hab ich noch nicht so ganz verstanden,
> > > wie mich das weiterbringt..
> >
> >
> > Nun berechne für [mm]x \equiv 0 ... 6[/mm] das Quadrat modulo 7.
> >
> > Dasselbe machst Du für [mm]x \equiv 0 ... 10[/mm] das Quadrat
> > modulo 11.
>
> Meinst Du damit:
>
> [mm]0^2[/mm] = 0 mod 7
> [mm]1^2[/mm] = 1 mod 7
> [mm]2^2[/mm] = 4 mod 7
> [mm]3^2[/mm] = 2 mod 7
> [mm]4^2[/mm] = 2 mod 7
> [mm]5^2[/mm] = 4 mod 7
> [mm]6^2[/mm] = 1 mod 7
>
> und
>
> [mm]0^2[/mm] = 0 mod 11
> [mm]1^2[/mm] = 1 mod 11
> [mm]2^2[/mm] = 4 mod 11
> [mm]3^2[/mm] = 9 mod 11
> [mm]4^2[/mm] = 5 mod 11
> [mm]5^2[/mm] = 3 mod 11
> [mm]6^2[/mm] = 3 mod 11
> [mm]7^2[/mm] = 5 mod 11
> [mm]8^2[/mm] = 9 mod 11
> [mm]9^2[/mm] = 4 mod 11
> [mm]10^2[/mm] = 1 mod 11
Genau.
>
> Am Anfang hieß es ja:
>
> [mm]x^2 \equiv[/mm] 8 mod 77 soll bedeuten:
>
> > Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> > lässt bei Teilung durch 7 den Rest 1 und bei Teilung durch
> > 11 den Rest 8 (bzw. -3).
>
> Die 7 und die 11 kommen wohl von der Zerlegung der 77 in
> Primfaktoren oder?
Ja, klar.
> Ist es dann immer so, dass ein Rest 1 und der andere wie
> "vor" dem "mod angegeben ist ?
Nein.
Nehme hier zum Beispiel die Kongruenz
[mm]x^{2} \equiv 13 \ \left(77\right)[/mm]
Dann muß gelten:
[mm]x^{2} \equiv 13 \equiv 6 \ \left(7\right)[/mm]
[mm]x^{2} \equiv 13 \equiv 2 \ \left(11\right)[/mm]
>
> Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest
> 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie
> geht es weiter?
>
Jetzt schaust Du danach, wo die entsprechenden Reste sind.
>
> Gruß
>
> D-C
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:42 Mi 23.09.2009 | | Autor: | D-C |
Hi,
es geht voran : )
> Nehme hier zum Beispiel die Kongruenz
>
> [mm]x^{2} \equiv 13 \ \left(77\right)[/mm]
>
> Dann muß gelten:
>
> [mm]x^{2} \equiv 13 \equiv 6 \ \left(7\right)[/mm]
>
> [mm]x^{2} \equiv 13 \equiv 2 \ \left(11\right)[/mm]
Ok, jetzt ist mir das klar.
> > Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest
> > 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie
> > geht es weiter?
> >
>
>
> Jetzt schaust Du danach, wo die entsprechenden Reste sind.
Die entsprechenden Reste müssten dann bei den Quadraten von mod7
bei [mm] 1^2 [/mm] und [mm] 6^2
[/mm]
sowie bei mod 11
bei [mm] 5^2 [/mm] und [mm] 6^2
[/mm]
liegen. Jetzt fehlt mir nur noch irgendwie der letzte Schluss, der mich zur Lösung bringt..
Gruß
D-C
|
|
|
| |
|
Hallo D-C,
> Hi,
>
> es geht voran : )
>
> > Nehme hier zum Beispiel die Kongruenz
> >
> > [mm]x^{2} \equiv 13 \ \left(77\right)[/mm]
> >
> > Dann muß gelten:
> >
> > [mm]x^{2} \equiv 13 \equiv 6 \ \left(7\right)[/mm]
> >
> > [mm]x^{2} \equiv 13 \equiv 2 \ \left(11\right)[/mm]
>
>
> Ok, jetzt ist mir das klar.
>
>
>
> > > Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest
> > > 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie
> > > geht es weiter?
> > >
> >
> >
> > Jetzt schaust Du danach, wo die entsprechenden Reste sind.
>
>
> Die entsprechenden Reste müssten dann bei den Quadraten
> von mod7
> bei [mm]1^2[/mm] und [mm]6^2[/mm]
>
> sowie bei mod 11
> bei [mm]5^2[/mm] und [mm]6^2[/mm]
Das stimmt nicht: [mm]5^{2}=25 \equiv 3 \not= 8 \ \left(11\right)[/mm]
>
> liegen. Jetzt fehlt mir nur noch irgendwie der letzte
> Schluss, der mich zur Lösung bringt..
>
>
> Gruß
> D-C
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:09 Mi 23.09.2009 | | Autor: | D-C |
Hi,
> > Die entsprechenden Reste müssten dann bei den Quadraten
> > von mod7
> > bei [mm]1^2[/mm] und [mm]6^2[/mm]
>
>
>
> > sowie bei mod 11
> > bei [mm]5^2[/mm] und [mm]6^2[/mm]
>
> Das stimmt nicht: [mm]5^{2}=25 \equiv 3 \not= 8 \ \left(11\right)[/mm]
Achso, ich hab hier die 3 zu Grunde gelegt, ein Rest 8 kommt dann hier wohl nicht vor....
> > Jetzt fehlt mir nur noch irgendwie der letzte
> > Schluss, der mich zur Lösung bringt..
Gruß
D-C
|
|
|
| |
|
Hallo D-C,
> Hi,
>
> > > Die entsprechenden Reste müssten dann bei den Quadraten
> > > von mod7
> > > bei [mm]1^2[/mm] und [mm]6^2[/mm]
> >
> >
> >
> > > sowie bei mod 11
> > > bei [mm]5^2[/mm] und [mm]6^2[/mm]
> >
>
> > Das stimmt nicht: [mm]5^{2}=25 \equiv 3 \not= 8 \ \left(11\right)[/mm]
>
> Achso, ich hab hier die 3 zu Grunde gelegt, ein Rest 8
> kommt dann hier wohl nicht vor....
Das heißt dann, daß die Kongruenz [mm]x^{2} \equiv 8 \ \left(77\right)[/mm] keine Lösung besitzt.
>
> > > Jetzt fehlt mir nur noch irgendwie der letzte
> > > Schluss, der mich zur Lösung bringt..
>
> Gruß
> D-C
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:35 Mi 23.09.2009 | | Autor: | D-C |
Hi,
> Das heißt dann, daß die Kongruenz [mm]x^{2} \equiv 8 \ \left(77\right)[/mm]
> keine Lösung besitzt.
Ok, das wäre dann also die Antwort zu der Aufgabe?
D.h. immer wenn in mindestens einem der beiden modulo (hier 7 und 11) kein passender Rest zu finden ist, gibt es auch keine Lösung!?
Im anderen Fall, wären dann alle die gefundenen Reste die Lösungen?
Gruß
D-C
|
|
|
| |
|
Hallo D-C,
> Hi,
>
> > Das heißt dann, daß die Kongruenz [mm]x^{2} \equiv 8 \ \left(77\right)[/mm]
> > keine Lösung besitzt.
>
>
> Ok, das wäre dann also die Antwort zu der Aufgabe?
Ja.
>
> D.h. immer wenn in mindestens einem der beiden modulo (hier
> 7 und 11) kein passender Rest zu finden ist, gibt es auch
> keine Lösung!?
>
> Im anderen Fall, wären dann alle die gefundenen Reste die
> Lösungen?
Die gefundenen Reste bilden ein Kongruenzsystem (hier mit 7 und 11)
[mm]x \equiv a \ \left(7\right)[/mm]
[mm]x \equiv b \ \left(11\right)[/mm]
deren Lösungen mit dem ![[]](/images/popup.gif) chinesischen Restsatz ermittelt werden können.
Natürlich mußt Du das für alle möglichen Reste machen.
>
> Gruß
>
> D-C
>
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:15 Mi 23.09.2009 | | Autor: | D-C |
Ok, dann erstmal danke für die Hilfe : )
Stimmt, wenn es hier passende Reste gegeben hätte, kann man dann den chinesischen Restsatz anwenden, da Teilerfremdheit ja gegeben ist..
Mal sehen, ob ich morgen mal noch ein Beispiel finde, wo es passende Reste gibt.
Alles in allem ist wohl der letzte Weg, der einfachere wenn man ihn erstmal kennt : ) das andere ist ja mehr ein ausprobieren, was wohl nur bei kleinen Zahlen lohnt..
Gruß
D-C
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:29 Do 24.09.2009 | | Autor: | D-C |
Hi,
nochmal eine kurze Nachfrage ; )
> Die gefundenen Reste bilden ein Kongruenzsystem (hier mit 7
> und 11)
>
> [mm]x \equiv a \ \left(7\right)[/mm]
>
> [mm]x \equiv b \ \left(11\right)[/mm]
>
> deren Lösungen mit dem
> chinesischen Restsatz
> ermittelt werden können.
>
> Natürlich mußt Du das für alle möglichen Reste machen.
Also für a setze ich alle passenden Reste aus mod 7 ein
und bei b entsprechen alle aus mod 11.
Es kann ja aber auch passieren, dass ich mehrere Reste habe
also z.b.
x [mm] \equiv [/mm] 1 mod 7
x [mm] \equiv [/mm] 6 mod 7
x [mm] \equiv [/mm] 8 mod 11
7 wäre ja dann von 7 nicht teilerfremd und daher ließe sich
der chinesische Restsatz erstmal nicht anwenden. Folglich
müsste ich also in dem Fall, wo mehrere Reste existieren, dann
das System noch soweit umstellen, bis ich den Satz anwenden kann,
oder ist mein Ansatz falsch!?
Gruß
D-C
|
|
|
| |
|
Hallo D-C,
> Hi,
>
> nochmal eine kurze Nachfrage ; )
>
> > Die gefundenen Reste bilden ein Kongruenzsystem (hier mit 7
> > und 11)
> >
> > [mm]x \equiv a \ \left(7\right)[/mm]
> >
> > [mm]x \equiv b \ \left(11\right)[/mm]
> >
> > deren Lösungen mit dem
> > chinesischen Restsatz
> > ermittelt werden können.
> >
> > Natürlich mußt Du das für alle möglichen Reste machen.
>
> Also für a setze ich alle passenden Reste aus mod 7 ein
> und bei b entsprechen alle aus mod 11.
>
Hier mußt jeden Rest aus mod 7 mit jedem Rest aus mod 11 kombinieren.
> Es kann ja aber auch passieren, dass ich mehrere Reste
> habe
>
> also z.b.
>
> x [mm]\equiv[/mm] 1 mod 7
> x [mm]\equiv[/mm] 6 mod 7
> x [mm]\equiv[/mm] 8 mod 11
>
> 7 wäre ja dann von 7 nicht teilerfremd und daher ließe
> sich
> der chinesische Restsatz erstmal nicht anwenden. Folglich
> müsste ich also in dem Fall, wo mehrere Reste existieren,
> dann
> das System noch soweit umstellen, bis ich den Satz anwenden
> kann,
> oder ist mein Ansatz falsch!?
Wenn Du mehrere Reste hast, hast Du dementsprechend
viele Kongruenzsysteme zu lösen.
1. Kongruenzsystem:
[mm]x \equiv 1 \ \operatorname{mod} \ 7[/mm]
[mm]x \equiv 8 \ \operatorname{mod} \ 11[/mm]
2. Kongruenzsystem:
[mm]x \equiv 6 \ \operatorname{mod} \ 7[/mm]
[mm]x \equiv 8 \ \operatorname{mod} \ 11[/mm]
>
>
> Gruß
>
> D-C
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:17 Do 24.09.2009 | | Autor: | D-C |
Ah ok, das "teilt" sich also auf..
Gruß
D-C
|
|
|
|
