Beweis Modulorechnung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:14 Di 11.07.2006 | | Autor: | dump_0 |
| Aufgabe | Seien [mm]a, b, k, m \in \IZ[/mm] und [mm]k \ge 1, m \ge 2[/mm] und es gelte [mm]a \equiv b[/mm] [mm]mod[/mm] [mm]m[/mm].
Zeigen Sie, dass [mm]a^k \equiv b^k[/mm] [mm]mod[/mm] [mm]m[/mm] für alle [mm]k > 0[/mm] gilt. |
Hallo!
Ich weiß nicht ganz genau wie ich die obige Aufgabe richtig beweisen soll, ich hatte an Induktion gedacht und bin mir aber nicht sicher ob es so geht:
Für [mm]k=1[/mm] ist die Aussage offensichtlich erfüllt.
Sei die Aussage also auch für alle [mm]k \in \IZ[/mm] erfüllt.
Dann ist [mm]a^{k+1} \equiv b^{k+1}[/mm] [mm]mod[/mm] [mm]m[/mm]
= [mm]a*a^k \equiv b*b^k[/mm] [mm]mod[/mm] [mm]m[/mm].
Nun weiß ich aber nicht mehr genau weiter mit dem Beweis, laut den "Modulo-Rechenregeln" gilt für versch. ganze Zahlen a,b,c,d:
Falls [mm]a \equiv b[/mm] [mm]mod[/mm] [mm]m[/mm] und [mm]c \equiv d[/mm] [mm]mod[/mm] [mm]m[/mm] gilt, dann gilt auch
[mm]a*c \equiv b*d[/mm] [mm]mod[/mm] [mm]m[/mm].
Aber kann man so einfach argumentieren?
Grüße
[mm] dump_0
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:30 Di 11.07.2006 | | Autor: | Hanno |
Hallo.
> ´Nun weiß ich aber nicht mehr genau weiter mit dem Beweis, laut den "Modulo-Rechenregeln" gilt für versch. ganze Zahlen a,b,c,d:
Falls $ a [mm] \equiv [/mm] b $ mod m und $ c [mm] \equiv [/mm] d $ mod m gilt, dann gilt auch
$ [mm] a\cdot{}c \equiv b\cdot{}d [/mm] $ mod m.
> Aber kann man so einfach argumentieren?
Ja, damit kann man argumentieren.
Alternativ kannst du es auch direkt nachweisen: [mm] $a\equiv b\pmod{m}$ [/mm] ist äquivalent zu $m|a-b$. Möchtest du [mm] $a^k\equiv b^k\pmod{m}$ [/mm] zeigen, musst du also zeigen, dass $m$ Teiler von [mm] $a^k-b^k$ [/mm] ist. Um dies zu sehen, musst du [mm] $a^k-b^k$ [/mm] geeignet faktorisieren.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:38 Di 11.07.2006 | | Autor: | ardik |
> Hallo.
>
> > ´Nun weiß ich aber nicht mehr genau weiter mit dem Beweis,
> laut den "Modulo-Rechenregeln" gilt für versch. ganze
> Zahlen a,b,c,d:
> Falls [mm]a \equiv b[/mm] mod m und [mm]c \equiv d[/mm] mod m gilt, dann
> gilt auch
> [mm]a\cdot{}c \equiv b\cdot{}d[/mm] mod m.
>
> > Aber kann man so einfach argumentieren?
>
> Ja, damit kann man argumentieren.
Hm, mache ich hier einen Denkfehler?
Durch die Verwendung von $c [mm] \equiv [/mm] d [mm] \mod [/mm] m$ setzt man hier doch das zu beweisende bereits als wahr voraus, oder?
Schöne Grüße,
ardik
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:16 Mi 12.07.2006 | | Autor: | Hanno |
Hallo.
> Durch die Verwendung von $ c [mm] \equiv [/mm] d [mm] \mod [/mm] m $ setzt man hier doch das zu beweisende bereits als wahr voraus, oder?
Nein, wenn du induktiv arbeitest, kannst du [mm] $a\equiv b\pmod{m}$ [/mm] und [mm] $a^n\equiv b^n\pmod{m}$ [/mm] voraussetzen und daraus [mm] $a^{n+1}\equiv b^{n+1}\pmod{m}$ [/mm] folgern.
Liebe Grüße,
Hanno
|
|
|
|
