Restklassen berechnen

13.09.2010, 17:32

schnickers

Restklassen berechnen

Meine Frage:
Hallo zusammen,
ich verzweifele Gerade an Grundlegen Aufgaben der Kryptographi.

Folgende Aufgabe:

Berechnen Sie die Restklasse von:
a) (-5)^{16} mod 7
b) 23^{121} mod 24

Meine Ideen:
Die Lösungen habe ich von einem Komilitonen (für a => 2 und für b=>23)
Aber wie komme ich dahin?

Eventuell reicht auch schon ein Ansatz damit ich weiterkomme.
Kann ich den z.B. bei (a) hingehen und die Gleichung nach:
2^{16} mod 7 umfomen?

13.09.2010, 17:34

tmo

Auf diesen Beitrag antworten »

Folgendes sagt eigentlich alles:

$\begin{eqnarray*} a \equiv b \pmod m \Rightarrow a^n \equiv b^n \pmod m \end{eqnarray*}$ für alle $\begin{eqnarray*} a,b \in \mathbb Z \end{eqnarray*}$ und $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$

Bei der a) hilft vielleicht noch das eine oder andere Potenzgesetz, aber die muss ich im Hochschulbereich wohl nicht erwähnen.

13.09.2010, 20:09

schnickers

Auf diesen Beitrag antworten »

Danke erstmal.

irgendwie hab ich aber noch ein Knoten im Hirn. Ist das überhaupt ohne den Euclid lösbar?

$\begin{eqnarray*} x^{16} \equiv (-5)^{16} (mod 7) \Rightarrow x \equiv (-5) (mod 7) \end{eqnarray*}$
Ich kann die Potenzen einfach weglassen? Da hab ich doch sicher was falsch verstanden.

Verzeiht bitte meine evtl. fehlenden Grundlagen Kenntnisse. Das Script was ich habe ist etwas mager und bei den Übungen sind keine Lösungswege dabei.

13.09.2010, 23:33

Julezzz

Auf diesen Beitrag antworten »

Ich geb dir mal den Lösungsweg für die Aufgabe a) an. Der Trick ist, dass du die modulo-Operation an dem Potenzieren "vorbei" machen darfst.

Wir wollen Repräsentanten bestimmen auf modulo 7 bezogen, also Zahlen im Bereich:

$\begin{eqnarray*} \{0,1,2,3,4,5,6\} \end{eqnarray*}$

Aufgabe a)

$\begin{eqnarray*} (-5)^{16} mod 7 \end{eqnarray*}$

Anstelle der -5 kann man 2 (Repräsentant!!!) schreiben, da

$\begin{eqnarray*} -5 = -1 * 7 + 2 \end{eqnarray*}$

also:

$\begin{eqnarray*} 2^{16} mod 7 \end{eqnarray*}$

Jetzt kommen einfache Potenzgesetze zum tragen:

$\begin{eqnarray*} (2^{2})^{8} mod 7 \end{eqnarray*}$
(Potenzen werden potenziert indem die Exponenten multipliziert werden und andersrum)

$\begin{eqnarray*} 4^{8} mod 7 \end{eqnarray*}$

4 ist schon der Repräsentant und wir wiederholen den Schritt von eben:

$\begin{eqnarray*} (4^{2})^{4} mod 7 = 16^{4} mod 7 \end{eqnarray*}$

der Repräsentant für 16 ist 2 da:

$\begin{eqnarray*} 16 = 2 * 7 + 2 \end{eqnarray*}$
(Für uns ist die 2 bei "+ 2" wichtig!!!)

$\begin{eqnarray*} 2^{4} mod 7 = 16 mod 7 \end{eqnarray*}$

wieder ist für 16 der Repräsentant 2 und das Ergebnis lautet:

$\begin{eqnarray*} 2 mod 7 \end{eqnarray*}$

Hoffe, du kommst mit der b) jetzt alleine zurecht!

Gruß
Julian

14.09.2010, 09:40

schnickers

Auf diesen Beitrag antworten »

Super, vielen Dank. Also ich versuchs mal mit der B:

$\begin{eqnarray*} 23^{121} mod 24 \end{eqnarray*}$

Anstelle 23 kann man -1 schreiben, da:
$\begin{eqnarray*} 23=1*24+(-1) \end{eqnarray*}$

also:
$\begin{eqnarray*} (-1)^{121} mod 24 \end{eqnarray*}$

nun ist:
$\begin{eqnarray*} (-1)^{121} = (-1) \end{eqnarray*}$

als:
$\begin{eqnarray*} (-1) mod 24 \end{eqnarray*}$

-1 ist in der gleichen Restklasse wie 23 da:
$\begin{eqnarray*} (-1)=(-1)*24+23 \end{eqnarray*}$

Richtig gerechnet?

14.09.2010, 18:47

tmo

Auf diesen Beitrag antworten »

Super gemacht, Julezzz geschockt

Statt auf diesen fatalen Fehler hinzuweisen, postest du die Komplettlösung.

Zitat:

Original von schnickers
$\begin{eqnarray*} x^{16} \equiv (-5)^{16} (mod 7) \Rightarrow x \equiv (-5) (mod 7) \end{eqnarray*}$
Ich kann die Potenzen einfach weglassen? Da hab ich doch sicher was falsch verstanden.

Das ist im Allgemeinen falsch.

Es ist z.b. $\begin{eqnarray*} 9^2 \equiv 5^2 \pmod 7 \end{eqnarray*}$ , aber $\begin{eqnarray*} 9 \not\equiv 5 \pmod 7 \end{eqnarray*}$ .

Nur die andere Richtung gilt. Wie auch in meinem Post geschrieben. Ich weiß nicht, warum du die Aussagen einfach umdrehst.

Neue Frage »

Antworten »

Restklassen berechnen

Verwandte Themen