Wie kann man modulo berechnen? Beispiel 3^8 mod 17

Question

 

ich hab Probleme beim modulo 

wie kann ich  ( 3⁸ mod 17 ) berechnen ? mit welcher Methode muss man berechnen ? 

vg 

Maria 

Comments

Eine Methode ist: 3⁸ = 6561 = 385·17 + 16.

---

und wie geht weiter ? ich meine wie lautet dann die Antwort ? 

---

\(\)1\(\)6\(\)

---

hmm 385.17 <- die 17 hier ist was in der Frage steht oder? denn ich brauche der kleinste positive Rest

danke dir :)

Answer 1

Hm hier kannst du es ja noch simpel lösen:

3⁸=6561

6561/17=385,94

-> 385*17=6545

6561-6545=16

Der Rest ist also 16.

Comments

danke dir aber ist das der kleinste positive Rest ? 

vg

---

3⁸ ≡ (3²)⁸ ≡ 9⁸ ≡ (-1)⁴ ≡ 1

Meinst du diesen Lösungsweg?

---

also in der Frage steht einen Hinweis : Beachten Sie auch Satz 2.20, der allerdings in dieser Form im allgemeinen nur für Primzahlen p angewendet werden kann.

Mit dem Satz 2.20 gemeint ist : Der kleine Satz von Fermat 

und wir müssen der kleinste positive Rest angeben

---

Der kleine Satz von Fermat ist ja:

a^p-1 ≡ 1 (mod p)

wobei p eine Primzahl ist.

Hier:

3⁸ = (3²)⁴ =9⁴ 

Jetzt Fermats kleinen Satz anwenden:

9⁴ ≡ 9^5-1 ≡ 1 (mod 5)

Der kleinste positive Rest ist also 1, wie ich es in meiner vorigen Rechnung schon gelöst habe.

---

Hallo Frontliner: Der Modul soll 17 sein!

Abgesehen davon sind deine Rechnungen
in den Kommentaren völlig konfus, bitte mal durchsehen!

---

Oh tut mir leid. Ich hatte die ganze Zeit gedacht, der Modul sei 5 . Mein Fehler.

Bei 17 gibt es verschiedene Arten vorzugehen. Beispiel:

3³ ≡10

3⁴=10*3³ ≡13

3⁵ ≡ 13*3 ≡ 5

3⁸ ≡ 5*3³ ≡ 5*10≡50≡16

Sorry für die Verwirrung die ich gestiftet hab ;)

---

@Frontiner: kein Problem!

Weiter möchte ich nun mal wissen, welcher Terrorist meinen Kommentar oben mit einer Spam-Markierung versehen hat! Das empfinde ich als absolute Unverschämtheit!

---

So, hier mal ein Versuch mit dem kleinen Satz von Fermat:
$$ 3^8 = 9^4 \equiv (-8)^4 = 2^{12} = -(-1)\cdot 2^{12} \\\equiv -16 \cdot 2^{12}  = -2^{17-1} \equiv -1 \equiv 16 \mod 17. $$(Ich hoffe, die Rechnung ist nachvollziehbar.)

Answer 2

Hi, ein möglicher Rechenweg zum kleinsten positiven Rest ist dieser:
$$ 3^8 = 81^2 = \left(85-4\right)^2 \equiv 16 \mod 17. $$