Kleine Frage < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hey, ich hab mal ne Frage, also es gilt:
[mm] x\equiv [/mm] r(mod m) und [mm] x\equiv [/mm] s(mod n)
Zudem gelte ggT(r,m)=1 und ggT(s,n)=1
Hieraus soll folgen ggT(x,m*n)=1
Kann ich dies einfach daraus folgern, dass ich weiss, dass wenn ggT(a,m)=ggT(b,m)=1 daraus folgt: ggT(ab,m)=1. Bzw. muss ich dazu noch erwähnen, dass ich aus den obigen beiden Kongruenzen quasi r und s als gleich ansehen kann?
mfg
piccolo
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:07 Fr 22.10.2010 | | Autor: | abakus |
> Hey, ich hab mal ne Frage, also es gilt:
> [mm]x\equiv[/mm] r(mod m) und [mm]x\equiv[/mm] s(mod n)
> Zudem gelte ggT(r,m)=1 und ggT(s,n)=1
>
> Hieraus soll folgen ggT(x,m*n)=1
>
> Kann ich dies einfach daraus folgern, dass ich weiss, dass
> wenn ggT(a,m)=ggT(b,m)=1 daraus folgt: ggT(ab,m)=1. Bzw.
> muss ich dazu noch erwähnen, dass ich aus den obigen
> beiden Kongruenzen quasi r und s als gleich ansehen kann?
Nein, das kannst du nicht. Beispielsweise gilt 19 [mm] \equiv [/mm] 4 mod 5, aber 19 [mm] \equiv [/mm] 1 mod 6.
Ich würde mal folgendes versuchen:
Aus [mm]x\equiv[/mm] r(mod m) folgt x=a*m+r.
Aus [mm]x\equiv[/mm] s(mod n) folgt x= b*n+s.
Dann gilt z.B. ggT(x,m*n)=ggT(a*m+r,m*n). Dieser ggT kann schon mal NICHT m sein...
Gruß Abakus
>
> mfg
> piccolo
|
|
|
| |
|
> > Hey, ich hab mal ne Frage, also es gilt:
> > [mm]x\equiv[/mm] r(mod m) und [mm]x\equiv[/mm] s(mod n)
> > Zudem gelte ggT(r,m)=1 und ggT(s,n)=1
> >
> > Hieraus soll folgen ggT(x,m*n)=1
> >
> > Kann ich dies einfach daraus folgern, dass ich weiss, dass
> > wenn ggT(a,m)=ggT(b,m)=1 daraus folgt: ggT(ab,m)=1. Bzw.
> > muss ich dazu noch erwähnen, dass ich aus den obigen
> > beiden Kongruenzen quasi r und s als gleich ansehen kann?
> Nein, das kannst du nicht. Beispielsweise gilt 19 [mm]\equiv[/mm] 4
> mod 5, aber 19 [mm]\equiv[/mm] 1 mod 6.
> Ich würde mal folgendes versuchen:
> Aus [mm]x\equiv[/mm] r(mod m) folgt x=a*m+r.
> Aus [mm]x\equiv[/mm] s(mod n) folgt x= b*n+s.
> Dann gilt z.B. ggT(x,m*n)=ggT(a*m+r,m*n). Dieser ggT kann
Hey, also ich hab jetzt nochmal ein bisschen rumprobiert und hab mir folgendes überlegt, wie du ja schon sagtest:
Aus [mm]x\equiv[/mm] r(mod m) folgt x=a*m+r.
Zudem gilt: aus ggT(r,m)=1 folgt, das ganze Zahlen d und e existieren müssen, sodass gilt:
1=d*r+e*m Hier setze ich jetzt r=x-a*m ein und durch umformen erhalte ich dann:
1=d*x-m*(a*d+e) Dabei gilt jetzt, dass d und (a*d+e) ganze Zahlen sind und somit ist diese Gleichung äquivalent zu:
ggT(x,m)=1.
Analog zeige ich ggT(x,n)=1 Woraus dann insgesamt folgt: ggT(x,m*n)=1.
Ist das soweit korrekt?
mfg
piccolo
> schon mal NICHT m sein...
> Gruß Abakus
> >
> > mfg
> > piccolo
>
|
|
|
| |
|
Hallo piccolo,
ja, das ist korrekt und also eine mögliche Lösung.
Grüße
reverend
|
|
|
| |
|
alles klar, danke
mfg piccolo
|
|
|
|
