Rechnen mit Restklassen

26.07.2023, 14:57

Malcang

Rechnen mit Restklassen

Hallo zusammen,

ich habe immernoch große Probleme, den Umgang mit Restklassen korrekt aufzuschreiben. Es ist ja

Zitat:

$\begin{eqnarray*} a\equiv b\pmod m \Leftrightarrow m\mid b-a. \end{eqnarray*}$

Nun weiß ich ja, dass dies nicht eindeutig ist. Dafür haben wir die Schreibweise $\begin{eqnarray*} [a]_m := \left\{ b\in\mathbb Z : b\equiv a\pmod m\right\} \end{eqnarray*}$ .

Nun möchte ich gerne folgenden Ausdruck "darstellen":
Wir haben für natürliche Zahlen $\begin{eqnarray*} a,b,c,m \end{eqnarray*}$ den Term $\begin{eqnarray*} a\cdot b^c \end{eqnarray*}$ und betrachten diesen modulo $\begin{eqnarray*} m. \end{eqnarray*}$ Aber nun ist es doch nicht korrekt dass ich schreibe

Zitat:

$\begin{eqnarray*} a\cdot b^c \equiv (a\pmod m)\cdot (b\pmod m)^c \end{eqnarray*}$ .

Oder um sogar noch einen Schritt weiter zu gehen, kann ich ja auch die Ordnung von $\begin{eqnarray*} b \end{eqnarray*}$ modulo $\begin{eqnarray*} m \end{eqnarray*}$ betrachten. Sei diese mit $\begin{eqnarray*} ord_m(b) \end{eqnarray*}$ bezeichnet. Das führt dann zu

Zitat:

$\begin{eqnarray*} a\cdot b^c \equiv (a\pmod m)\cdot (b\pmod m)^{c \pmod{ord_m(b)}} \end{eqnarray*}$ .

Als Beispiel betrachte ich mal $\begin{eqnarray*} 154\cdot 20^{301} \pmod 9 \end{eqnarray*}$ :
$\begin{eqnarray*} 154\cdot 20^{301} \equiv (154 \pmod 9)\cdot (20\pmod 9)^{301} \equiv 1\cdot 2^{301} \end{eqnarray*}$ , was ja vom Ergebnis her erstmal stimmt. Außerdem ist $\begin{eqnarray*} ord_9(20) = 6 \end{eqnarray*}$ und damit kann ich rechnen
$\begin{eqnarray*} 1\cdot 2^{301} \equiv 2^1 \equiv 2 \pmod 9 \end{eqnarray*}$ , und das ist ja auch das richtige Ergebnis. Aber der Weg ist hier der falsche verwirrt

Wie gehe ich das sauber an?

Entschuldigt bitte dass ich möglicherweise "wirr" frage. Aber dieses Thema habe ich leider nie wirklich verinnerlicht, dafür aber zu stark bereits angewendet.

26.07.2023, 15:02

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Aber nun ist es doch nicht korrekt dass ich schreibe

Zitat:

$\begin{eqnarray*} a\cdot b^c \equiv (a\pmod m)\cdot (b\pmod m)^c \end{eqnarray*}$ .

Doch, ist korrekt und auch so nachweisbar.

Zitat:

Original von Malcang
Oder um sogar noch einen Schritt weiter zu gehen, kann ich ja auch die Ordnung von $\begin{eqnarray*} b \end{eqnarray*}$ modulo $\begin{eqnarray*} m \end{eqnarray*}$ betrachten. Sei diese mit $\begin{eqnarray*} ord_m(b) \end{eqnarray*}$ bezeichnet. Das führt dann zu

Zitat:

$\begin{eqnarray*} a\cdot b^c \equiv (a\pmod m)\cdot (b\pmod m)^{c \pmod{ord_m(b)}} \end{eqnarray*}$ .

Stimmt auch, sofern $\begin{eqnarray*} b \end{eqnarray*}$ überhaupt eine solche Ordnung besitzt - mit anderen Worten: teilerfremd zu $\begin{eqnarray*} m \end{eqnarray*}$ ist.

26.07.2023, 15:12

Malcang

Auf diesen Beitrag antworten »

HAL 9000, ich danke die ganz vielmals für deine Mühen. Vielleicht hole ich dann jetzt doch nochmal aus:
Ich schreibe aktuell eine Arbeit, über die mein Prof natürlich drüberschaut. Nun habe ich in der Arbeit folgendes geschrieben:

Zitat:

Seien h und k natürliche Zahlen und p eine Primzahl. $\begin{eqnarray*} h\cdot 2^k + 1 \equiv (h\pmod p)\cdot 2^{k\pmod{ord_p(2)}} + 1 \pmod p. \end{eqnarray*}$

Nun hat er mir aber $\begin{eqnarray*} (h\pmod p) \end{eqnarray*}$ und $\begin{eqnarray*} k \pmod{ord_p(2))} \end{eqnarray*}$ angestrichen mit dem Kommentar "So etwas gibt es nicht. Andere Bezeichnung finden".

Gut, ich hätte um die rechte Seite möglicherweise Klammern setzen sollen. Aber ich verstehe nicht, warum er mir nur diese beiden angestrichen hat verwirrt

Natürlich möchte ich das erstmal "diskutieren", damit ich da einen stärkeren Lerneffekt habe und das Forum davon vielleicht auch profitiert, als nur zu ihm hinzugehen.

26.07.2023, 16:04

Elvis

Auf diesen Beitrag antworten »

