Gruppe < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei n [mm] \in \IZ [/mm] und [mm] {\IZ}/{n\IZ} [/mm] die additive Gruppe der Kongruenzklassen modulo n.
i) Zeige: Wenn [mm] 1\le [/mm] a < n und a und n sind nicht teilerfremd, dann existiert ein 1 [mm] \le [/mm] b < n so, dass a*b=0 mod n
Folgere, dass [mm] \bar{a} [/mm] kein multiplikativ Inverses in [mm] {\IZ}/{n\IZ} [/mm] haben kann. |
Ich dachte mir, dass wenn wir wissen, dass n und a nicht teilerfremd sind, so kann man schreiben n=v*d und a=f*d wobei d ein gemeinsamer Teiler der beiden ist und v,f,d [mm] \in \IZ. [/mm] Wenn wir zeigen wollen, dass ab=0 mod n ist das äquivalent zu
ab=q*n für ein q [mm] \in \IZ
[/mm]
das Obere eingesetzt ergibt:
f*d*b=q*v*d
das d kann man auf beiden Seiten kürzen so erhalten wir
f*b=q*v. Nun könnte man das ganze nach b auflösen, und müsste zeigen, dass es so ein b gibt.
Bringt mir das was? Ich weiss leider nicht weiter....
über Anregungen würde ich mich sehr freuen 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:42 Sa 18.03.2017 | | Autor: | Ladon |
Teil 1: $a $ und $n$ nicht teilerfremd folgt es existiert ein $d>1 $, s.d. $d|a$ und $d|n$, d.h. es gibt [mm] $1\le [/mm] x,y <n $, s.d. $a=dx$ und $n=dy$, was zu $ay=dxy$ und $nx=dxy$ äquivalent ist. Es folgt [mm] $ay=nx\gdw [/mm] ay-nx=0$. Das bedeutet aber: es gibt ein [mm] $1\le [/mm] y <n$ mit [mm] $(a+n\IZ)(y+\IZ)=0$.
[/mm]
Wie kommt man darauf? Betrachte verschiedene Beispiele, z.B. [mm] $\IZ/9\IZ [/mm] $ und $a = 6$ mit gemeinsamen Teiler $3$. Dann schau, was das kgV ist.
Zu dem 2. Teil: Nutze Ring- und Idealtheorie. Zeige hat $a$ ein multiplicatives Inverses, d.h. [mm] $a+n\IZ\in (\IZ/n\IZ)^\times [/mm] $, so sind a und n teilerfremd, d.h. $ggT(a,n)=1$.
[mm] $a+n\IZ\in (\IZ/n\IZ)^\times [/mm] $, dann existiert ein [mm] $1\le [/mm] b <n$ mit [mm] $(a+n\IZ)(b+n\IZ)=ab+n\IZ=1+n\IZ [/mm] $, d.h. es existieren [mm] $x,y\in\IZ$, [/mm] s.d. $ab+nx=1+ny [mm] \gdw [/mm] ab+n(x-y)=1$. Daraus folgt $(a,n)=(a)+(n)=(1)$, was $ggT(a,n)=1$ impliziert.
|
|
|
| |
|
> Teil 1: [mm]a[/mm] und [mm]n[/mm] nicht teilerfremd folgt es existiert ein
> [mm]d>1 [/mm], s.d. [mm]d|a[/mm] und [mm]d|n[/mm], d.h. es gibt [mm]1\le x,y
> [mm]a=dx[/mm] und [mm]n=dy[/mm], was zu [mm]ay=dxy[/mm] und [mm]nx=dxy[/mm] äquivalent ist. Es
> folgt [mm]ay=nx\gdw ay-nx=0[/mm]. Das bedeutet aber: es gibt ein
> [mm]1\le y
>
Meinst du [mm](a+n\IZ)(y+n\IZ)=0[/mm]?
Dann würde ich es verstehen.
> Wie kommt man darauf? Betrachte verschiedene Beispiele,
> z.B. [mm]\IZ/9\IZ[/mm] und [mm]a = 6[/mm] mit gemeinsamen Teiler [mm]3[/mm]. Dann
> schau, was das kgV ist.
>
> Zu dem 2. Teil: Nutze Ring- und Idealtheorie. Zeige hat [mm]a[/mm]
> ein multiplicatives Inverses, d.h. [mm]a+n\IZ\in (\IZ/n\IZ)^\times [/mm],
> so sind a und n teilerfremd, d.h. [mm]ggT(a,n)=1[/mm].
> [mm]a+n\IZ\in (\IZ/n\IZ)^\times [/mm], dann existiert ein [mm]1\le b
> mit [mm](a+n\IZ)(b+n\IZ)=ab+n\IZ=1+n\IZ [/mm], d.h. es existieren
> [mm]x,y\in\IZ[/mm], s.d. [mm]ab+nx=1+ny \gdw ab+n(x-y)=1[/mm]. Daraus folgt
> [mm](a,n)=(a)+(n)=(1)[/mm], was [mm]ggT(a,n)=1[/mm] impliziert.
Ah super. Das heißt meine Aussage ist ja die Negation von dem was du gerade bewiesen hast. Nicht teilerfremd--> kein multiplikativ Inverses.
Super, vielen Dank dir!
|
|
|
| |
|
> > Teil 1: [mm]a[/mm] und [mm]n[/mm] nicht teilerfremd folgt es existiert ein
> > [mm]d>1 [/mm], s.d. [mm]d|a[/mm] und [mm]d|n[/mm], d.h. es gibt [mm]1\le x,y
> > [mm]a=dx[/mm] und [mm]n=dy[/mm], was zu [mm]ay=dxy[/mm] und [mm]nx=dxy[/mm] äquivalent ist. Es
> > folgt [mm]ay=nx\gdw ay-nx=0[/mm]. Das bedeutet aber: es gibt ein
> > [mm]1\le y
> >
> Meinst du [mm](a+n\IZ)(y+n\IZ)=0[/mm]?
> Dann würde ich es verstehen.
Beziehungsweise könnte man nicht schon auf [mm] ay=nx [/mm] modulo n anwenden, dann steht da ja gleich ay=0 was zu zeigen war?
> > Wie kommt man darauf? Betrachte verschiedene Beispiele,
> > z.B. [mm]\IZ/9\IZ[/mm] und [mm]a = 6[/mm] mit gemeinsamen Teiler [mm]3[/mm]. Dann
> > schau, was das kgV ist.
> >
> > Zu dem 2. Teil: Nutze Ring- und Idealtheorie. Zeige hat [mm]a[/mm]
> > ein multiplicatives Inverses, d.h. [mm]a+n\IZ\in (\IZ/n\IZ)^\times [/mm],
> > so sind a und n teilerfremd, d.h. [mm]ggT(a,n)=1[/mm].
> > [mm]a+n\IZ\in (\IZ/n\IZ)^\times [/mm], dann existiert ein [mm]1\le b
> > mit [mm](a+n\IZ)(b+n\IZ)=ab+n\IZ=1+n\IZ [/mm], d.h. es existieren
> > [mm]x,y\in\IZ[/mm], s.d. [mm]ab+nx=1+ny \gdw ab+n(x-y)=1[/mm]. Daraus folgt
> > [mm](a,n)=(a)+(n)=(1)[/mm], was [mm]ggT(a,n)=1[/mm] impliziert.
> Ah super. Das heißt meine Aussage ist ja die Negation von
> dem was du gerade bewiesen hast. Nicht teilerfremd--> kein
> multiplikativ Inverses.
> Super, vielen Dank dir!
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:51 Sa 18.03.2017 | | Autor: | Ladon |
> > > Teil 1: [mm]a[/mm] und [mm]n[/mm] nicht teilerfremd folgt es existiert ein
> > > [mm]d>1 [/mm], s.d. [mm]d|a[/mm] und [mm]d|n[/mm], d.h. es gibt [mm]1\le x,y
> > > [mm]a=dx[/mm] und [mm]n=dy[/mm], was zu [mm]ay=dxy[/mm] und [mm]nx=dxy[/mm] äquivalent ist. Es
> > > folgt [mm]ay=nx\gdw ay-nx=0[/mm]. Das bedeutet aber: es gibt ein
> > > [mm]1\le y
> > >
> > Meinst du [mm](a+n\IZ)(y+n\IZ)=0[/mm]?
> > Dann würde ich es verstehen.
> Beziehungsweise könnte man nicht schon auf [mm]ay=nx[/mm] modulo n
> anwenden, dann steht da ja gleich ay=0 was zu zeigen war?
Klar. Warum nicht? 
> > > Wie kommt man darauf? Betrachte verschiedene
> Beispiele,
> > > z.B. [mm]\IZ/9\IZ[/mm] und [mm]a = 6[/mm] mit gemeinsamen Teiler [mm]3[/mm]. Dann
> > > schau, was das kgV ist.
> > >
> > > Zu dem 2. Teil: Nutze Ring- und Idealtheorie. Zeige hat [mm]a[/mm]
> > > ein multiplicatives Inverses, d.h. [mm]a+n\IZ\in (\IZ/n\IZ)^\times [/mm],
> > > so sind a und n teilerfremd, d.h. [mm]ggT(a,n)=1[/mm].
> > > [mm]a+n\IZ\in (\IZ/n\IZ)^\times [/mm], dann existiert ein
> [mm]1\le b
> > > mit [mm](a+n\IZ)(b+n\IZ)=ab+n\IZ=1+n\IZ [/mm], d.h. es existieren
> > > [mm]x,y\in\IZ[/mm], s.d. [mm]ab+nx=1+ny \gdw ab+n(x-y)=1[/mm]. Daraus folgt
> > > [mm](a,n)=(a)+(n)=(1)[/mm], was [mm]ggT(a,n)=1[/mm] impliziert.
> > Ah super. Das heißt meine Aussage ist ja die Negation von
> > dem was du gerade bewiesen hast. Nicht teilerfremd--> kein
> > multiplikativ Inverses.
> > Super, vielen Dank dir!
> >
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:50 Sa 18.03.2017 | | Autor: | Ladon |
> > Teil 1: [mm]a[/mm] und [mm]n[/mm] nicht teilerfremd folgt es existiert ein
> > [mm]d>1 [/mm], s.d. [mm]d|a[/mm] und [mm]d|n[/mm], d.h. es gibt [mm]1\le x,y
> > [mm]a=dx[/mm] und [mm]n=dy[/mm], was zu [mm]ay=dxy[/mm] und [mm]nx=dxy[/mm] äquivalent ist. Es
> > folgt [mm]ay=nx\gdw ay-nx=0[/mm]. Das bedeutet aber: es gibt ein
> > [mm]1\le y
> >
> Meinst du [mm](a+n\IZ)(y+n\IZ)=0[/mm]?
> Dann würde ich es verstehen.
Ich meine [mm](a+n\IZ)(y+n\IZ)=0+n\IZ[/mm]
|
|
|
|
