lineare Kongruenz lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Lösen Sie (falls möglich) die folgende lineare Kongruenz:
a) [mm] 21x\equiv [/mm] 6mod48
... |
Hallo,
ich weiß nicht genau, wie ich so eine Kongruenz löse und wäre froh wenn mir da jemand helfen könnte.
Also erstmal müssten ja, damit es überhaupt eine Lösung gibt, 21 und 6 teilerfremd sein, oder? Das wäre ja schonmal der Fall.
Und wenn ich mich nicht täusche folgt doch aus obiger Kongruenz:
[mm] \exists [/mm] y [mm] \in \IZ [/mm] : 21x+48y=6
Ist das soweit richtig? Falls ja, wie kann ich weiter machen?
Danke schonmal für Antworten!
Lieben Gruß
vom Congo
|
|
| |
|
Hallo Congo,
> Lösen Sie (falls möglich) die folgende lineare
> Kongruenz:
>
> a) [mm]21x\equiv[/mm] 6mod48
>
> ich weiß nicht genau, wie ich so eine Kongruenz löse und
> wäre froh wenn mir da jemand helfen könnte.
> Also erstmal müssten ja, damit es überhaupt eine Lösung
> gibt, 21 und 6 teilerfremd sein, oder? Das wäre ja
> schonmal der Fall.
Oh, keineswegs. 21,6 und 48 sind alle durch 3 teilbar.
Deswegen reduziert man die Äquivalenz erstmal auf
[mm] 7x\equiv 2\mod{16}
[/mm]
> Und wenn ich mich nicht täusche folgt doch aus obiger
> Kongruenz:
>
> [mm]\exists[/mm] y [mm]\in \IZ[/mm] : 21x+48y=6
bzw. dann eben 7x+16y=2
> Ist das soweit richtig? Falls ja, wie kann ich weiter
> machen?
Mit dem ![[]](/images/popup.gif) erweiterten euklidischen Algorithmus. Ein Beispiel und weiteres findest Du hier.
(Die Lösung lautet übrigens 14, aber versuche unbedingt, sie auch rechnerisch zu ermitteln!)
Grüße
reverend
|
|
|
| |
|
Hallo, ich bins nochmal.
Und wie siehts dann mit folgender Kongruenz aus?
10x [mm] \equiv [/mm] 4 mod 20
Die habe ich dann noch wie du mir oben gesagt hast reduziert auf:
5x [mm] \equiv [/mm] 2 mod 10
Aber da ja der ggT von 5 und 10 nicht eins ist und ich die Kongruenz nicht weiter reduzieren kann, komme ich ja auf kein Inverses von 5 mod 10 oder? Oder habe ich hier einen Denkfehler?
Danke schonmal für Antworten und Gruß
vom congo
|
|
|
| |
|
> Hallo, ich bins nochmal.
>
> Und wie siehts dann mit folgender Kongruenz aus?
>
> 10x [mm]\equiv[/mm] 4 mod 20
>
> Die habe ich dann noch wie du mir oben gesagt hast
> reduziert auf:
>
> 5x [mm]\equiv[/mm] 2 mod 10
>
> Aber da ja der ggT von 5 und 10 nicht eins ist und ich die
> Kongruenz nicht weiter reduzieren kann, komme ich ja auf
> kein Inverses von 5 mod 10 oder? Oder habe ich hier einen
> Denkfehler?
Doch, doch, stimmt schon, die Gleichung ist nicht lösbar.
Kannst du sonst auch einfach daran sehen, dass "mod 10" bei einer natürlichen Zahl immer die letzte Ziffer gibt. Und ein Vielfaches von 5, das an letzter Stelle eine 2 hat?^^
> Danke schonmal für Antworten und Gruß
> vom congo
MfG
Schadowmaster
|
|
|
| |
|
Hallo c.h.,
kleine Ergänzung:
eine lineare Kongruenz [mm]a\cdot{}x \ \equiv \ b \ \operatorname{mod}(m)[/mm] ist genau dann lösbar, wenn [mm]\operatorname{ggT}(a,m) \ \mid \ b[/mm]
Hier hast du [mm]10\cdot{}x \ \equiv \ 4 \ \operatorname{mod}(20)[/mm]
Und [mm]\operatorname{ggT}(10,20)=10[/mm], aber [mm]10 \ \nmid \ 4[/mm]
Also ist die Kongruenz nicht lösbar.
Gruß
schachuzipus
|
|
|
|
