Kongruenzrechnung Korrekt? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:29 Do 16.04.2009 | | Autor: | Cannae |
| Aufgabe | | 120x - 39 [mm] \equiv [/mm] 9 mod 88 |
Hi Leute,
ich habe die Aufgabe berechnet und würde gerne Eure Meinung wissen.
Ich bin vorgegange wie es mir schachuzipus, felixf und leduart bereits gezeigt haben.
die -39 rüber
wir erhalten: 120x [mm] \equiv [/mm] 48 mod 88
berechnen: 32x [mm] \equiv [/mm] 48 mod 88
ggT(32,88) = 8 und 8|48
Kongruenz ist also lösbar und es gibt 8 modulo 88 inkongruente Lösungen der Kongruenz.
Es ist 48 = 6 * 8
Ergeben sich:
32x [mm] \equiv [/mm] 48 mod 6 = 2x [mm] \equiv [/mm] 0 mod 6
32x [mm] \equiv [/mm] 48 mod 8 = 0x [mm] \equiv [/mm] 0 mod 8 [mm] \Rightarrow [/mm] reduntante Kongruenz
Soweit richtig?
Danke und Gruß
Stefan Beike
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:40 Do 16.04.2009 | | Autor: | abakus |
> 120x - 39 [mm]\equiv[/mm] 9 mod 88
> Hi Leute,
>
> ich habe die Aufgabe berechnet und würde gerne Eure Meinung
> wissen.
> Ich bin vorgegange wie es mir schachuzipus, felixf und
> leduart bereits gezeigt haben.
>
> die -39 rüber
> wir erhalten: 120x [mm]\equiv[/mm] 48 mod 88
>
> berechnen: 32x [mm]\equiv[/mm] 48 mod 88
Beidseitige Division durch 16 ergibt
(unter Berücksichtigung, dass ggT(16,88)=8)
2x[mm]\equiv[/mm] 3 mod [mm] \bruch{88}{8}
[/mm]
2x[mm]\equiv[/mm] 3 mod 11
rechts kann 11 addiert werden:
2x[mm]\equiv[/mm] 14 mod 11
(durch 2 teilen; Modul bleibt, da ggt(2,11)=1)
x[mm]\equiv[/mm] 7 mod 11
Lösungen sind also alle x=7+11k [mm] (k\in [/mm] Z)
Gruß Abakus
>
> ggT(32,88) = 8 und 8|48
>
> Kongruenz ist also lösbar und es gibt 8 modulo 88
> inkongruente Lösungen der Kongruenz.
>
> Es ist 48 = 6 * 8
>
> Ergeben sich:
>
> 32x [mm]\equiv[/mm] 48 mod 6 = 2x [mm]\equiv[/mm] 0 mod 6
> 32x [mm]\equiv[/mm] 48 mod 8 = 0x [mm]\equiv[/mm] 0 mod 8 [mm]\Rightarrow[/mm]
> reduntante Kongruenz
>
> Soweit richtig?
>
> Danke und Gruß
>
> Stefan Beike
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:49 Do 16.04.2009 | | Autor: | Cannae |
Danke.
warum dividierst Du durch 16?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:00 Do 16.04.2009 | | Autor: | abakus |
> Danke.
>
> warum dividierst Du durch 16?
Um mit einfacherem Zahlenmatrial arbeiten zu können (und weil 32 und 48 eben durch 16 teilbar sind).
Die verwendete Rechenregel lautet:
"Aus ac [mm] \equiv [/mm] bc mod m und ggT(m,c)=d folgt a [mm] \equiv [/mm] b mod [mm] \bruch{m}{d} [/mm] "
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:06 Do 16.04.2009 | | Autor: | Cannae |
danke.
ok die formel hat mir gefehlt. Habe nur noch eine Frage:
warum darfst Du am Ende auf die 3 mod 11 addieren?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:18 Do 16.04.2009 | | Autor: | abakus |
> danke.
> ok die formel hat mir gefehlt. Habe nur noch eine Frage:
>
> warum darfst Du am Ende auf die 3 mod 11 addieren?
Da fehlt dir offensichtlich die nächste Formel.
Aus [mm] a\equiv [/mm] b mod m und [mm] c\equiv [/mm] d mod m folgt [mm] a+c\equiv [/mm] b+d mod m .
Hier gilt konkret
[mm] 2x\equiv [/mm] 3 mod 11
und
0 [mm] \equiv [/mm] 11 mod 11 (0 und 11 lassen bei Teilung durch 11 den gleichen Rest)
Beide Kongruenzen werden nach o.g. Regel addiert.
Hier kann man allerdings auch damit argumentieren, dass die Kongruenzrelation eine Äquivalenzlelation (und damit insbesondere transitiv) ist .
Aus 2x [mm] \equiv [/mm] 3 mod 11 und [mm] 3\equiv [/mm] 14 mod 11 folgt 2x [mm] \equiv [/mm] 14 mod 11.
Wurden diese grundlegenden Dinge bei euch an der Uni nicht gelehrt? Lehrplanstoff ist so etwas zwar auch in Sachsen nicht, aber im Korrespondenzzirkel Mathematik für begabte Schüler vermitteln wir so etwas schon in Klasse 7.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:33 Do 16.04.2009 | | Autor: | Cannae |
Danke abakus.
Es handelt sich um FH und ein begabter Matheschüler war ich auch nie :)
Algebra ist mein letzter Schein. Die anderen habe ich alle mit 1 bestanden.
Ich verstehe gerade deshalb nicht warum mir Algebra soviel Probleme bereitet. Ich außerdem Bachelor of Science Informatik und nicht Mathematics.
Danke für Deine Hilfe. Noch 2 Tage lernen und ich kann auch die Kongruenzgleichungen.
Gruß
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:35 Do 16.04.2009 | | Autor: | Cannae |
> > danke.
> > ok die formel hat mir gefehlt. Habe nur noch eine
> Frage:
> >
> > warum darfst Du am Ende auf die 3 mod 11 addieren?
> Da fehlt dir offensichtlich die nächste Formel.
> Aus [mm]a\equiv[/mm] b mod m und [mm]c\equiv[/mm] d mod m folgt [mm]a+c\equiv[/mm]
> b+d mod m .
> Hier gilt konkret
> [mm]2x\equiv[/mm] 3 mod 11
> und
> 0 [mm]\equiv[/mm] 11 mod 11 (0 und 11 lassen bei Teilung durch 11
> den gleichen Rest)
> Beide Kongruenzen werden nach o.g. Regel addiert.
> Hier kann man allerdings auch damit argumentieren, dass
> die Kongruenzrelation eine Äquivalenzlelation (und damit
> insbesondere transitiv) ist .
> Aus 2x [mm]\equiv[/mm] 3 mod 11 und [mm]3\equiv[/mm] 14 mod 11 folgt 2x
> [mm]\equiv[/mm] 14 mod 11.
ich verstehe leider nicht wie du auf 0 [mm] \equiv [/mm] 11 mod 11 gekommen bist wenn c [mm] \equiv [/mm] d mod m ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:40 Do 16.04.2009 | | Autor: | abakus |
> > > danke.
> > > ok die formel hat mir gefehlt. Habe nur noch eine
> > Frage:
> > >
> > > warum darfst Du am Ende auf die 3 mod 11 addieren?
> > Da fehlt dir offensichtlich die nächste Formel.
> > Aus [mm]a\equiv[/mm] b mod m und [mm]c\equiv[/mm] d mod m folgt [mm]a+c\equiv[/mm]
> > b+d mod m .
> > Hier gilt konkret
> > [mm]2x\equiv[/mm] 3 mod 11
> > und
> > 0 [mm]\equiv[/mm] 11 mod 11 (0 und 11 lassen bei Teilung durch 11
> > den gleichen Rest)
> > Beide Kongruenzen werden nach o.g. Regel addiert.
> > Hier kann man allerdings auch damit argumentieren, dass
> > die Kongruenzrelation eine Äquivalenzlelation (und damit
> > insbesondere transitiv) ist .
> > Aus 2x [mm]\equiv[/mm] 3 mod 11 und [mm]3\equiv[/mm] 14 mod 11 folgt 2x
> > [mm]\equiv[/mm] 14 mod 11.
>
> ich verstehe leider nicht wie du auf 0 [mm]\equiv[/mm] 11 mod 11
> gekommen bist wenn c [mm]\equiv[/mm] d mod m ist?
Hallo,
0=0*11 plus Rest 0
11=1*11 plus Rest 0
0 und 11 lassen also den gleichen Rest bei Teilung durch 11 (nämlich den Rest 0)..
Der Fachbegriff für "restegleich bei Teilung durch 11" ist
"kongruent nach dem Modul 11".
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:43 Do 16.04.2009 | | Autor: | Cannae |
Sry habe die Frage falsch gestellt.
Ich hätte für die Werte in der Formel c [mm] \equiv [/mm] d mod m die Werte 16 [mm] \equiv [/mm] 8 mod 11 eingetragen. Aus diesem Kontext verstehe ich nicht wie man auf 0 [mm] \equiv [/mm] 11 mod 11
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:56 Do 16.04.2009 | | Autor: | abakus |
> Sry habe die Frage falsch gestellt.
>
> Ich hätte für die Werte in der Formel c [mm]\equiv[/mm] d mod m die
> Werte 16 [mm]\equiv[/mm] 8 mod 11 eingetragen. Aus diesem Kontext
Man kommt nicht "aus diesem Kontext" auf 0 [mm]\equiv[/mm] 11 mod 11 .
Die Aussage 0 [mm]\equiv[/mm] 11 [mm] \equiv [/mm] 22 [mm] \equiv 33\equiv... [/mm] mod 11 ist einfach eine grundlegende.
Die Formulierung [mm] a\equiv [/mm] b mod m lässt sich auf verschiedene Weise defiunieren:
- a und b sind restegleich bei Teilung durch m (bzw. gehören der selben Restklasse an)
- Es gilt a= [mm] q_1*m+r [/mm] und [mm] b=q_2*m+r [/mm] (q jeweils ganze Zahlen)
- Die Differenz aus a und b ist durch m teilbar.
Die Kongruenz 0 [mm]\equiv[/mm] 11 mod 11 lässt sich auf jede dieser 3 Arten erklären.
Gruß Abakus
> verstehe ich nicht wie man auf 0 [mm]\equiv[/mm] 11 mod 11
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:13 Do 16.04.2009 | | Autor: | Cannae |
Das heist du versuchst nach Möglichkeit eine Kongruenz mit mod 11 zu finden auf die eine der drei Bedingungen zutrifft?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:25 Do 16.04.2009 | | Autor: | abakus |
>
> Das heist du versuchst nach Möglichkeit eine Kongruenz mit
> mod 11 zu finden auf die eine der drei Bedingungen
> zutrifft?
Es treffen alle 3 Bedingungen zu.
Und ich versuche von den vielen Kongruenzen eine zu finden, die die weitere Rechnung vereinfacht.
[mm] 2x\equiv [/mm] 3 mod 11 kann ich nicht auf beiden Seiten durch 2 teilen. Deshalb ersetze ich 3 durch eine zu 3 kongruente Zahl, die durch 2 teilbar (und möglichst klein) ist.
Ich hätte auch 3 durch -8 ersetzen können und aus 2x [mm] \equiv [/mm] -8 mod 11 auf x [mm] \equiv [/mm] -4 [mm] \equiv [/mm] 7 mod 11 kommen können.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:01 Do 16.04.2009 | | Autor: | Cannae |
Bedeutet weitere Mögliche Werte für 3 sind:
2x [mm] \equiv [/mm] 14 mod 11
2x [mm] \equiv [/mm] 20 mod 11 warum erhalte ich für 3=20 noch nicht die richtige Lösung? Wie würde ich weiter machen, wenn ich x [mm] \equiv [/mm] 10 mod 11 habe?
Gruß
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:07 Do 16.04.2009 | | Autor: | abakus |
>
> Bedeutet weitere Mögliche Werte für 3 sind:
>
> 2x [mm]\equiv[/mm] 14 mod 11
> 2x [mm]\equiv[/mm] 20 mod 11 warum erhalte ich für 3=20 noch nicht
Nein! 14+11 ist 25.
Die Zahlen 3, 14, 25, 36, 47, ... , auch -8, -19, -30, -41 , ...
lassen alle den Rest 3 bei Teilung durch 11.
Die Zahl 20 lässt hingegen den Rest 9, ist also nicht kongruent zu 3 nach dem Modul 11.
Gruß Abakus
> die richtige Lösung? Wie würde ich weiter machen, wenn ich
> x [mm]\equiv[/mm] 10 mod 11 habe?
>
> Gruß
> Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:17 Do 16.04.2009 | | Autor: | Cannae |
Jetzt ist der Groschen gefallen!
Danke
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:02 Do 16.04.2009 | | Autor: | Cannae |
| Aufgabe | | 28x - 38 [mm] \equiv [/mm] 193 mod 35 |
Diese Aufgabe habe ich bereits in einem anderen Topic gestellt.
ich hole die 38 rüber:
28x [mm] \equiv [/mm] 231 mod 35
führe das erste mod durch:
28x [mm] \equiv [/mm] 21 mod 35
nun sehe ich:
ac [mm] \equiv [/mm] bc mod m und ggT(m,c)=d folgt a [mm] \equiv [/mm] b mod m/d
für c = 7
ggT(35,7)=7
m=35
also habe ich:
28x [mm] \equiv [/mm] 21 mod 5
mod ausführen:
3x [mm] \equiv [/mm] 1 mod 5 (im anderen Topic war die Aufgabe damit beendet)
Ich würde aber jetzt versuchen die 3 vor dem x zu entfernen.
Ich ersetze die 1 durch 6:
3x [mm] \equiv [/mm] 6 mod 5 /:3
x [mm] \equiv [/mm] 2 mod 5
Richtig?
|
|
|
| |
|
Hallo Stefan,
> 28x - 38 [mm]\equiv[/mm] 193 mod 35
> Diese Aufgabe habe ich bereits in einem anderen Topic
> gestellt.
>
> ich hole die 38 rüber:
>
> 28x [mm]\equiv[/mm] 231 mod 35
>
> führe das erste mod durch:
>
> 28x [mm]\equiv[/mm] 21 mod 35 ![[ok]](/images/smileys/ok.gif "[ok]")
>
> nun sehe ich:
> ac [mm]\equiv[/mm] bc mod m und ggT(m,c)=d folgt a [mm]\equiv[/mm] b mod m/d
>
> für c = 7
> ggT(35,7)=7
> m=35
>
> also habe ich:
>
> 28x [mm]\equiv[/mm] 21 mod 5
Hmm, da steht doch [mm] $\red{7}\cdot{}4x\equiv\red{7}\cdot{}3 [/mm] \ [mm] \mod [/mm] 35$
Also mit der Kürzungsregel [mm] $4x\equiv [/mm] 3 \ [mm] \mod [/mm] 5$
was zum selben Ergebnis führt ...
In dem anderen thread war ich glaube ich auch beteiligt und hatte den Modul [mm] $35=5\cdot{}7$ [/mm] geschrieben und die beiden "Teilkongruenzen" betrachtet, von denen diejenige, die [mm] $\mod [/mm] 7$ ist, redundant ist, die andere [mm] $28x\equiv [/mm] 21 \ [mm] \mod [/mm] 5$ reduziert sich zu deinem Ergebnis [mm] $3x\equiv [/mm] 1 \ [mm] \mod [/mm] 5$
Wenn du's mit der Kürzungsregel machst, wie beschrieben, kommt das etwas andere Teilergebnis heraus, was aber zum selben Endergebnis führt ...
>
> mod ausführen:
>
> 3x [mm]\equiv[/mm] 1 mod 5 (im anderen Topic war die Aufgabe damit
> beendet)
>
> Ich würde aber jetzt versuchen die 3 vor dem x zu
> entfernen.
> Ich ersetze die 1 durch 6:
>
> 3x [mm]\equiv[/mm] 6 mod 5 /:3
> x [mm]\equiv[/mm] 2 mod 5
>
> Richtig?
Jo
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Do 16.04.2009 | | Autor: | Cannae |
Danke. Das war mir da noch nicht bewusst :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:25 Do 16.04.2009 | | Autor: | abakus |
> 28x - 38 [mm]\equiv[/mm] 193 mod 35
> Diese Aufgabe habe ich bereits in einem anderen Topic
> gestellt.
>
> ich hole die 38 rüber:
>
> 28x [mm]\equiv[/mm] 231 mod 35
>
> führe das erste mod durch:
>
> 28x [mm]\equiv[/mm] 21 mod 35
>
> nun sehe ich:
> ac [mm]\equiv[/mm] bc mod m und ggT(m,c)=d folgt a [mm]\equiv[/mm] b mod m/d
>
> für c = 7
> ggT(35,7)=7
> m=35
>
> also habe ich:
>
> 28x [mm]\equiv[/mm] 21 mod 5
>
> mod ausführen:
>
> 3x [mm]\equiv[/mm] 1 mod 5 (im anderen Topic war die Aufgabe damit
> beendet)
>
> Ich würde aber jetzt versuchen die 3 vor dem x zu
> entfernen.
> Ich ersetze die 1 durch 6:
>
> 3x [mm]\equiv[/mm] 6 mod 5 /:3
> x [mm]\equiv[/mm] 2 mod 5
>
> Richtig?
Ich bin stolz auf Dich! 
Gruß Abakus
|
|
|
|
