Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:23 Sa 22.01.2011 | | Autor: | Bodo0686 |
| Aufgabe | | [mm] 1235X\equiv [/mm] -79 mod 1683 |
Hallo,
kann man hier auf den ersten Blick sehen, ob diese Kongruenz lösbar ist? Wenn ja, woran kann ich dies erkennen?
Könnt ihr mir hier weiterhelfen?
Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:47 Sa 22.01.2011 | | Autor: | abakus |
> [mm]1235X\equiv[/mm] -79 mod 1683
> Hallo,
>
> kann man hier auf den ersten Blick sehen, ob diese
> Kongruenz lösbar ist? Wenn ja, woran kann ich dies
> erkennen?
>
> Könnt ihr mir hier weiterhelfen?
>
> Grüße
Hallo,
[mm] ax\equiv [/mm] b mod m ist nur lösbar, wenn ggT(a,m)|b .
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:03 Sa 22.01.2011 | | Autor: | Bodo0686 |
Hallo,
also hätte ich
ggT(1235,1683)=1 -> 1|-79 damit Kongruenz lösbar, richtig?
Grüße
|
|
|
| |
|
Hallo Bodo,
> Hallo,
>
> also hätte ich
>
> ggT(1235,1683)=1 ![[ok]](/images/smileys/ok.gif "[ok]") -> 1|-79 damit Kongruenz lösbar,
> richtig?
Ja!
>
> Grüße
LG
schachuzipus
|
|
|
| |
|
Ok,
ich soll nun 1235X [mm] \equiv [/mm] -79 mod 1683 mit dem chinesischen Restsatz zwar die betragsmäßig kleinste ganzzahlige Lösung mod 1683.
ggT(1235,1683)=1 -> 1|-79 ist also lösbar.
PFZ: 1683 = [mm] 3^2*11*17
[/mm]
->
1235 X [mm] \equiv [/mm] -79 mod [mm] 3^2
[/mm]
1235 X [mm] \equiv [/mm] -79 mod 11
1235 X [mm] \equiv [/mm] -79 mod 17
So bis hierhin dürfte doch alles noch richtig sein, oder?
Jetzt muss ich ja obige 3 Kongruenzen auf die Form [mm] aX\equiv [/mm] b mod m bringen.
Wenn ich als Bsp habe [mm] 7X\equiv [/mm] 1 mod 17
dann kann ich doch immer vielfache von 17 zu 1 hinzuaddieren.
1+17=18
18+17=35 ->(7X=35 -> x=5)
-> [mm] X\equiv [/mm] 5 mod 17
Das kann ich doch nun genauso machen, oder? Allerdings habe ich das schon mit Excel (54 Datensätze) probiert jedoch kommen dort überall Kommazahlen heraus...
Könnt ihr mir helfen?
Danke
|
|
|
| |
|
Hi,
ich hab es auch nur mit Excel gemacht.
Du suchst ja praktisch eine ganzzahlige Lösung für das System
$x = 1 + 9a$
$3x = 9 + 11b$
$11x = 6 + 17c$
Ich habe in der 1. Spalte sozusagen das x durchgezählt von 1 bis 1000 und in die Spalten 2 bis 4 dann die drei Gleichungen nach a, b und c aufgelöst und in der fünften Spalte dann die Überprüfung, ob das ganze Zahlen sind. Dann entfällt so etwas wie "mit Kombinationen testen".
Bei x=883 findet man dann ganzzahlige a,b,c.
Ob es eine sinnvolle Rechnung gibt, weiß ich nicht (abgesehen von der Zerlegung in ein System von Kongruenzen, die du schon gemacht hast).
lg weightgainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:39 Sa 22.01.2011 | | Autor: | Bodo0686 |
Hallo
> Hi,
>
> ich hab es auch nur mit Excel gemacht.
>
> Du suchst ja praktisch eine ganzzahlige Lösung für das
> System
>
> [mm]x = 1 + 9a[/mm]
>
> [mm]3x = 9 + 11b[/mm]
>
> [mm]11x = 6 + 17c[/mm]
Wie kommst du hier auf diese Lösungen?
>
> Ich habe in der 1. Spalte sozusagen das x durchgezählt von
> 1 bis 1000 und in die Spalten 2 bis 4 dann die drei
> Gleichungen nach a, b und c aufgelöst und in der fünften
> Spalte dann die Überprüfung, ob das ganze Zahlen sind.
> Dann entfällt so etwas wie "mit Kombinationen testen".
> Bei x=883 findet man dann ganzzahlige a,b,c.
>
> Ob es eine sinnvolle Rechnung gibt, weiß ich nicht
> (abgesehen von der Zerlegung in ein System von Kongruenzen,
> die du schon gemacht hast).
>
> lg weightgainer
lg
|
|
|
| |
|
Hey,
du hattest die Gleichungen schon durch deine Kongruenzen da stehen:
$1235 X [mm] \equiv [/mm] -79\ mod\ 9$
$1235 X [mm] \equiv [/mm] -79\ mod\ 11 $
$1235 X [mm] \equiv-79\ [/mm] mod\ 17$
Ich hab auf der rechten Seite nur die -79 durch Addition von Vielfachen des Moduls in den "normalen" Bereich gebracht und auf der linken Seite die 1235 auch durch den Modul reduziert:
$-79 + 9*9 = 2$
$-79 + 8*11 = 9$
$-79 + 5*17 = 6$
$1235 = 9*137 + 2$
$1235 = 11*112 + 3$
$1235 = 17*72 + 11 $
Exemplarisch mit der letzten Kongruenz steht also da:
$1235X [mm] \equiv [/mm] -79\ mod\ 17$
[mm] $\gdw [/mm] (17*72+11)X [mm] \equiv [/mm] 6\ mod\ 17$
[mm] $\gdw [/mm] 17*72*X + 11X [mm] \equiv [/mm] 6\ mod\ 17$
[mm] $\gdw [/mm] 11X [mm] \equiv [/mm] 6\ mod\ 17$
Und das hab ich dann in eine Gleichung übersetzt, also 11x = 6 + 17c
lg weightgainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:03 Sa 22.01.2011 | | Autor: | Bodo0686 |
> Hey,
>
> du hattest die Gleichungen schon durch deine Kongruenzen da
> stehen:
>
> [mm]1235 X \equiv -79\ mod\ 9[/mm]
> [mm]1235 X \equiv -79\ mod\ 11[/mm]
> [mm]1235 X \equiv-79\ mod\ 17[/mm]
>
> Ich hab auf der rechten Seite nur die -79 durch Addition
> von Vielfachen des Moduls in den "normalen" Bereich
> gebracht und auf der linken Seite die 1235 auch durch den
> Modul reduziert:
>
> [mm]-79 + 9*9 = 2[/mm]
> [mm]-79 + 8*11 = 9[/mm]
> [mm]-79 + 5*17 = 6[/mm]
ok, bis hierhin kann ich dir folgen
> [mm]1235 = 9*137 + 2[/mm]
> [mm]1235 = 11*112 + 3[/mm]
> [mm]1235 = 17*72 + 11[/mm]
>
aber wie kommst du jetzt bspw. auf die entsprechenden Werte(137,112,72) und (2,3,11)?
> Exemplarisch mit der letzten Kongruenz steht also da:
>
> [mm]1235X \equiv -79\ mod\ 17[/mm]
>
> [mm]\gdw (17*72+11)X \equiv 6\ mod\ 17[/mm]
>
> [mm]\gdw 17*72*X + 11X \equiv 6\ mod\ 17[/mm]
>
> [mm]\gdw 11X \equiv 6\ mod\ 17[/mm]
Warum fällt hier 17*72*X weg?
>
> Und das hab ich dann in eine Gleichung übersetzt, also 11x
> = 6 + 17c
>
> lg weightgainer
lg
|
|
|
| |
|
> > Hey,
> >
> > du hattest die Gleichungen schon durch deine Kongruenzen da
> > stehen:
> >
> > [mm]1235 X \equiv -79\ mod\ 9[/mm]
> > [mm]1235 X \equiv -79\ mod\ 11[/mm]
>
> > [mm]1235 X \equiv-79\ mod\ 17[/mm]
> >
> > Ich hab auf der rechten Seite nur die -79 durch Addition
> > von Vielfachen des Moduls in den "normalen" Bereich
> > gebracht und auf der linken Seite die 1235 auch durch den
> > Modul reduziert:
> >
> > [mm]-79 + 9*9 = 2[/mm]
> > [mm]-79 + 8*11 = 9[/mm]
> > [mm]-79 + 5*17 = 6[/mm]
>
> ok, bis hierhin kann ich dir folgen
>
>
> > [mm]1235 = 9*137 + 2[/mm]
> > [mm]1235 = 11*112 + 3[/mm]
> > [mm]1235 = 17*72 + 11[/mm]
>
> >
>
> aber wie kommst du jetzt bspw. auf die entsprechenden
> Werte(137,112,72) und (2,3,11)?
Durch etwas, was du bestimmt seit der 5. Klasse schon wieder vergessen hast, weil man da die Division nicht mehr mit Rest macht, sondern mit Komma  .
Im Ernst: Du machst einfach eine Division mit Rest: 1235 : 9 = 137 R2
Also kannst du 1235 = 137*9 + 2 schreiben.
Sinn des Ganzen: Wenn du auf der linken Seite z.B. 9*x hast und du schaust das ganze modulo 9 an, dann kannst du für x einsetzen, was du willst, insgesamt ist das 0. Du kannst also insbesondere bei einer Multiplikation solche Zahlen auch reduzieren, indem du alle Vielfachen des Moduls rausrechnest.
Also wenn da jetzt sowas wie $13x [mm] \equiv [/mm] 5\ mod\ 9$ stünde, dann liefern dir 9 von den 13x keinen Beitrag, weil 9x modulo 9 genau 0 ergibt, also brauchst du links nur noch 4x anzuschauen.
Etwas klarer?
>
>
> > Exemplarisch mit der letzten Kongruenz steht also da:
> >
> > [mm]1235X \equiv -79\ mod\ 17[/mm]
> >
> > [mm]\gdw (17*72+11)X \equiv 6\ mod\ 17[/mm]
> >
> > [mm]\gdw 17*72*X + 11X \equiv 6\ mod\ 17[/mm]
> >
> > [mm]\gdw 11X \equiv 6\ mod\ 17[/mm]
>
> Warum fällt hier 17*72*X weg?
siehe Erklärung oben
>
> >
> > Und das hab ich dann in eine Gleichung übersetzt, also 11x
> > = 6 + 17c
> >
> > lg weightgainer
> lg
lg weightgainer
|
|
|
| |
|
Hallo,
ok diese Schritte habe ich soweit durchgerechnet, nur bei I) habe ich etwas anderes:
[mm] 1235X\equiv [/mm] -79 mod 9
[mm] \gdw (9*137+2)*X\equiv [/mm] 2 mod 9
[mm] \gdw [/mm] 9*137X + 2X [mm] \equiv [/mm] 2 mod 9
[mm] \gdw [/mm] 2X [mm] \equiv [/mm] 2 mod 9
Hier kann ich doch dann 2:2 rechnen, oder? also [mm] x\equiv [/mm] 1 mod 9 ( da 2 und 9 teilerfremd)
Das könnte ich aber dann doch auch bei der zweiten machen, oder?
[mm] 3X\equiv9mod11 [/mm] -> [mm] X\equiv [/mm] 3 mod 11 (da 3 und 11 tf und 9 und 11 teilerfremd)
Wie müsste ich jetzt hier weitermachen? Ich brauche doch alle drei Kongruenzen in [mm] "X\equiv [/mm] b mod m" Form...
Grüße
|
|
|
| |
|
Hi,
aber genau das hatte ich doch für die erste Kongruenz auch - ich hatte das ja nicht mehr ausführlich hergeleitet, aber wenn du dir meine Gleichung anschaust, die ich in der Tabellenkalkulation verwendet habe, kannst du es sehen.
lg weightgainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Di 25.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:27 Mo 24.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
