Rest Bestimmen (mit benutzung Satz von Fermat)

03.12.2007, 18:45

poochy

Auf diesen Beitrag antworten »

Rest Bestimmen (mit benutzung Satz von Fermat)

Nabend

smile

.

Die Aufgabe lautet:
Bestimmen Sie den Rest von 3^99 bei Division durch 17. (Hinweis: Satz von Fermat, geschickte Zerlegung von 99)

Der Satz von Fermat geht ja
$\begin{eqnarray*} n^{p-1} \equiv 1 (mod p) \end{eqnarray*}$

In diesem Fall wäre p ja die Primzahl 17.

Aber wie Nutze ich den Hinweis? Wie zerlege ich "geschickt" die 99?

Wäre um jeden Gedankenanstoß sehr dankbar.

03.12.2007, 18:49

AD

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 99 = 96+3 = 6\cdot (17-1)+3 \end{eqnarray*}$

Und dabei an die Potenzgesetze denken...

03.12.2007, 18:50

tmo

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 99 = 6 \cdot 16 + 3 \end{eqnarray*}$

edit: nächstes mal schneller tippen Augenzwinkern

Augenzwinkern

04.12.2007, 14:02

poochy

Auf diesen Beitrag antworten »

ok

das sieht ja schonmal ganz cool aus

danke

$\begin{eqnarray*} 3^{6(17-1)} \cdot 3^3 \end{eqnarray*}$

darüber bin ich ja schonmal glücklich

satz von fermat ist ja

$\begin{eqnarray*} n^{p-1} \equiv 1 (mod p) \end{eqnarray*}$

und dies p-1 haben wir ja oben im exponenten. Das seh ich alles, bloss weiß ich nicht wie jetzt der nächste schritt ist.

Soll ich jetzt damit arbeiten, dass der rest von $\begin{eqnarray*} 3^{(17-1)} \end{eqnarray*}$ 1 ist? und da wir das 6 mal haben der rest 6 ist? und dann nur noch 3^3 haben?
damit rest 33 zusammengezählt?
nochmal durch 17 und dann wäre der rest 16?

04.12.2007, 14:06

AD

Auf diesen Beitrag antworten »

Zitat:

Original von poochy
Soll ich jetzt damit arbeiten, dass der rest von $\begin{eqnarray*} 3^{(17-1)} \end{eqnarray*}$ 1 ist?

Ja.

Zitat:

Original von poochy
und da wir das 6 mal haben der rest 6 ist?

Nein! Ich hab oben nicht umsonst das Wort Potenzgesetze fallen lassen - denk mal an

$\begin{eqnarray*} a^{bc} = (a^b)^c \end{eqnarray*}$ .

04.12.2007, 14:08

poochy

Auf diesen Beitrag antworten »

doh ^^
also 3^6 * 3^3

?

edit: moment

mussi nochmal überdenken

smile

smile

rest 14?

Anzeige

04.12.2007, 14:42

AD

Auf diesen Beitrag antworten »

Herrje, ist denn das so schwer nach den Hinweisen:

$\begin{eqnarray*} 3^{(17-1)\cdot 6} = \left( 3^{(17-1)} \right)^6 \equiv 1^6 = 1\mod 17 \end{eqnarray*}$

04.12.2007, 14:49

poochy

Auf diesen Beitrag antworten »

naja ist ziemlich neu für mich unglücklich

unglücklich

sry

aber danke

04.12.2007, 15:16

poochy

Auf diesen Beitrag antworten »

rest 10

ja Big Laugh

Big Laugh

?

04.12.2007, 15:42

AD

Auf diesen Beitrag antworten »

Endergebnis $\begin{eqnarray*} 3^{99} \equiv 10 \mod 17 \end{eqnarray*}$ ist richtig. Freude

Freude

04.12.2007, 15:58

poochy

Auf diesen Beitrag antworten »

ich bin sooooooo gut Big Laugh

Big Laugh

05.12.2007, 09:16

newsys

Auf diesen Beitrag antworten »

warum lässt man hier die 3^3 weg???

$\begin{eqnarray*} 3^{(17-1)\cdot 6} = \left( 3^{(17-1)} \right)^6 \equiv 1^6 = 1\mod 17 \end{eqnarray*}$

05.12.2007, 09:22

AD

Auf diesen Beitrag antworten »

Weil man sich erstmal um ein Zwischenergebnis kümmert. Augenzwinkern

Augenzwinkern

05.12.2007, 09:27

newsys

Auf diesen Beitrag antworten »

Ok und auf rest 10 kommt man weil 3^3=27 und 27/17=1 rest 10 ?

05.12.2007, 09:28

AD

Auf diesen Beitrag antworten »

Richtig - also nochmal in aller Ausführlichkeit:

$\begin{eqnarray*} 3^{99} = 3^{16\cdot 6}\cdot 3^3 \equiv 1^6\cdot 27 \equiv 10 \mod 17 \end{eqnarray*}$

05.12.2007, 09:33

newsys

Auf diesen Beitrag antworten »

Super Danke!!!
Blumen

Blumen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »