Moduloeigenschaft(en) < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweise folgende Formeln:
$((a [mm] \mod [/mm] n) + (b [mm] \mod [/mm] n)) [mm] \mod [/mm] n = (a + b) [mm] \mod [/mm] n $
$((a [mm] \mod [/mm] n) (b [mm] \mod [/mm] n) [mm] \mod [/mm] n = (ab) [mm] \mod [/mm] n$ |
Nun hab ich gedacht, dass schaff ich in 5 Minuten, da es ja eigentlich recht trivial ist aber ich sitz da jetzt schon seit gestern dran.
Ich habe erst versucht die Formel direkt umzuformen. Da ich aber schon ein bisschen aus den Kongurenzen raus bin (paar Jahre her, dass ich damit gearbeitet habe), bin ich mir nicht mehr so sicher welche Rechenregeln ich bezueglich Multiplikation anwenden darf.
Deswegen hab ich Modulo umgeschrieben in:
$(a+b) [mm] \mod [/mm] n = (a+b) - n [mm] \cdot \lfloor \frac{a+b}{n}\rfloor$
[/mm]
analog mit der linken Seite.
Leider fummel ich mir da aber nur einen mit den Gaussklammern ab, ohne da irgendetwas rein oder rausziehen zu können. Weshalb ich da stecken bleibe.
Wahrscheinlich bin ich damit sowieso auf dem Holzweg. Mir fehlt aber der richtige Ansatz. Ich ärger mich selbst, dass ich bei so einer Banalität ins Stocken komme.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:32 Do 04.11.2010 | | Autor: | Sigma |
Hallo Sesquilinearform,
ich versuche mal bei Aufgabe a) zu helfen.
$ ((a [mm] \mod [/mm] n) + (b [mm] \mod [/mm] n)) [mm] \mod [/mm] n = (a + b) [mm] \mod [/mm] n $
Hier wollen wir hin:
$ (a+b) [mm] \mod [/mm] n = (a+b) - n [mm] \cdot \lfloor \frac{a+b}{n}\rfloor [/mm] $
$ ((a [mm] \mod [/mm] n) + (b [mm] \mod [/mm] n)) [mm] \mod [/mm] n = [mm] a-\left\lfloor{\frac{a}{n}}\right\rfloor*n+ b-\left\lfloor{\frac{b}{n}}\right\rfloor*n-\left\lfloor{ \frac{a}{n}-\left\lfloor{\frac{a}{n}}\right\rfloor+ \frac{b}{n}-\left\lfloor{\frac{b}{n}}\right\rfloor}\right\rfloor*n$
[/mm]
Jetzt wenden wir in der letzten Gaußklammer an, das für reelle Zahlen x und ganze Zahlen k gilt:$ [mm] \left\lfloor{x+k}\right\rfloor= \left\lfloor{x}\right\rfloor+k$
[/mm]
$ ((a [mm] \mod [/mm] n) + (b [mm] \mod [/mm] n)) [mm] \mod [/mm] n = [mm] a+b-\left\lfloor{\frac{a}{n}}\right\rfloor*n-\left\lfloor{\frac{b}{n}}\right\rfloor*n-\left\lfloor{ \frac{a}{n}+ \frac{b}{n}}\right\rfloor*n+\left\lfloor{\frac{a}{n}}\right\rfloor*n+\left\lfloor{\frac{b}{n}}\right\rfloor*n$
[/mm]
Jetzt noch kürzen und wir haben das Ergebnis:
$((a [mm] \mod [/mm] n) + (b [mm] \mod [/mm] n)) [mm] \mod [/mm] n = [mm] a+b-\left\lfloor{ \frac{a}{n}+ \frac{b}{n}}\right\rfloor*n=(a+b) \mod [/mm] n$ [mm] \hfill $\Box$
[/mm]
mfg sigma
|
|
|
| |
|
Wenn man es so sieht..
ich habe den Ansatz so oft versucht und immer verrechnet. Sodass ich nie kuerzen konnte.
Danke fuer die Erleuchtung.
|
|
|
| |
|
| Aufgabe | Beweise:
$ ((a [mm] \mod [/mm] n) (b [mm] \mod [/mm] n) [mm] \mod [/mm] n = (ab) [mm] \mod [/mm] n $ |
Mir fällt gerade auf,
das gilt nur wenn $a,bnn [mm] \in \IZ$ [/mm] sind oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:40 Do 04.11.2010 | | Autor: | Sigma |
> Beweise:
> [mm]((a \mod n) (b \mod n) \mod n = (ab) \mod n[/mm]
>
>
> Mir fällt gerade auf,
> das gilt nur wenn [mm]a,bnn \in \IZ[/mm] sind oder?
Nein, z.Bsp. gilt:
$((3.3 [mm] \mod [/mm] 2)(4.4 [mm] \mod 2))\mod [/mm] 2 = (3.3*4.4) [mm] \mod [/mm] 2$
$(1.3*0.4) [mm] \mod [/mm] 2 = 14.52 [mm] \mod [/mm] 2$
$0.52=0.52 $
|
|
|
| |
|
Das verstehe ich nicht.
Ich ende irgendwann in:
$ab + n(-a [mm] \lfloor \frac{b}{n}\rfloor [/mm] - [mm] b\lfloor \frac{a}{n}\rfloor [/mm] + [mm] \lfloor \frac{a}{n}\rfloor \lfloor \frac{b}{n}\rfloor [/mm] n) - [mm] \lfloor \frac{ab}{n} [/mm] - a [mm] \lfloor \frac{b}{n}\rfloor [/mm] - [mm] b\lfloor \frac{a}{n}\rfloor [/mm] + [mm] \lfloor \frac{a}{n} \rfloor \lfloor \frac{b}{n} \rfloor [/mm] n [mm] \rfloor [/mm] n
Selbst wenn ich die grosse Gaussklammer umforme kann ich nichts raus oder reinziehen, weil nichts ganzzahlig ist.
Ich habe aber auch nichts ganzzahliges was ich in die Klammer reinziehen könnte, da immer ein realwertiger Faktor davor steht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:08 Do 04.11.2010 | | Autor: | Sigma |
Was ist den mit [mm] $\lfloor \frac{a}{n} \rfloor \lfloor \frac{b}{n} \rfloor$ [/mm] und [mm] $-a\lfloor \frac{b}{n}\rfloor [/mm] - [mm] b\lfloor \frac{a}{n}\rfloor$ [/mm]
Das ist alles ganzzahlig für $a,b,n [mm] \in \IZ$ [/mm] Ob das ganze auch für a,b [mm] \in \IR [/mm] und n [mm] \in \IZ [/mm] gilt. Weiß ich noch nicht. Ich denke ja, aber dann muss sich die letzte Gaußklammer ja auch auflösen lassen.
OK gilt wohl doch nur für $a,b,n [mm] \in \IZ$ [/mm] Gegenbeispiel folgt:
$((3.75 [mm] \mod [/mm] 3)(3.3 [mm] \mod [/mm] 3)) [mm] \mod [/mm] 3 [mm] \not= [/mm] (3.75*3.3) [mm] \mod [/mm] 3$
$(0.75*0.3) [mm] \mod [/mm] 3 [mm] \not= [/mm] 12.375 [mm] \mod [/mm] 3$
$ 0.225 [mm] \not= [/mm] 0.375$
|
|
|
| |
|
Also fuer $a,b,n [mm] \in \IZ$ [/mm] ist es ganz einfach, dann passiert das:
$ab + [mm] \underbrace{n(-a \lfloor \frac{b}{n} \rfloor - b \lfloor \frac{a}{n} \rfloor + \lfloor \frac{a}{n} \rfloor \lfloor \frac{a}{n}\rfloor \lfloor \frac{b}{n}\rfloor n) - \lfloor \frac{a}{n} \rfloor \lfloor{b}{n} \rfloor n^2 - a \lfloor \frac{b}{n} \rfloor n - b\lfloor \frac{a}{n} \rfloor n}_{\text{ kuerzt sich weg }} [/mm] - [mm] \lfloor \frac{ab}{n} \rfloor [/mm] n$
was genau das ist was ich will.
Fuer $a,b [mm] \in \IR, [/mm] n [mm] \in \IZ [/mm] $ sehe ich allerdings keine Lösung. Ausser es gibt eine Eigenschaft die besagt, dass
$ -a [mm] \lfloor \frac{b}{n} \rfloor [/mm] -b [mm] \lfloor \frac{a}{n} \rfloor \in \IZ [/mm] $
Da das doch aber sehr speziell ist und man es auch nicht sieht, komm ich hier auch nicht weiter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:50 Do 04.11.2010 | | Autor: | Sigma |
> Also fuer [mm]a,b,n \in \IZ[/mm] ist es ganz einfach, dann passiert
> das:
>
> [mm]ab + \underbrace{n(-a \lfloor \frac{b}{n} \rfloor - b \lfloor \frac{a}{n} \rfloor + \lfloor \frac{a}{n} \rfloor \lfloor \frac{a}{n}\rfloor \lfloor \frac{b}{n}\rfloor n) - \lfloor \frac{a}{n} \rfloor \lfloor{b}{n} \rfloor n^2 - a \lfloor \frac{b}{n} \rfloor n - b\lfloor \frac{a}{n} \rfloor n}_{\text{ kuerzt sich weg }} - \lfloor \frac{ab}{n} \rfloor n[/mm]
>
> was genau das ist was ich will.
> Fuer [mm]a,b \in \IR, n \in \IZ[/mm] sehe ich allerdings keine
> Lösung. Ausser es gibt eine Eigenschaft die besagt, dass
>
> [mm]-a \lfloor \frac{b}{n} \rfloor -b \lfloor \frac{a}{n} \rfloor \in \IZ[/mm]
>
> Da das doch aber sehr speziell ist und man es auch nicht
> sieht, komm ich hier auch nicht weiter
Leider gilt die Gleichung wohl doch nur für $a,b,n [mm] \in \IZ$.Sonst [/mm] lässt sich die Gaußklammer nicht vereinfachen. Es gibt zwar Zahlen [mm]a,b \in \IR, n \in \IZ[/mm] für die es gilt(siehe Beispiel), aber leider auch welche wo die Gleichung nicht gilt(siehe Gegenbeispiel).
|
|
|
|
