Modulo-Rechnung

09.11.2012, 12:39

Modulorechner

Modulo-Rechnung

Meine Frage:
Hey ich hänge bei einem Problem

also ich soll überprüfen ob

$\begin{eqnarray*} 3^{444} +4^{333} durch 5 \end{eqnarray*}$ teilbar ist.

Vorgegangen bin ich mit der Modulorechnung

Meine Ideen:
Ausgegangen bin ich von folgenden Regeln:

1) (a + b) mod n = ((a mod n) + (b mod n)) mod n
2) $\begin{eqnarray*} a^{b} mod n = (a modn )^{n} modn \end{eqnarray*}$

Durch einsetzen kam ich dann zu folgendem:

$\begin{eqnarray*} ((((3 mod 5)^{444} mod 5) mod5)+ (((4 mod 5)^{333} mod 5) mod 5)) mod 5 \end{eqnarray*}$

Ist das soweit richtig?
Nur wie ich es weiter auflösen soll weiß ich nicht so genau, da z.B. 3 durch 5 ja wieder rest 3 ergibt..

09.11.2012, 12:44

lgrizu

Auf diesen Beitrag antworten »

RE: Modulo-Rechnung
Die Aufgabe lässt sich schnell mit dem kleinen Fermat lösen, für jede ganze Zahl a gilt

$\begin{eqnarray*} a^{p-1} \equiv 1 \mod p \end{eqnarray*}$

Desweiteren ist $\begin{eqnarray*} (a+b) \mod p \equiv a \mod p + b \mod p \end{eqnarray*}$

Beides angewendet brigt dich worauf?

09.11.2012, 12:53

Summenzeichen1111

Auf diesen Beitrag antworten »

RE: Modulo-Rechnung
oh ok

also ich hab das jetzt so verstanden.

Der kleine Fermat besagt ja dass

$\begin{eqnarray*} 3^{444} mod 5 = 1 mod 5 \end{eqnarray*}$

und

$\begin{eqnarray*} 4^{333} mod 5 = 4 mod 5 \end{eqnarray*}$

Da wir ja (a+b) haben macht das (1+4) = 5

und 5 mod 5 ist 0

Stimmt das so?

09.11.2012, 12:58

lgrizu

Auf diesen Beitrag antworten »

RE: Modulo-Rechnung

Zitat:

Original von Summenzeichen1111

$\begin{eqnarray*} 3^{444} mod 5 = 1 mod 5 \end{eqnarray*}$

Genau, also ausführlich:

$\begin{eqnarray*} 3^{444}=(3^4)^{111} \equiv 1^{111} \mod 5 \equiv 1 \mod 5 \end{eqnarray*}$

Zitat:

Original von Summenzeichen1111
$\begin{eqnarray*} 4^{333} mod 5 = 4 mod 5 \end{eqnarray*}$

und auch hier ausführlich:

$\begin{eqnarray*} 4^{333} =4^{332} \cdot 4 =(4^4)^{83} \cdot 4 \equiv 1^{83} \cdot 4 \mod 5 \equiv 4 \mod 5 \end{eqnarray*}$

Zitat:

Original von Summenzeichen1111
Da wir ja (a+b) haben macht das (1+4) = 5

Zusammen also:

$\begin{eqnarray*} 1 \mod 5 + 4 \mod 5 \equiv (1+4) \mod 5 \equiv 0 \mod 5 \end{eqnarray*}$

Also richtig, die Zahl ist durch 5 teilbar....

09.11.2012, 12:59

Mystic

Auf diesen Beitrag antworten »

RE: Modulo-Rechnung

Zitat:

Original von lgrizu
Die Aufgabe lässt sich schnell mit dem kleinen Fermat lösen, für jede ganze Zahl a gilt

$\begin{eqnarray*} a^{p-1} \equiv 1 \mod p \end{eqnarray*}$

Allerdings schon unter der Voraussetzung, dass p nicht Teiler von a ist, was aber hier glücklicherweise zutrifft... Augenzwinkern