Kongruenzgleichung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:02 So 08.04.2012 | | Autor: | tagg |
| Aufgabe | | Gegeben sei [mm] a^{80} \equiv [/mm] 1 (mod 561). Bestimmen Sie a! |
Hallo und Frohe Ostern!
Ich habe bald eine mündliche Prüfung und bin bei meinen Vorbereitungen auf die o.g. Frage gestoßen, die der Prof. des Öfteren zu stellen scheint. Ich habe leider keine gute Idee, wie ich an so etwas herangehen könnte.
Ich weiß, dass 561 = 3*11*17 und [mm] \phi(561)=320 [/mm] ist. Des Weiteren gilt 80|320.
Ich kann mir nicht vorstellen, dass der Prof. die triviale Lösung a=1 erwartet. Ich denke, er will etwas hören, das mit Primitivwurzeln zu tun hat...? Nach Lagrange KÖNNTE es ja eine Untergruppe von [mm] \IZ_{561}^{\*} [/mm] geben, die die Ordnung 80 hat. Aus dieser Untergruppe müsste ich doch dann einfach ein a bestimmen, das ganz U erzeugt, also <a> = U.
Nur... wie geht das? :)
Danke für eure Hilfe!!
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Du solltest erstmal die Lösungen von [mm] a^{80}=1 [/mm] mod m für m=3,11 und 17 bestimmen.
Und dann wird es viel einfacher als du denkst...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:23 So 08.04.2012 | | Autor: | tagg |
also ich habe mal bissl gerechnet:
m=3: [mm] \phi(3)=2|80 [/mm] und a=2 ist PW mod 3
m=11: [mm] \phi(11)=10|80 [/mm] und a=2 ist PW mod 11 [mm] (2^{5}\equiv [/mm] -1)
m=17: [mm] \phi(17)=16|80, [/mm] aber a=2 ist diesmal keine PW, weil [mm] 2^{8} \equiv [/mm] 1 mod 17. Wär ja aber trotzdem nicht schlimm, löst ja trotzdem die Gleichung, oder?
Insgesamt habe ich also für alle m=2,11,17 eine Lösung a=2 gefunden. Nach dem Chinesischen Restsatz könnte ich doch jetzt schließen, dass 2 auch Lösung für das Ausgangsproblem ist, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:38 So 08.04.2012 | | Autor: | abakus |
> also ich habe mal bissl gerechnet:
>
> m=3: [mm]\phi(3)=2|80[/mm] und a=2 ist PW mod 3
>
> m=11: [mm]\phi(11)=10|80[/mm] und a=2 ist PW mod 11 [mm](2^{5}\equiv[/mm]
> -1)
>
> m=17: [mm]\phi(17)=16|80,[/mm] aber a=2 ist diesmal keine PW, weil
> [mm]2^{8} \equiv[/mm] 1 mod 17. Wär ja aber trotzdem nicht schlimm,
> löst ja trotzdem die Gleichung, oder?
>
> Insgesamt habe ich also für alle m=2,11,17 eine Lösung
> a=2 gefunden. Nach dem Chinesischen Restsatz könnte ich
> doch jetzt schließen, dass 2 auch Lösung für das
> Ausgangsproblem ist, oder?
Kann man. Allerdings glaube ich, dass du alle Lösungen a finden sollst.
[mm]2^{80}\equiv 1 mod 3[/mm] wird z.B. nicht nur von a=2, sondern von allen nicht durch 3 teilbaren Zahlen a erfüllt.
Kommt man nicht mit dem kleinen Fermat weiter?
Für alle nicht durch 3 teilbaren Zahlen a gilt [mm]a^2\equiv 1 mod 3[/mm] und demzufolge auch [mm](a^2)^{40}\equiv 1 mod 3[/mm].
Für alle nicht durch 11 teilbaren Zahlen a gilt [mm]a^{10}\equiv 1 mod 11[/mm] und demzufolge auch [mm](a^{10})^{8}\equiv 1 mod 11[/mm].
Für alle nicht durch 17 teilbaren Zahlen a gilt [mm]a^{16}\equiv 1 mod 17[/mm] und demzufolge auch [mm](a^{16})^{5}\equiv 1 mod 11[/mm].
Lösung müssten also alle Zahlen a sein, die weder durch 3 noch durch 11 noch durch 17 teilbar sind.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:50 So 08.04.2012 | | Autor: | tagg |
ok, das klingt ziemlich einleuchtend.. da fragt man sich, warum man da nicht selber drauf kommt :)
vielen dank!!
|
|
|
|
