Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:33 Sa 09.01.2010 | | Autor: | Unk |
| Aufgabe | | Zeigen Sie: [mm] \forall [/mm] a [mm] \in \mathbb{Z} [/mm] gilt [mm] a^{193}\equiv [/mm] a mod 195. |
Hallo,
ich habe die Behauptung zunächst mit dem Satz von Euler gezeigt, was auch funktioniert, nur ein Problem beinhaltet: Nach dem Satz von Euler gilt die Behauptung dann nur für ggT(a, 195)=1, ich soll es ja aber für alle ganzen Zahlen zeigen.
Wie kann man es besser machen?
|
|
| |
|
Hallo Unk,
Euler-Fermat ist schon gut, sofern Dir folgendes klar ist:
[mm] a^{193}\equiv a\mod{195}\quad \gdw \quad a^{192}\equiv 1\mod{\bruch{195}{ggT(a,195)}}
[/mm]
Dass [mm]195=3*5*13[/mm] und damit [mm] \varphi(195)=(3-1)(5-1)(13-1)=96 [/mm] hast Du ja offenbar schon herausgefunden.
Versuch doch mal a=75 mit der Umformung oben, dann siehst Du sicher, was da passiert. Dann brauchst Du noch eine allgemeine Herleitung...
lg
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:03 Sa 09.01.2010 | | Autor: | Unk |
> Hallo Unk,
>
> Euler-Fermat ist schon gut, sofern Dir folgendes klar ist:
>
> [mm]a^{193}\equiv a\mod{195}\quad \gdw \quad a^{192}\equiv 1\mod{\bruch{195}{ggT(a,195)}}[/mm]
>
> Dass [mm]195=3*5*13[/mm] und damit [mm]\varphi(195)=(3-1)(5-1)(13-1)=96[/mm]
> hast Du ja offenbar schon herausgefunden.
>
> Versuch doch mal a=75 mit der Umformung oben, dann siehst
> Du sicher, was da passiert. Dann brauchst Du noch eine
> allgemeine Herleitung...
>
> lg
> reverend
Naja in dem Fall hätte ich dann rechts eine Primzahl, also modulo 13. Und dann wieder nach Euler [mm] a^p\equiv [/mm] a mod n, falls (a, n)=1.
Was aber wenn 1<(a, 195)<195, z.B. 3, dann habe ich ja kein modulo einer Primzahl und kann das ganze wieder nicht anwenden. Kann ich es noch theoretisch verallgemeiern oder muss ich alle übrig bleibenden Fälle einzeln berechnen?
|
|
|
| |
|
So auf dem Weg ins Bett nochmal hallo...
Na, dann nimm halt ein allgemeines a mit ggT(a,195)=3.
Dann wird aus Deiner Äquivalenz doch [mm] a^{192}\equiv 1\mod{65},
[/mm]
und Du weißt sicher, dass ggT(a,65)=1 ist. Dann musst Du nur noch zeigen, dass [mm] kgV(\varphi(65),192)=192 [/mm] ist, also 192 ein Vielfaches von [mm] \varphi(65).
[/mm]
Das kannst Du doch leicht verallgemeinern, ohne jeden Fall einzeln zu untersuchen.
Allerdings erfüllen die Primteiler von 195 schon einige wenige Sonderbedingungen, ohne die die Aufgabe nicht funktionieren würde. Mit 1001=7*11*13 würde das z.B. nicht klappen. Wieso eigentlich nicht?
Gute Nacht,
reverend
|
|
|
|
