| |
| Autor |
  Rest und Kongruenz |
|
native
Ehemals Aktiv 
Dabei seit: 29.09.2002
Mitteilungen: 79
Wohnort: 030 / 44
 |  Themenstart: 2004-05-29
|
gruesst euch,
Sind a,b,m ganze Zahlen, m > 0 und rem(a,m) \teiltnicht m, dann gilt
a^b == rem(a,m)^(rem(b,\phi(m))) mod m
dabei bezeichnet rem(a,m) den Rest von a bei der Division durch m.
ich komm leider gar nich weiter, da ich keine Ansaetze haben.
und auch mit dem umgeformten
(a^b - rem(a,m)^(rem(b,\phi(m))) ) mod m = 0
<=> a^b mod m - (rem(a,m)^(rem(b,\phi(m))) ) mod m = 0
komm ich nicht weiter.
Was spielt das rem(a,m) \teiltnicht m fuer eine rolle?
bin fuer jeden Tipp dankbar.
gruss
joe
p.s.: ist die Funktion \phi(m) bekannt? also grob erklaert,
die anzahl der der Zahlen < m die relativ prim zu m sind.
|
 Profil
|
Gockel
Senior 
Dabei seit: 22.12.2003
Mitteilungen: 25548
Wohnort: Jena
 | Beitrag No.1, eingetragen 2004-05-29
|
Hi native.
rem und mod sind eigentlich dasselbe
Wenn man das ganze nun im Restklassenring \IZ_m betrachtet
- im Prinzip macht man damit nur deutlich, dass nach jeder
Multiplikation, Addition und Subtraktion noch einmal mod m
ausgeführt wird - dann schreibt sich das so:
a^b==a^(b mod \phi(m)) (mod m)
Wenn du a^i mod m betrachtest und dabei i von 1 bis b durchlaufen
lässt, stellst du fest, dass es u.U. dazu kommt, dass irgendwann
zwischendurch der Anfangswert weider erreicht wird, sodass sich
eine periodische Wiederholung ergibt. Die Gleichung sagt aus,
dass diese Periode bei \phi(m) liegt und das es deshalb ausreicht
den mod \phi(m) reduizierten Exponenten zu betrachten.
Verstehst du, was ich meine? Wenn nicht, versuch ichs anders zu
erklären.
mfg Gockel.
|
Profil
|
native
Ehemals Aktiv
Dabei seit: 29.09.2002
Mitteilungen: 79
Wohnort: 030 / 44
| Beitrag No.2, vom Themenstarter, eingetragen 2004-05-31
|
gruess dich,
also 100% konnte ich es nicht nachvollziehen, Restklassenring sagt mir so leider auch nix ;(
hab mir mal ein bsp ausgedacht:
a=b=5 und b=3
x_i = a^i mod m
dabei ist die loesung: x = {2,1,2,1,2} da sieht man
dann wohl die wiederholung, d.h. also man muesste nur bis
zum 2.Index ( und das ist "zufaellig" \phi(m)?!, da
\phi() fuer prims ja so definiert ist \phi(m) = m-1 )
Aber wie du jetzt auf die Gleichung kommst,
kann ich nicht nachvollziehen.
also waere ich ueber "andere" erklaerung sehr dankbar!!
danke!
j
p.s.: ist das bsp eigentlich ok so?
|
Profil
|
Gockel
Senior
Dabei seit: 22.12.2003
Mitteilungen: 25548
Wohnort: Jena
| Beitrag No.3, eingetragen 2004-05-31
|
Hi.
"Restklassenring" bedeutet, dass du anderes rechnest als mit normalen Zahlen, denn im Gegensatz zu den ganzen Zahlen führst du in einem Restklassenring nach jeder Addition, Subtraktion und Multiplikation mod m aus.
In diesen Strukturen gilt beispielsweise 2+7=0. Setze dazu m=9. Jetzt musst du ja wie gesagt nach jeder Addition mod m ausführen. Deshalb gilt 7+2=0, denn 9 mod 9 =0.
Ein anderes Beispiel ist deine Armbanduhr (oder irgendeine andere Uhr). Hier gilt zum Beispiel 2 + 11 = 1. In diesem Fall wäre m=12.
Verstehst du das Prinzip?
Jetzt führt man für Restklassenringe neue Schreibweisen ein. Man schreibt zum Beispiel i.A. nicht mehr 11+2=1, sondern
11+2==1(mod $ 12)
Damit man erstens immer erkennt, wann man "normal" rechnet und wann nicht und zum anderen damit man das m immer erkennt.
Dein Beispiel ist gut, denn wie du richtig erkannt hast, tritt die Widerholung genau bei 2 ein, was (nicht nur aus Zufall) exakt phi(m) entspricht.
mfg Gockel.
|
Profil
|
native
Ehemals Aktiv
Dabei seit: 29.09.2002
Mitteilungen: 79
Wohnort: 030 / 44
| Beitrag No.4, vom Themenstarter, eingetragen 2004-05-31
|
ok verstanden.
also ich versuche mich nochmal:
a^b == rem(a,m)^(rem(b,\phi(m))) mod m
das koennte man also auch so schreiben:
a^b == a^(b mod \phi(m)) mod m
1.fall:
a^b = a^(b mod \phi(m))
dann waere das trivial :)...a^b == a^b mod m
2.fall:
a^b >= a^(b mod \phi(m))
(a^b - a^(b mod phi(m))) mod m = 0
ob das stimmt?
d = (a^b - a^(b mod phi(m)));
d < a^b, ob sich d nun durch m teilen laesst ohne einen
Rest zu hinterlassen, sagt das auch nicht aus?! ( oder
mach ich es mir gerade zu kompliziert? )
nochmals danke!
j
[ Nachricht wurde editiert von native am 2004-05-31 22:47 ]
|
Profil
|
native hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
