Kongruenzen begründen ohne Taschenrechner? Bsp. 23^13 ≡ 2 (mod 21)

Question

Begründe nur mit Hilfe von Rechenregeln für Kongruenzen, ohne einen Taschenrechner zu benutzen. Die dabei verwendeten Rechenregeln sind anzugeben.

a) 17 | (69^1234567 − 1)

b) 2^12 ≡ 1 (mod 21)

c) 23^13 ≡ 2 (mod 21) 

Comments

Hi, b) ist offfensichtlich falsch. Überprüfe deine Angaben!

---

Oh nein!!! Die Zahlen wurden nicht hochgestellt! Sorry!

Hier nochmal die richtigen Aufgaben:

17 | (69^1234567 − 1)

b) 2¹² ≡ 1 (mod 21)

c) 23¹³ ≡ 2 (mod 21) 

Danke schon mal für eure Hilfe!

---

$$69\equiv 1 \mod 17$$

$$\varphi(21)=2\cdot 6 =12$$

$$23 \equiv 2 \mod 21$$ und fertig isses.

---

Soweit ich die Aufgabe verstehe, sollen die Kongruenzen auch nicht berechnet, sondern lediglich durch die Rechengesetze von Kongruenzen wie:

a≡b (mod n) ⇒ a + c ≡ b +c (mod n)

und

a≡b (mod n) ⇒ a *c ≡ b *c (mod n)

begründet werden...

---

Aber wie kommt man auf dieses Zeichen vor der 21?

und wie kann ich begründen, dass man die Potenzen weglassen kann?

---

Eulersche phi-Funktion und Satz von Euler(-Fermat)

Answer 1

Die erste Aufgabe ist also, zu zeigen, dass \(17\mid 69^{1234567}-1\).

Dazu musst du zeigen, dass \(69^{1234567}\equiv 1 \mod 17\).
Es gilt: \(17\mid 68\), also \(69\equiv 1\mod 17\). Damit hast du jetzt fast schon die Lösung für die erste Aufgabe. Die anderen zwei gehen ähnlich.

Answer 2

691234567 − 1=691234566  davon 680000000 abziehen gibt (68=4*17)

11234566     davon  10200000  ( denn 102 ist 6*17)

1034566   davon 1020000 abziehen

14566    davon  13600    (136=8*17)

9566   davon 8500 abziehen

1066  davon  1020 abziehen

46   ??????????   Die Zahl ist nicht durch 17 teilbar !

oder ich hab mich verrechnet.

Comments

Und ich dachte ich hab was übersehen

a) 691234566 ≡ 14 (mod 17) 

b) 212 ≡ 2 (mod 21)

c) 2313 ≡ 3 (mod 21)

---

14.566-13.600=966

ändert aber nichts daran, dass die Aussage falsch ist und das trotzdem kaum ohne TR lösbar ist.

---

EDIT: Die Hochstellungen wurden anscheinend vergessen. Vgl. Kommentare oben.

Answer 3

Alle drei sind falsch.

Ist die Frage richtig wiedergegeben? Denn: falsche Kongruenzen sind nicht begründbar.

(Und die Begründung, dass die erste falsch ist, ist deutlich schwerer als die anderen zwei.)

Comments

Die Hochstellungen wurden anscheinend zuerst mal vergessen. Vgl. Kommentare oben. 

---

Wie kommt die Spammarkierung da hin?Das ist eine richtige Antwort auf die gestellte Frage. Nur weil die Frage falsch gestellt war ist das doch nicht Spam.Da ist es deutlich mehr Spam das Nick.. als Antwort das nochmal schreibt was als kommentar bereits  von mir oben geschrieben wurde.Seltsames Forum hier.

---

Weiss ich nicht; ich hatte sie vorher gerade aufgehoben.