Lösbarkeit von Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:46 Fr 14.01.2011 | | Autor: | Bodo0686 |
| Aufgabe | Entscheiden Sie über die Lösbarkeit der folgenden Kongruenzen und bestimmen Sie ggf. die Lösungsanzahl und sämtliche Lösungen
a) [mm] 34X\equiv [/mm] 3 mod 42
b) 21X [mm] \equiv [/mm] -6 mod 33 |
Hallo,
Ich habe beide Aufgaben mal gelöst und poste nun hier meine Lösungen. Es wäre lieb, wenn jemand da mal kurz drüber schauen könnte! Danke!
a) [mm] 34X\equiv [/mm] 3 mod 42
a=34, c=3, m=42
Es gilt: ggt(34,42)=2
Bilde nun: [mm] a'=\frac{a}{(a,m)}, c'=\frac{c}{(a,m)}, m'=\frac{m}{(a,m)}
[/mm]
Hier: [mm] a'=\frac{34}{2}=17, c'=\frac{3}{2}=1.5, m'=\frac{42}{2}=21
[/mm]
Bestimme nun die Lösung der Kongruenz
[mm] 17X\equiv [/mm] 1.5 mod 21 durch ausprobieren der Zahlen 0,...,20
-> ggT(a,m)=ggT(17,21)=1
Ich würde sagen, dass dies nicht Lösbar ist, da Kongruenzen nur ganzzahlige Lösungen besitzt, aber c'=1.5 ist, funktioniert dies nicht.
[mm] b)21X\equiv-6 [/mm] mod 33
ggT(21,33)=3
a'=7, c'=-2, m'=11
Löse nun: [mm] 7X\equiv [/mm] -2 mod 11 durch ausprobieren der Zahlen {0,...,10}
ggT(7,11)=1
X 1 2 3 4 5 6 7 8 9 10
7xmod11 7 3 10 6 2 9 5 1 6 4
X=3
Welche der Zahlen 3+t*11 liegen nun in der Zahlenmenge {0,...,32}
t 0 1 2 3
3+t*11 3 14 25 36 (36 fällt weg, da außerhalb der Zahlemenge)
Also sind 3, 14 ,25 die -6 mod 33 inkongruenten Lösungen.
Ist dies so korrekt?
|
|
| |
|
Hallo Bodo0686,
> Entscheiden Sie über die Lösbarkeit der folgenden
> Kongruenzen und bestimmen Sie ggf. die Lösungsanzahl und
> sämtliche Lösungen
>
> a) [mm]34X\equiv[/mm] 3 mod 42
> b) 21X [mm]\equiv[/mm] -6 mod 33
> Hallo,
>
> Ich habe beide Aufgaben mal gelöst und poste nun hier
> meine Lösungen. Es wäre lieb, wenn jemand da mal kurz
> drüber schauen könnte! Danke!
>
> a) [mm]34X\equiv[/mm] 3 mod 42
>
> a=34, c=3, m=42
>
> Es gilt: ggt(34,42)=2
> Bilde nun: [mm]a'=\frac{a}{(a,m)}, c'=\frac{c}{(a,m)}, m'=\frac{m}{(a,m)}[/mm]
>
> Hier: [mm]a'=\frac{34}{2}=17, c'=\frac{3}{2}=1.5, m'=\frac{42}{2}=21[/mm]
Hier darfst Du nicht einfach durch 2 teilen.
Es gibt diesen Satz:![[]](/images/popup.gif) Lösbarkeit von Kongruenzen
>
> Bestimme nun die Lösung der Kongruenz
>
> [mm]17X\equiv[/mm] 1.5 mod 21 durch ausprobieren der Zahlen
> 0,...,20
> -> ggT(a,m)=ggT(17,21)=1
>
> Ich würde sagen, dass dies nicht Lösbar ist, da
> Kongruenzen nur ganzzahlige Lösungen besitzt, aber c'=1.5
> ist, funktioniert dies nicht.
>
> [mm]b)21X\equiv-6[/mm] mod 33
> ggT(21,33)=3
> a'=7, c'=-2, m'=11
>
> Löse nun: [mm]7X\equiv[/mm] -2 mod 11 durch ausprobieren der Zahlen
> {0,...,10}
> ggT(7,11)=1
>
> X 1 2 3 4 5 6 7 8 9 10
> 7xmod11 7 3 10 6 2 9 5 1 6 4
>
> X=3
Es muss hier X=6 sein.
Das kannst Du auch rechnerisch ermitteln.
Bestimme dazu das multiplikative Inverse zu 7 modulo 11.
>
> Welche der Zahlen 3+t*11 liegen nun in der Zahlenmenge
> {0,...,32}
>
> t 0 1 2 3
> 3+t*11 3 14 25 36 (36 fällt weg, da außerhalb der
> Zahlemenge)
>
> Also sind 3, 14 ,25 die -6 mod 33 inkongruenten
> Lösungen.
>
Das stimmt nicht. ![[notok]](/images/smileys/notok.gif "[notok]")
> Ist dies so korrekt?
Nein.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:17 Fr 14.01.2011 | | Autor: | Bodo0686 |
> Hallo Bodo0686,
>
> > Entscheiden Sie über die Lösbarkeit der folgenden
> > Kongruenzen und bestimmen Sie ggf. die Lösungsanzahl und
> > sämtliche Lösungen
> >
> > a) [mm]34X\equiv[/mm] 3 mod 42
> > b) 21X [mm]\equiv[/mm] -6 mod 33
> > Hallo,
> >
> > Ich habe beide Aufgaben mal gelöst und poste nun hier
> > meine Lösungen. Es wäre lieb, wenn jemand da mal kurz
> > drüber schauen könnte! Danke!
> >
> > a) [mm]34X\equiv[/mm] 3 mod 42
> >
> > a=34, c=3, m=42
> >
> > Es gilt: ggt(34,42)=2
> > Bilde nun: [mm]a'=\frac{a}{(a,m)}, c'=\frac{c}{(a,m)}, m'=\frac{m}{(a,m)}[/mm]
>
> >
> > Hier: [mm]a'=\frac{34}{2}=17, c'=\frac{3}{2}=1.5, m'=\frac{42}{2}=21[/mm]
>
>
> Hier darfst Du nicht einfach durch 2 teilen.
Ok fangen wir hier an:
also es muss gelten, dass hatte ich übersehen (a,m) | c
(a,m)=2 und c =3 -> 2|3 klappt nicht.
also ist Aufgabe so nicht lösbar?
Grüße
|
|
|
| |
|
Hallo Bodo0686,
> > Hallo Bodo0686,
> >
> > > Entscheiden Sie über die Lösbarkeit der folgenden
> > > Kongruenzen und bestimmen Sie ggf. die Lösungsanzahl und
> > > sämtliche Lösungen
> > >
> > > a) [mm]34X\equiv[/mm] 3 mod 42
> > > b) 21X [mm]\equiv[/mm] -6 mod 33
> > > Hallo,
> > >
> > > Ich habe beide Aufgaben mal gelöst und poste nun hier
> > > meine Lösungen. Es wäre lieb, wenn jemand da mal kurz
> > > drüber schauen könnte! Danke!
> > >
> > > a) [mm]34X\equiv[/mm] 3 mod 42
> > >
> > > a=34, c=3, m=42
> > >
> > > Es gilt: ggt(34,42)=2
> > > Bilde nun: [mm]a'=\frac{a}{(a,m)}, c'=\frac{c}{(a,m)}, m'=\frac{m}{(a,m)}[/mm]
>
> >
> > >
> > > Hier: [mm]a'=\frac{34}{2}=17, c'=\frac{3}{2}=1.5, m'=\frac{42}{2}=21[/mm]
>
> >
> >
> > Hier darfst Du nicht einfach durch 2 teilen.
>
> Ok fangen wir hier an:
>
> also es muss gelten, dass hatte ich übersehen (a,m) | c
> (a,m)=2 und c =3 -> 2|3 klappt nicht.
>
> also ist Aufgabe so nicht lösbar?
Ja.
> Grüße
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:41 Fr 14.01.2011 | | Autor: | Bodo0686 |
Ok, kommen wir zu b)
21 X [mm] \equiv [/mm] -6 mod 33
ggT(21,33)=3
Bedingung: (a,m)|c -> 3|6 ist so korrekt richtig? D.h. doch übersetzt, dass 3 die 6 teilt richtig?
Kann ich dann, [mm] a'=\frac{21}{3}=7 [/mm] rechnen, was aber sicherlich falsch ist, oder muss ich [mm] a'=\frac{21}{2}=10.5 [/mm] rechnen? (Da 6:3=2)
Grüße
|
|
|
| |
|
Hallo Bodo0686,
> Ok, kommen wir zu b)
>
> 21 X [mm]\equiv[/mm] -6 mod 33
> ggT(21,33)=3
>
> Bedingung: (a,m)|c -> 3|6 ist so korrekt richtig? D.h. doch
> übersetzt, dass 3 die 6 teilt richtig?
>
> Kann ich dann, [mm]a'=\frac{21}{3}=7[/mm] rechnen, was aber
> sicherlich falsch ist, oder muss ich [mm]a'=\frac{21}{2}=10.5[/mm]
> rechnen? (Da 6:3=2)
So, wie Du das in Deinem allerersten Post
in diesem Thread gemacht ist, ist es richtig.
Da 21, -6. 33 die Zahl 3 teilen kannst Du schreiben:
[mm]7 X \equiv -2 \ mod \ 11[/mm]
>
> Grüße
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:08 Fr 14.01.2011 | | Autor: | Bodo0686 |
Also, war meine erste Lösung (im ersten Post) so korrekt. Es war aber sozusagen falsch, weil die Bedingung nicht da stand. Richtig?
|
|
|
| |
|
Hallo Bodo0686,
> Also, war meine erste Lösung (im ersten Post) so korrekt.
> Es war aber sozusagen falsch, weil die Bedingung nicht da
> stand. Richtig?
Die Umformung zu
[mm]7X \equiv -2 \ \operatorname{mod} \ 33[/mm]
ist korrekt, jedoch die Lösung nicht.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:19 Fr 14.01.2011 | | Autor: | Bodo0686 |
7X [mm] \equiv [/mm] -2 mod 11
ggT(7,11)=1
Bestimme nun di eLösungen der kongruenz 7X [mm] \equiv [/mm] -2 mod 11 durch ausprobieren der Zahlen für 0,...,10 für X.
A=7X mod 11
X 1 2 3 4 5 6 7 8 9 10
A 7 3 10 6 2 9 5 1 6 4
Dies sind die berechneten Werte ich heraus habe.
Was muss ich denn jetzt hier überprüfen? Ich muss doch jetzt irgendwie auf den Rest von 7X [mm] \equiv [/mm] -2 mod 11 schließen (also auf die -2)???
|
|
|
| |
|
Hallo Bodo0686,
> 7X [mm]\equiv[/mm] -2 mod 11
> ggT(7,11)=1
>
> Bestimme nun di eLösungen der kongruenz 7X [mm]\equiv[/mm] -2 mod
> 11 durch ausprobieren der Zahlen für 0,...,10 für X.
>
> A=7X mod 11
>
> X 1 2 3 4 5 6 7 8 9 10
> A 7 3 10 6 2 9 5 1 6 4
>
> Dies sind die berechneten Werte ich heraus habe.
> Was muss ich denn jetzt hier überprüfen? Ich muss doch
> jetzt irgendwie auf den Rest von 7X [mm]\equiv[/mm] -2 mod 11
> schließen (also auf die -2)???
Da [mm]-2 \equiv 9 \ \operatorname{mod} \ 11[/mm] ist,
musst Du das jenige X herausfinden,
für das A den Wert 9 annimmt.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:35 Fr 14.01.2011 | | Autor: | Bodo0686 |
Also wäre das X=7
Aber verstehe jetzt nicht warum du dir
-2X [mm] \equiv9 [/mm] mod 11 anguckst. Wir haben doch 7X [mm] \equiv [/mm] -2 mod 11
Also betrachte ich mir immer die Differenz von meinem (a-m) und dieses ergebnis suche ich dann in meiner Tabelle, korrekt?
|
|
|
| |
|
Hallo Bodo0686,
> Also wäre das X=7
Rechne mal [mm]7*7 \ \operatorname{mod} \ 11[/mm]
>
> Aber verstehe jetzt nicht warum du dir
> -2X [mm]\equiv9[/mm] mod 11 anguckst. Wir haben doch 7X [mm]\equiv[/mm] -2
> mod 11
>
> Also betrachte ich mir immer die Differenz von meinem (a-m)
> und dieses ergebnis suche ich dann in meiner Tabelle,
> korrekt?
Wenn auf der rechten Seite der Konguenz eine negative Zahl steht,
dann addiere ich hier 11 dazu, damit die Zahl positiv wird.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:51 Fr 14.01.2011 | | Autor: | Bodo0686 |
> Hallo Bodo0686,
>
> > Also wäre das X=7
>
>
> Rechne mal [mm]7*7 \ \operatorname{mod} \ 11[/mm]
>
49 mod 11 Rest 5
>
> >
> > Aber verstehe jetzt nicht warum du dir
> > -2X [mm]\equiv9[/mm] mod 11 anguckst. Wir haben doch 7X [mm]\equiv[/mm]
> -2
> > mod 11
> >
> > Also betrachte ich mir immer die Differenz von meinem (a-m)
> > und dieses ergebnis suche ich dann in meiner Tabelle,
> > korrekt?
>
> Wenn auf der rechten Seite der Konguenz eine negative Zahl
> steht,
> dann addiere ich hier 11 dazu, damit die Zahl positiv
> wird.
[mm] 7X\equiv [/mm] -2 mod 11 (addieren +11)
[mm] 7X\equiv [/mm] 9 mod 11 (aber was passiert mit der 7´auf der linken Seite?
>
> Gruss
> MathePower
Grüße
|
|
|
| |
|
Hallo Bodo0686,
> > Hallo Bodo0686,
> >
> > > Also wäre das X=7
> >
> >
> > Rechne mal [mm]7*7 \ \operatorname{mod} \ 11[/mm]
> >
>
> 49 mod 11 Rest 5
>
Das heisst doch, daß X=7 keine Lösung ist.
> >
> > >
> > > Aber verstehe jetzt nicht warum du dir
> > > -2X [mm]\equiv9[/mm] mod 11 anguckst. Wir haben doch 7X
> [mm]\equiv[/mm]
> > -2
> > > mod 11
> > >
> > > Also betrachte ich mir immer die Differenz von meinem (a-m)
> > > und dieses ergebnis suche ich dann in meiner Tabelle,
> > > korrekt?
> >
> > Wenn auf der rechten Seite der Konguenz eine negative Zahl
> > steht,
> > dann addiere ich hier 11 dazu, damit die Zahl positiv
> > wird.
>
> [mm]7X\equiv[/mm] -2 mod 11 (addieren +11)
> [mm]7X\equiv[/mm] 9 mod 11 (aber was passiert mit der 7´auf der
> linken Seite?
>
Nun, wenn Du zu 7X die Zahl 11 addierst und
dies modulo 11 rechnest, dann steht da wiederum 7X.
>
> >
> > Gruss
> > MathePower
> Grüße
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:08 Fr 14.01.2011 | | Autor: | Bodo0686 |
> Hallo Bodo0686,
>
> > > Hallo Bodo0686,
> > >
> > > > Also wäre das X=7
> > >
> > >
> > > Rechne mal [mm]7*7 \ \operatorname{mod} \ 11[/mm]
> > >
> >
> > 49 mod 11 Rest 5
> >
>
>
> Das heisst doch, daß X=7 keine Lösung ist.
>
>
> > >
> > > >
> > > > Aber verstehe jetzt nicht warum du dir
> > > > -2X [mm]\equiv9[/mm] mod 11 anguckst. Wir haben doch 7X
> > [mm]\equiv[/mm]
> > > -2
> > > > mod 11
> > > >
> > > > Also betrachte ich mir immer die Differenz von meinem (a-m)
> > > > und dieses ergebnis suche ich dann in meiner Tabelle,
> > > > korrekt?
> > >
> > > Wenn auf der rechten Seite der Konguenz eine negative Zahl
> > > steht,
> > > dann addiere ich hier 11 dazu, damit die Zahl
> positiv
> > > wird.
> >
> > [mm]7X\equiv[/mm] -2 mod 11 (addieren +11)
> > [mm]7X\equiv[/mm] 9 mod 11 (aber was passiert mit der 7´auf der
> > linken Seite?
> >
>
>
> Nun, wenn Du zu 7X die Zahl 11 addierst und
> dies modulo 11 rechnest, dann steht da wiederum 7X.
>
Und wie kommst du dann auf die -2 auf der linken Seite???
Also müssen wir nun:
7X [mm] \equiv [/mm] 9 mod 11 berechnen???
Also wir gucken dann für [mm] x\in{0,...,10} [/mm] nach wo der Rest 9 herauskommt. Und das ist ja gerade bei X=6
>
> >
> > >
> > > Gruss
> > > MathePower
> > Grüße
>
>
> Gruss
> MathePower
Grüße
|
|
|
| |
|
Hallo Bodo0686,
> > Hallo Bodo0686,
> >
> > > > Hallo Bodo0686,
> > > >
> > > > > Also wäre das X=7
> > > >
> > > >
> > > > Rechne mal [mm]7*7 \ \operatorname{mod} \ 11[/mm]
> > > >
> > >
> > > 49 mod 11 Rest 5
> > >
> >
> >
> > Das heisst doch, daß X=7 keine Lösung ist.
> >
> >
> > > >
> > > > >
> > > > > Aber verstehe jetzt nicht warum du dir
> > > > > -2X [mm]\equiv9[/mm] mod 11 anguckst. Wir haben doch
> 7X
> > > [mm]\equiv[/mm]
> > > > -2
> > > > > mod 11
> > > > >
> > > > > Also betrachte ich mir immer die Differenz von meinem (a-m)
> > > > > und dieses ergebnis suche ich dann in meiner Tabelle,
> > > > > korrekt?
> > > >
> > > > Wenn auf der rechten Seite der Konguenz eine negative Zahl
> > > > steht,
> > > > dann addiere ich hier 11 dazu, damit die Zahl
> > positiv
> > > > wird.
> > >
> > > [mm]7X\equiv[/mm] -2 mod 11 (addieren +11)
> > > [mm]7X\equiv[/mm] 9 mod 11 (aber was passiert mit der 7´auf
> der
> > > linken Seite?
> > >
> >
> >
> > Nun, wenn Du zu 7X die Zahl 11 addierst und
> > dies modulo 11 rechnest, dann steht da wiederum 7X.
> >
>
> Und wie kommst du dann auf die -2 auf der linken Seite???
Die Ausgangsgleichung ist doch
[mm]21X \equiv \ -6 \ \operatorname{mod} \ 33[/mm]
Da 21, -6 , 33 durch 3 teilbar sind, folgt:
[mm]7X \equiv \ -2 \ \operatorname{mod} \ 11[/mm]
>
> Grüße
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:21 Fr 14.01.2011 | | Autor: | Bodo0686 |
und jetzt addierst du einfach 11 hinzu (die 11 von modulo)
Aus 7X [mm] \equiv [/mm] -2 mod 11 erhälst du [mm] 7X\equiv [/mm] 9 mod 11???
Und jetzt einfach ausrechnen?
Grüße
|
|
|
| |
|
Hallo Bodo,
> und jetzt addierst du einfach 11 hinzu (die 11 von modulo)
>
> Aus 7X [mm]\equiv[/mm] -2 mod 11 erhälst du [mm]7X\equiv[/mm] 9 mod 11??? ![[ok]](/images/smileys/ok.gif "[ok]")
Ja, es ist doch [mm]-2 \ \equiv \ 9 \ \ \operatorname{mod}(11)[/mm]
[mm]-2[/mm] und [mm]11[/mm] lassen doch bei Division durch [mm]11[/mm] denselben Rest.
[mm]\equiv[/mm] ist transitiv, damit ist also
[mm]7X \ \equiv \ -2 \ \ \operatorname{mod}(11)[/mm] und [mm]-2 \ \equiv \ 9 \ \ \operatorname{mod}(11) \ \ \Rightarrow \ \ [/mm] [mm]7X \ \equiv \ 9 \ \ \operatorname{mod}(11)[/mm]
>
> Und jetzt einfach ausrechnen?
Ja!
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:32 Fr 14.01.2011 | | Autor: | Bodo0686 |
7X [mm] \equiv [/mm] 9 mod 11
A= 7X mod 11
X 1 2 3 4 5 6 7 8 9 10
A 7 3 10 6 2 9 ---------
Also ist X=6 die Lösung.
Welche Zahlen 6+t*11 liegen in der Zahlenfolge {0,...,20}
B=6+t*11
t 0 1 2 3
B 6 18 -----
Also sind die Zahlen 6, 18 die -6 mod 33 inkongruenten Lösungen
Richtig?
|
|
|
| |
|
Hallo Bodo0686,
> 7X [mm]\equiv[/mm] 9 mod 11
>
> A= 7X mod 11
>
> X 1 2 3 4 5 6 7 8 9 10
> A 7 3 10 6 2 9 ---------
>
> Also ist X=6 die Lösung.
>
> Welche Zahlen 6+t*11 liegen in der Zahlenfolge {0,...,20}
>
> B=6+t*11
>
> t 0 1 2 3
> B 6 18 -----
>
> Also sind die Zahlen 6, 18 die -6 mod 33 inkongruenten
> Lösungen
>
> Richtig?
Lösungen sind 6, 17.
Gruss
MathePower
|
|
|
|
