Kongruenz beweisen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 12:52 Di 30.08.2011 | Autor: | sillium |
Aufgabe | Folgendes Problem:
es gilt:
[mm] a^j [/mm] ≡ [mm] b^j [/mm] mod n
und
[mm] a^r [/mm] ≡ [mm] b^r [/mm] mod n
daraus soll folgen:
[mm] a^s [/mm] ≡ [mm] b^s [/mm] mod n
wobei j=l*r+s mit 0<s<r
mir scheinen die rechenregel für kongruenzen (addition multiplikation und potenzieren) nicht zu helfen.
kann mir jemand einen tipp geben |
Hallo,
kann mir jemand bite einen tipp geben dies zu lösen?
mir scheinen die rechenregel für kongruenzen (addition multiplikation und potenzieren) nicht zu helfen.
Grüße
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 13:25 Di 30.08.2011 | Autor: | leduart |
Hallo
setz doch einfach mal s in deine Kongruez ein
[mm] a^{lr}=b^{lr} [/mm] mod n folgt doch
welche Regeln sind denn verletzt?
Gruss leduart
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 13:41 Di 30.08.2011 | Autor: | Nisse |
> kann mir jemand bite einen tipp geben dies zu lösen?
Mein Tipp wäre: Schau Dir noch einmal an, wie ihr [mm] a \equiv b \mod n[/mm] definiert habt. Da gibt es eine Darstellung mit der man besser rechnen kann. Und dann rechne los und überlege, wie man [mm]a^s -b^s[/mm] zerlegen kann.
|
|
|
|
|
Status: |
(Frage) überfällig | Datum: | 23:17 Di 30.08.2011 | Autor: | sillium |
kann ich folgender maßen argumentieren:
[mm] a^j \equiv b^j [/mm] mod n
[mm] a^{lr+s} \equiv b^{lr+s} [/mm] mod n
[mm] a^{lr} a^{s} \equiv b^{lr} b^{s} [/mm] mod n
[mm] a^{lr} a^{s} [/mm] = kn + [mm] b^{lr} b^{s}
[/mm]
und
[mm] a^{r} \equiv b^{r} [/mm] mod n
[mm] (a^{r})^{l} \equiv (b^{r})^{l} [/mm] mod n
[mm] a^{lr} \equiv b^{lr} [/mm] mod n
[mm] a^{lr}=Kn+b^{lr}
[/mm]
wenn man nun zweites in erstes einsetzt folgt:
(Kn + [mm] b^{lr}) a^{s} [/mm] = kn + [mm] b^{lr} b^{s} [/mm]
[mm] Kna^{s} [/mm] + [mm] b^{lr} a^{s} [/mm] - [mm] b^{lr} b^{s} [/mm] = kn
[mm] b^{lr} (a^{s} [/mm] - [mm] b^{s}) [/mm] = [mm] (k-Ka^{s})n
[/mm]
da nun linke seite durch n teilbar und b^lr [mm] \not= [/mm] 0 mod n muss [mm] a^s [/mm] - [mm] b^s [/mm] durch n teilbar sein??
vielen dank
Grüße
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 23:20 Do 01.09.2011 | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|