Beweis für modulo-Rechenregeln < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie, dass folgende Aussage gilt:
[mm] $(a+b)\bmod [/mm] n = [mm] (a\bmod [/mm] n + [mm] b\bmod n)\bmod [/mm] n$ |
Hi!
Ich soll oben stehende Rechenregel (als auch die weiteren für Subtraktion, Multiplikation und Potenzierung, aber ich vermute das verläuft dann recht analog) beweisen.
Leider hänge ich total durch. Ich komme irgendwie nur mittels Equivalenzen von der linken zur rechten Seite, das reicht ja aber offensichtlich nicht, denn es ist ja eine Identiät!
Mein Ansatz:
[mm] $(a+b)\bmod n=(an+bn)\bmod n\equiv (an\bmod n+bn\bmod n)\bmod n=(a\bmod n+b\bmod n)\bmod [/mm] n$
Danke für jede Hilfe!
---
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:46 Mi 13.11.2013 | | Autor: | Teufel |
Hi!
Wie kommst du denn auf die 1. Gleichung? Es gilt doch stets $(an+bn) [mm] \mod [/mm] n = 0$! Ich würde folgende Äquivalenz ausnutzen:
$a [mm] \mod [/mm] n = b [mm] \mod [/mm] n [mm] \gdw [/mm] n|a-b [mm] \gdw [/mm] a-b=kn [mm] \gdw [/mm] a=b+kn$ für ein $k [mm] \in \IZ$. [/mm] Nimm dir also mal die zu zeigende Gleichung und nutz dann diese Äquivalenz (die du vorher zeigen muss, wenn ihr das nicht schon gemacht habt oder es eh klar ist ;) ).
Dann beachte noch, dass z.B. a=qn+r geschrieben werden kann und $a [mm] \mod [/mm] n$ dann einfach $r$ ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:03 Mi 13.11.2013 | | Autor: | thissideup |
> Hi!
>
> Wie kommst du denn auf die 1. Gleichung? Es gilt doch stets
> [mm](an+bn) \mod n = 0[/mm]!
oha! Das war mir tatsächlich gar nicht bewusst! Aber jetzt wo du es sagst, ergibt es natürlich Sinn (und diese Erkenntnis hilft mir sogar bereits  ).
Deinen Vorschlag werde ich mir später oder morgen nochmal näher anschauen, habe leider gerade keine Zeit. Im Moment ist mir noch nicht so sehr klar inwiefern ich diese Äquivalenz denn [mm] $\forall a,b\in\mathbb{Z}$ [/mm] nutzen kann, es scheint mir so, als würde das ja nur für bestimmte $a,b$ funktionieren. Aber wie gesagt, ich schau es mir in Ruhe nochmal näher an.
Vielen, lieben Dank auf jeden Fall schon mal!
|
|
|
| |
|
Okay, ich glaube ich habe deinen Tipp doch nicht ganz verstanden, denn wenn ich hier hin und her transformiere, dann komme ich zum Ergebnis: $r+s+kn=r+s+2kn$, was ja eine Kontradiktion ist.
Lemma 1: $x [mm] \bmod [/mm] n = y [mm] \bmod [/mm] n [mm] \iff [/mm] n|x-y [mm] \iff [/mm] x-y=kn [mm] \iff [/mm] x=y+kn$
Lemma 2: $x = qn+r$
[mm] $(a+b)\bmod n=(a\bmod n+b\bmod n)\bmod n\overset{Lemma 2}{=} (r+s)\bmod n\overset{Lemma 1}{\iff} a+b=r+s+kn\iff [/mm] a=r+s+kn-b$
[mm] $(a+b)\bmod n=(a\bmod n+b\bmod n)\bmod n\iff (r+s+kn-b+b)\bmod n=((r+s+kn-b)\bmod n+b\bmod n)\bmod n\overset{Lemma 1}{\iff}r+s+kn=r+s+kn-b+b+kn\iff [/mm] r+s+kn=r+s+2kn$
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:17 Mo 18.11.2013 | | Autor: | Teufel |
Hi!
Ne, da ging was schief. Dieses du musst immer ein anderes k verwenden, wenn du die Modulogleichung umschreiben willst. z.B. ist $9 [mm] \mod [/mm] 4 = 5 [mm] \mod [/mm] 4 [mm] \gdw [/mm] 9=5+1*4$, aber $13 [mm] \mod [/mm] 4 = 5 [mm] \mod [/mm] 4 [mm] \gdw [/mm] 13=5+2*4$.
Fang mal so an:
[mm] $(a+b)\mod [/mm] n = [mm] (a\mod [/mm] n + [mm] b\mod [/mm] n) [mm] \mod [/mm] n [mm] \gdw a+b-(a\mod n)-(b\mod [/mm] n)=kn$ für irgendein [mm] $k\in\IZ$. [/mm] Jetzt arbeite mit der Darstellung $a=qn+r$, $b=q'n+r'$.
|
|
|
| |
|
> Hi!
>
> Ne, da ging was schief. Dieses du musst immer ein anderes k
> verwenden, wenn du die Modulogleichung umschreiben willst.
hehe, sowas sollte natürlich nicht passieren... 
> Fang mal so an:
> [mm](a+b)\mod n = (a\mod n + b\mod n) \mod n \gdw a+b-(a\mod n)-(b\mod n)=kn[/mm]
> für irgendein [mm]k\in\IZ[/mm]. Jetzt arbeite mit der Darstellung
> [mm]a=qn+r[/mm], [mm]b=q'n+r'[/mm].
hm, auf eine ähnliche Idee bin ich auch schon mal gekommen, nur habe ich da kaum Sinn drin erkannt:
$a+b-r-r'=kn$ (also [mm] $a\bmod [/mm] n=r$ eingesetzt) zeigt ja imho gar nichts, und mit [mm] $a+b-((qn+r)\bmod n)-((q'n+r')\bmod [/mm] n)=kn$ kann ich irgendwie nichts anfangen. Es kommt mir so vor, als würde mir auch genau bei [mm] $(qn+r)\bmod [/mm] n$ der richtige Ansatz fehlen. Aber kürzen oder ausklammern kann man da doch überhaupt nichts, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:53 Di 19.11.2013 | | Autor: | Teufel |
Hi nochmal!
Sorry, vielleicht war die Äquivalenz mit dem k auch etwas irreführend. Nehmen wir mal stattdessen $a [mm] \mod [/mm] n = b [mm] \mod [/mm] n [mm] \gdw [/mm] n|a-b$. Ist ja das gleiche wie mit dem $k$, nur dass man hier keine neues Symbol einführen muss.
In unserem Fall wollen wir also zeigen: [mm] $n|a+b-(a\mod n)-(b\mod [/mm] n)$. Weil wir $a=qn+r$ und $b=q'n+r'$ schreiben können, gilt [mm] $a+b-(a\mod n)-(b\mod [/mm] n)=(qn+r)+(q'n+r')-r-r'=(q+q')n$, also gilt [mm] $n|a+b-(a\mod n)-(b\mod [/mm] n)$, was wir zeigen wollten.
Ist das ok so? Oder gibt es noch Fragen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:35 Mi 20.11.2013 | | Autor: | thissideup |
Aah, natürlich, jetzt ist es offensichtlich.
Mein großes Problem schien tatsächlich in der Beziehung von $a=qn+r$, [mm] $a\bmod [/mm] n=r$ und $n|(a-r)$ zu bestehen. In modulare Arithmetik muss sich echt erst einmal hineingedacht werden - obwohl es ja eigentlich alles recht simpel ist!
Vielen, vielen Dank auf jeden Fall für deine Hilfe und Geduld!
|
|
|
| |
|
Hallo thissideup, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Beweisen Sie, dass folgende Aussage gilt:
> [mm](a+b)\bmod n = (a\bmod n + b\bmod n)\bmod n[/mm]
> Hi!
>
> Ich soll oben stehende Rechenregel (als auch die weiteren
> für Subtraktion, Multiplikation und Potenzierung, aber ich
> vermute das verläuft dann recht analog) beweisen.
>
> Leider hänge ich total durch. Ich komme irgendwie nur
> mittels Equivalenzen von der linken zur rechten Seite, das
> reicht ja aber offensichtlich nicht, denn es ist ja eine
> Identiät!
Oder es ist ein Notationsfehler, aber so recht glaube ich das nicht. Wie habt Ihr denn den Hauptrepräsentanten einer Restklasse definiert? Mit anderen Worten: was genau ist eigentlich [mm] $a\bmod{n}$?
[/mm]
> Mein Ansatz:
> [mm](a+b)\bmod n=(an+bn)\bmod n\equiv (an\bmod n+bn\bmod n)\bmod n=(a\bmod n+b\bmod n)\bmod n[/mm]
Na, dazu hast Du ja schon eine Rückmeldung.
> Danke für jede Hilfe!
Grüße
reverend
|
|
|
|
