Frage modulo < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hey, ich hab gerad in nem Zahlentheoriebuch in einem Beweis folgendes gelesen:
Ausgangspunkt: [mm] 5^r\equiv -5^s(mod2^n)
[/mm]
Durch Division mit [mm] 5^s [/mm] soll sich dann folgendes ergeben:
[mm] 5^{r-s}\equiv -1(mod2^n)
[/mm]
Nun ist meine Frage, ob das so richtig ist, müsste nicht mit dem [mm] 2^n [/mm] hinten noch was passieren??
Zusätzlich hab ich nochmal ne Frage zur Ordnung eines Elements. Da steht z.B. in nem Beweis, dass gilt:
[mm] 5^{2^{n-2}}\equiv 1(mod2^n)
[/mm]
Nun wird gezeigt, dass dies auch gleich der Ordnung des Elements 5 entspricht, dazu muss ja gezeigt werden, dass [mm] 2^{n-2} [/mm] die kleinste Zahl ist, für die obiges gilt. In dem Buch haben sie es so gemacht, dass sie einfach für n dann (n-1) eingesetzt haben. Ist das so ausreichend, wenn man dann zeigt, dass die Kongruenz für diesen Fall dann nicht mehr gilt??
Mfg
piccolo
PS: Es werden jeweils die multiplikativen Gruppen modulo [mm] 2^n [/mm] betrachtet, die nur aus den relativ primen Elementen zu [mm] 2^n [/mm] bestehen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:51 Do 21.10.2010 | | Autor: | abakus |
> Hey, ich hab gerad in nem Zahlentheoriebuch in einem Beweis
> folgendes gelesen:
> Ausgangspunkt: [mm]5^r\equiv -5^s(mod2^n)[/mm]
> Durch Division mit
> [mm]5^s[/mm] soll sich dann folgendes ergeben:
> [mm]5^{r-s}\equiv -1(mod2^n)[/mm]
>
> Nun ist meine Frage, ob das so richtig ist, müsste nicht
> mit dem [mm]2^n[/mm] hinten noch was passieren??
Hallo,
es gilt folgender Satz:
Aus [mm] ac\equiv [/mm] bc mod m UND d=ggT(m,c) folgt
a [mm] \equiv [/mm] b mod [mm] \bruch{m}{d}.
[/mm]
Dieser Satz besagt, dass sich bei beidseitiger Division einer Kongruenz der Modul ändern kann (aber eben nur, wenn d -also der ggT des Moduls und des Divisors- nicht den Wert 1 annimmt).
Da 2 und 5 teilerfremd sind, passiert hier eben nichts.
Gruß Abakus
>
> Zusätzlich hab ich nochmal ne Frage zur Ordnung eines
> Elements. Da steht z.B. in nem Beweis, dass gilt:
> [mm]5^{2^{n-2}}\equiv 1(mod2^n)[/mm]
> Nun wird gezeigt, dass dies
> auch gleich der Ordnung des Elements 5 entspricht, dazu
> muss ja gezeigt werden, dass [mm]2^{n-2}[/mm] die kleinste Zahl ist,
> für die obiges gilt. In dem Buch haben sie es so gemacht,
> dass sie einfach für n dann (n-1) eingesetzt haben. Ist
> das so ausreichend, wenn man dann zeigt, dass die Kongruenz
> für diesen Fall dann nicht mehr gilt??
>
>
> Mfg
> piccolo
>
> PS: Es werden jeweils die multiplikativen Gruppen modulo
> [mm]2^n[/mm] betrachtet, die nur aus den relativ primen Elementen zu
> [mm]2^n[/mm] bestehen
|
|
|
| |
|
Hallo, kann mir evtl noch jemand bei diesem Problem eine Erklärung geben???
> > Zusätzlich hab ich nochmal ne Frage zur Ordnung eines
> > Elements. Da steht z.B. in nem Beweis, dass gilt:
> > [mm]5^{2^{n-2}}\equiv 1(mod2^n)[/mm]
> > Nun wird gezeigt, dass
> dies
> > auch gleich der Ordnung des Elements 5 entspricht, dazu
> > muss ja gezeigt werden, dass [mm]2^{n-2}[/mm] die kleinste Zahl ist,
> > für die obiges gilt. In dem Buch haben sie es so gemacht,
> > dass sie einfach für n dann (n-1) eingesetzt haben. Ist
> > das so ausreichend, wenn man dann zeigt, dass die Kongruenz
> > für diesen Fall dann nicht mehr gilt??
> >
> >
> > Mfg
> > piccolo
> >
> > PS: Es werden jeweils die multiplikativen Gruppen modulo
> > [mm]2^n[/mm] betrachtet, die nur aus den relativ primen Elementen zu
> > [mm]2^n[/mm] bestehen
>
mfg piccolo
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:53 Fr 22.10.2010 | | Autor: | abakus |
> Hallo, kann mir evtl noch jemand bei diesem Problem eine
> Erklärung geben???
Gegenfrage:
1) Wie kommst du darauf, dass sich am Modul [mm] 2^n [/mm] etwas ändern sollte?
2) Was hast du an der Antwort nicht verstehen können?
Wenn wir das nicht wissen, erhältst du vielleicht nur noch einmal die gleiche Antwort.
Den von mir zitiertzen Satz findest du auch hier:
http://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)#Rechenregeln
Gruß Abakus
>
> > > Zusätzlich hab ich nochmal ne Frage zur Ordnung eines
> > > Elements. Da steht z.B. in nem Beweis, dass gilt:
> > > [mm]5^{2^{n-2}}\equiv 1(mod2^n)[/mm]
> > > Nun wird gezeigt,
> dass
> > dies
> > > auch gleich der Ordnung des Elements 5 entspricht, dazu
> > > muss ja gezeigt werden, dass [mm]2^{n-2}[/mm] die kleinste Zahl ist,
> > > für die obiges gilt. In dem Buch haben sie es so gemacht,
> > > dass sie einfach für n dann (n-1) eingesetzt haben. Ist
> > > das so ausreichend, wenn man dann zeigt, dass die Kongruenz
> > > für diesen Fall dann nicht mehr gilt??
> > >
> > >
> > > Mfg
> > > piccolo
> > >
> > > PS: Es werden jeweils die multiplikativen Gruppen modulo
> > > [mm]2^n[/mm] betrachtet, die nur aus den relativ primen Elementen zu
> > > [mm]2^n[/mm] bestehen
> >
>
> mfg piccolo
|
|
|
| |
|
> > Hallo, kann mir evtl noch jemand bei diesem Problem eine
> > Erklärung geben???
> Gegenfrage:
> 1) Wie kommst du darauf, dass sich am Modul [mm]2^n[/mm] etwas
> ändern sollte?
> 2) Was hast du an der Antwort nicht verstehen können?
Deine Antwort habe ich verstanden, das ist mir jetzt auch klar, ich meinte jetzt auch das 2. Problem, was weiter unten im Text steht, wo es um die Ordnung geht. Das würde ich gerne noch nachvollziehen können. Deine Erklärung zu dem Problem vorher war echt super, das ist mir jetzt klar 
> Wenn wir das nicht wissen, erhältst du vielleicht nur
> noch einmal die gleiche Antwort.
> Den von mir zitiertzen Satz findest du auch hier:
>
> http://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)#Rechenregeln
> Gruß Abakus
> >
> > > > Zusätzlich hab ich nochmal ne Frage zur Ordnung eines
> > > > Elements. Da steht z.B. in nem Beweis, dass gilt:
> > > > [mm]5^{2^{n-2}}\equiv 1(mod2^n)[/mm]
> > > > Nun wird
> gezeigt,
> > dass
> > > dies
> > > > auch gleich der Ordnung des Elements 5 entspricht, dazu
> > > > muss ja gezeigt werden, dass [mm]2^{n-2}[/mm] die kleinste Zahl ist,
> > > > für die obiges gilt. In dem Buch haben sie es so gemacht,
> > > > dass sie einfach für n dann (n-1) eingesetzt haben. Ist
> > > > das so ausreichend, wenn man dann zeigt, dass die Kongruenz
> > > > für diesen Fall dann nicht mehr gilt??
> > > >
> > > >
> > > > Mfg
> > > > piccolo
> > > >
> > > > PS: Es werden jeweils die multiplikativen Gruppen modulo
> > > > [mm]2^n[/mm] betrachtet, die nur aus den relativ primen Elementen zu
> > > > [mm]2^n[/mm] bestehen
> > >
> >
> > mfg piccolo
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:33 Fr 22.10.2010 | | Autor: | moudi |
Hallo Piccolo
Gilt [mm] $x^n\equiv [/mm] 1 [mm] \mod [/mm] k$, so muss n ein Vielfaches der Ordnung von x Modulo k sein. Da in deinem Beispiel [mm] $2^{n-2}$ [/mm] statt n eine 2er-Potenz ist, muss man nur die naechst kleinere 2er-Potenz testen, also [mm] $2^{n-3}$. [/mm] Wenn also [mm] $5^{2^{n-3}}\not\equiv 1\mod 2^n$ [/mm] ist, dann ist die Ordnung [mm] $2^{n-2}$.
[/mm]
mfG Moudi
|
|
|
|
