Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:27 Fr 21.12.2012 | | Autor: | MattiJo |
| Aufgabe | 2. Löse die Kongruenzen
(a) [mm] x^{23} \equiv [/mm] 141 mod 210
(b) [mm] x^{96} \equiv [/mm] 456 mod 1001. |
Hallo,
ich beschäftige mich gerade mit der (a), komm aber nicht so recht weiter...
141 und 210 sind beide durch 3 teilbar, hierdurch kommt man zu
1412 [mm] \equiv [/mm] 141 mod 210
Aber wie kann auf alle Lösungen kommen?
|
|
| |
|
Hallo MattiJo,
> 2. Löse die Kongruenzen
> (a) [mm]x^{23} \equiv[/mm] 141 mod 210
> (b) [mm]x^{96} \equiv[/mm] 456 mod 1001.
> Hallo,
>
> ich beschäftige mich gerade mit der (a), komm aber nicht
> so recht weiter...
> 141 und 210 sind beide durch 3 teilbar, hierdurch kommt
> man zu
> 1412 [mm]\equiv[/mm] 141 mod 210
Wie das? Diese Äquivalenz stimmt nicht.
> Aber wie kann auf alle Lösungen kommen?
Am sichersten geht das durch simultane Kongruenzen. Es ist 210=2*3*5*7.
Daher gilt also [mm] x^{23}\equiv 1\mod{2}, \;x^{23}\equiv 0\mod{3}, \;x^{23}\equiv 1\mod{5} [/mm] und [mm] \;x^{23}\equiv 1\mod{7}. [/mm] Alle diese Kongruenzen sind eindeutig lösbar, es wird also auch nur eine Lösung [mm] \mod{210} [/mm] geben.
Grüße
reverend
|
|
|
| |
|
Hallo nochmal,
die Aufgabe b) birgt einige Tücken.
> 2. Löse die Kongruenzen
> (a) [mm]x^{23} \equiv[/mm] 141 mod 210
> (b) [mm]x^{96} \equiv[/mm] 456 mod 1001.
Auch hier: 1001=7*11*13, also
[mm] x^{96}\equiv 1\mod{7}
[/mm]
[mm] x^{96}\equiv 5\mod{11}
[/mm]
[mm] x^{96}\equiv 1\mod{13}
[/mm]
Nun ist das gemeine daran, dass die erste Kongruenz für alle x gilt, die nicht durch 7 teilbar sind, entsprechend auch die letzte Kongruenz für alle nicht durch 13 teilbaren x. (warum?)
Zum Modul 11 sieht es etwas besser aus, da gibt es nur zwei Lösungen.
Die Lösungsmenge ist jedenfalls ziemlich "groß" und man muss sich gut überlegen, wie man sie angibt.
Grüße
reverend
|
|
|
|