Wenn du die Restklasse $\begin{eqnarray*} \overline h=h+p\mathbb Z \end{eqnarray*}$ meinst, dann schreibe das doch und nicht einen solchen Unsinn wie $\begin{eqnarray*} h (\mod p) \end{eqnarray*}$ . Eine Restklasse kann natürlich nicht gleich und nicht kongruent einer Zahl $\begin{eqnarray*} h\cdot 2^k+1 \end{eqnarray*}$ sein. Zahlen können gleich oder verschieden, kongruent oder nicht kongruent sein. Restklassen können gleich oder verschieden sein, Restklassen können nicht kongruent sein. Zahlen und Restklassen kann man addieren und multiplizieren, aber das sind verschiedene Objekte und verschiedene Operationen. Du musst dich schon entscheiden, ob du über Zahlen, Restklassen oder Vertreter von Restklassen redest; Vertreter von Restklassen sind Elemente von Restklassen, also Zahlen.

26.07.2023, 16:17

Malcang

Auf diesen Beitrag antworten »

Auch dir Elvis vielen dank für deine Zeit.
Ich muss allerdings Rückfragen, denn ich habe nun von dir und HAL zwei widersprüchliche antworten erhalten. Oder liegt es daran, dass ich mod p nicht nochmal ans Ende setzen sollte?

26.07.2023, 17:03

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
denn ich habe nun von dir und HAL zwei widersprüchliche antworten erhalten.

Tatsächlich?

Ich hatte angenommen, du weißt über die verschiedenen Bedeutungen der Symbolik "mod" Bescheid - anscheinend doch nicht so richtig:

1) Es gibt die zweistellige Operation $\begin{eqnarray*} a{\color{red}\bmod} m = r \end{eqnarray*}$ mit ganzzahligen Argumenten $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} m\geq 1 \end{eqnarray*}$ , das ist einfach der Rest bei Multiplikation durch $\begin{eqnarray*} m \end{eqnarray*}$ , mit möglichen Werten $\begin{eqnarray*} r\in\{0,1,\ldots,m-1\} \end{eqnarray*}$ .

2) Es gibt die Schreibweise $\begin{eqnarray*} a\equiv b{\color{blue}\bmod} m \end{eqnarray*}$ , die für ganze Zahlen $\begin{eqnarray*} a,b,m \end{eqnarray*}$ einfach nur das gleiche bedeutet wie $\begin{eqnarray*} m\mid (b-a) \end{eqnarray*}$ .

In dem Sinne ist die Rechenvereinfachung

$\begin{eqnarray*} a\cdot b^c \equiv \left(a{\color{red}\bmod} m\right)\cdot \left(b{\color{red}\bmod} m\right)^{c{\color{red}\bmod} \operatorname{ord}_m(b)}{\color{blue}\bmod} m \end{eqnarray*}$

für ganze Zahlen $\begin{eqnarray*} a,b,m \end{eqnarray*}$ (wobei $\begin{eqnarray*} b,m \end{eqnarray*}$ teilerfremd sind) durchaus richtig - so habe ich es zumindest gemeint, nicht anders!!!

26.07.2023, 18:50

Malcang

Auf diesen Beitrag antworten »

Danke nochmal für diese Erklärung HAL. Ich denke, damit hat sich der Knoten etwas gelöst.
Wenn ich das richtig sehe, darf ich also schreiben:
$\begin{eqnarray*} h\cdot 2^k + 1 \bmod p = (h\bmod p)\cdot 2^{k\pmod{ord_p(2)}} + 1 \end{eqnarray*}$
oder auch
$\begin{eqnarray*} h\cdot 2^k + 1 \equiv (h\bmod p)\cdot 2^{k\pmod{ord_p(2)}} + 1 \bmod p \end{eqnarray*}$ ,
korrekt?

Ich vergleiche das halt gerne mit der Eingabe im Taschenrechner: $\begin{eqnarray*} 78 \ mod 9 \end{eqnarray*}$ liefert mir ja $\begin{eqnarray*} 6 \end{eqnarray*}$ und nicht etwa $\begin{eqnarray*} -3 \end{eqnarray*}$ oder $\begin{eqnarray*} 15 \end{eqnarray*}$ oder gar eine Menge.

27.07.2023, 09:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Wenn ich das richtig sehe, darf ich also schreiben:
$\begin{eqnarray*} h\cdot 2^k + 1 \bmod p = (h\bmod p)\cdot 2^{k\pmod{ord_p(2)}} + 1 \end{eqnarray*}$

Wenn das = im Sinne Gleichheit ganzer Zahlen steht, dann ist das i.a. falsch: Es ist nur gewährleistet, dass links wie rechts des Gleichheitszeichens ganze Zahlen derselben Restklasse modulo $\begin{eqnarray*} p \end{eqnarray*}$ stehen.

Anders ausgedrückt: In deiner Gleichung ist keineswegs gewährleistet, das rechts eine Zahl aus $\begin{eqnarray*} \{0,1,\ldots,p-1\} \end{eqnarray*}$ rauskommt (so wie es links der Fall ist).

Zitat:

Original von Malcang
$\begin{eqnarray*} h\cdot 2^k + 1 \equiv (h\bmod p)\cdot 2^{k\pmod{ord_p(2)}} + 1 \bmod p \end{eqnarray*}$ ,

Das ist Ok.

28.07.2023, 08:34

Malcang

Auf diesen Beitrag antworten »

Vielen Dank nochmal für diese Erklärungen, das hat wirklich geholfen Freude

Neue Frage »

Antworten »

Rechnen mit Restklassen

Verwandte Themen