Teilbarkeit und Reste/Modulo Aufgaben

Question

Aufgabe:

1. $$\text{ Ist die zahl } 3^{139} \text{ durch 15 teilbar? }$$

2.  $$77^{17} \equiv z\text{ } (mod 19)\text{ Für welche z ist dies erfüllt? }$$

3. $$\text{ Berechnen Sie den Rest(} 2^{167} \text{) bzgl. der "basis" 83 } $$

Problem/Ansatz:

Bei diesen 3 Aufgabentypen habe ich keine Idee wie ich mit diesen riesigen Potenzen umgehen soll.. Wir sollen diesen Aufgabentyp per Vereinfachung der Potenzen lösen.. Da frage ich mich aber wie genau ich das schaffen solle? Hat da jemand eine Idee?

Answer 1

Eine Zahl, die durch 15 teilbar sein soll, braucht in ihrer Primfaktorzerlegung mindestens einen Faktor 3 und mindestens einen Faktor 5. Ist das hier erfüllt?

Da 76 durch 19 teilbar ist, gilt \(76 \equiv 0 mod 19\) und demzufolge  \(77 \equiv 1 mod 19\).

Was hat das für Auswirkungen auf 77ⁿ ?

Nach dem kleinen Satz von Fermat gilt

\(2^{82}\equiv 1 mod 83\)

Ziehe Schlussfolgerungen für \(2^{164}\) und für  \(2^{167}=2^{164}\cdot 8\).

Comments

1. Also ist es nicht möglich zu teilen. Weil die 3 eine Primzahl ist und nicht mit der 5 dargestellt werden kann

2. Die Gleichung wäre für z = 1 erfüllt, weil bei Modul-Gleichungen gilt: 77^n kongruent 1^n mod19, was wieder 1 ergibt.

3. Den Satz kannte ich noch gar nicht, war kein Teil der Vorlesung

Stimmen die Antworten 1,2?

---

2) ist unvollständig.

Lösung ist nicht nur 1, sondern jede ganze Zahl z, für die  \(z \equiv 1 mod 19\) gilt.

Bei 1) hast du was verwechselt. Richtig wäre:

Weil die 5 eine Primzahl ist und nicht mit der 3 dargestellt werden kann

---

2) Stimmt daran habe ich nicht gedacht!

1) Die Potenz ist ja als Basis die 3, also wäre das 3*3*3*...*3 (139 mal eben) die Zahl die es durch 15 zu teilen gilt. Da der Faktor 5 allerdings nicht auftaucht gibt es kein 3*5 was 15 wäre und somit nicht geteilt werden kann. Stimmt das so etwa nicht?