Kongruenz lösen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe Probleme bei einer Aufgabe, bei der es um Kongruenzen geht.
Bestimmen Sie durch Faktorisierung Phi(2537) und lösen sie dann die Kongruenz [mm] 1949*d\equiv [/mm] 1 mod Phi(2537).
Mit phi ist die eulersche Phi-Funktion gemeint. Ich habe bereits herausgefunden, dass 2537=59*43 ist. Wie bringe ich das jetzt aber in eine Kongruenz, auf die ich den chinesischen Restsatz anwenden kann?
Da brauche ich doch so etwas hier:
[mm] d\equiv [/mm] irgendwas mod irgendwas
[mm] d\equiv [/mm] irgendwas mod irgendwas
[mm] d\equiv [/mm] irgendwas mod irgendwas
...
59 und 43 sind Primzahlen, ich kann also hier die Phi-Funktion anwenden und bekomme dann Phi(2537)=Phi(59)*Phi(43)=58*42.
Das sind doch aber keine teilerfremden Zahlen. Da kann ich doch den Restsatz gar nicht mehr anwenden, oder? Kann mir jemand helfen?
Viele Grüße
Daniel
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:55 Do 01.12.2005 | | Autor: | felixf |
> ich habe Probleme bei einer Aufgabe, bei der es um
> Kongruenzen geht.
>
> Bestimmen Sie durch Faktorisierung Phi(2537) und lösen sie
> dann die Kongruenz [mm]1949*d\equiv[/mm] 1 mod Phi(2537).
>
> Mit phi ist die eulersche Phi-Funktion gemeint. Ich habe
> bereits herausgefunden, dass 2537=59*43 ist. Wie bringe ich
> das jetzt aber in eine Kongruenz, auf die ich den
> chinesischen Restsatz anwenden kann?
>
> Da brauche ich doch so etwas hier:
> [mm]d\equiv[/mm] irgendwas mod irgendwas
> [mm]d\equiv[/mm] irgendwas mod irgendwas
> [mm]d\equiv[/mm] irgendwas mod irgendwas
> ...
>
> 59 und 43 sind Primzahlen, ich kann also hier die
> Phi-Funktion anwenden und bekomme dann
> Phi(2537)=Phi(59)*Phi(43)=58*42.
>
> Das sind doch aber keine teilerfremden Zahlen. Da kann ich
> doch den Restsatz gar nicht mehr anwenden, oder? Kann mir
> jemand helfen?
Dann faktorisier doch mal 58*42 bzw. schreib es als Produkt von teilerfremden Zahlen. Dann kannst du den Chinesischen Restsatz sehr wohl anwenden. 
HTH Felix
|
|
|
| |
|
Hallo,
okay dann bekomme ich 58*42=29*2*7*3*2
Dummerweise sind jetzt aber 2 und 2 nicht teilerfremd. Und was mache ich jetzt? Hat da einer ne Idee?
VG Daniel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:04 Fr 02.12.2005 | | Autor: | felixf |
> Hallo,
>
> okay dann bekomme ich 58*42=29*2*7*3*2
>
> Dummerweise sind jetzt aber 2 und 2 nicht teilerfremd. Und
> was mache ich jetzt? Hat da einer ne Idee?
Na, du klammerst halt 29 * (2 * 2) * 7 * 3 = 29 * 4 * 7 * 3. Und 29, 4, 7 und 3 sind paarweise teilerfremd.
HTH Felix
|
|
|
|
