Äquivalenzumformungen bei Kongruenzen

Question

Aufgabe:

Weisen Sie durch Äquivalenzumformungen nach, dass das Folgende gilt:

\( 15.920 .340 .683 .584 .346.302.566.262.408^{9} x \equiv 32 \bmod 10 \quad \Longleftrightarrow \quad x \equiv 4 \bmod 5 \)

Problem/Ansatz:

Kann mir mal jemand bei dieser Aufgabe helfen? Egal wie ich es angehe, ich bekomme nie die richtige Lösung raus

Answer 1

Wer bei Teilung durch 10 den "Rest" 32 lässt, der lässt bei Teilung durch 10 eigentlich den Rest 2. Und wer bei Teilung durch 10 den Rest 2 lässt, lässt auch bei Teilung durch 5 den Rest 2.

Und wegen

 \( 15.920 .340 .683 .584 .346.302.566.262.408  \equiv 3 \bmod 5  \)

gilt auch

\( 15.920 .340 .683 .584 .346.302.566.262.408^{9}  \equiv 3^9 \bmod 5 \ \)

Dann gilt natürlich auch \( 15.920 .340 .683 .584 .346.302.566.262.408^{9} x \equiv 3^9 x\bmod 5 \ \).

Kannst du \( 3^9 \bmod 5 \ \) ausrechnen?

Comments

Warum muss ich 3^9 mod ausrechnen?

---

8^ 9x≡32 mod 10

Kann ich nicht nur diesen Teil rechen ?

---

Ja, du kannst nur \( 8^9 x \equiv 32 \bmod 10 \) berechnen. Da \( 8^9 \equiv 8 \bmod 10 \) und \( 32 \equiv 2 \bmod 10 \), ergibt sich \( 8x \equiv 2 \bmod 10 \). Durch Vereinfachen erhält man \( x \equiv 4 \bmod 5 \).

---

Text erkannt:

\( \begin{array}{rlrl}53.277 .864 .763 .929 .637 .549 .646^{7} x & \equiv 22 \bmod 10 & & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6^{7} x & \equiv 22 \bmod 10 & & \mid T \\ \Leftrightarrow 6^{6} \cdot 6 x & \equiv 22 \bmod 10 & & \mid T \\ \Leftrightarrow\left(6^{2}\right)^{3} \cdot 6 x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 36^{3} \cdot 6 x & \equiv 22 \bmod 10 & & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6^{3} \cdot 6 x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 6^{4} x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow\left(6^{2}\right)^{2} x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 36^{2} x & \equiv 22 \bmod 10 & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6^{2} x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 36 x & \equiv 22 \bmod 10 & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6 x & \equiv 42 \bmod 10 & \mid \text { Proposition 2.9.9 (3.) für } k=6 \\ \Leftrightarrow x & \equiv 7 \bmod 5 & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow x & \equiv 2 \bmod 5 & & \end{array} \)

Beim Tutorium haben haben wir eine ähnliche Aufgabe gerechnet, und dazu haben sie uns folgende Lösungen gegeben. ( so sollten wir es rechnen)

---

Es kommt doch darauf an, was in Prop. 2.9.9. steht, die kennen wir nicht. Wie lautet die?

Answer 2

In Kurznotation:

\(15920340683584346302566262408^{9}\equiv_{10} (-2)^9 \equiv_{10} -512 \equiv_{10} -2 \)

Deine Gleichung ist also äquivalent zu: \(-2x\equiv_{10} 2\), das ist äquivalent zu \(-x\equiv_{5}1\).

Die Gleichung multiplizieren wir mit der Einheit \(-1\) bzw. \(4\) und erhalten \(x\equiv_5 4\).

Comments

Text erkannt:

\( \begin{array}{rlrl}53.277 .864 .763 .929 .637 .549 .646^{7} x & \equiv 22 \bmod 10 & & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6^{7} x & \equiv 22 \bmod 10 & & \mid T \\ \Leftrightarrow 6^{6} \cdot 6 x & \equiv 22 \bmod 10 & & \mid T \\ \Leftrightarrow\left(6^{2}\right)^{3} \cdot 6 x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 36^{3} \cdot 6 x & \equiv 22 \bmod 10 & & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6^{3} \cdot 6 x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 6^{4} x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow\left(6^{2}\right)^{2} x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 36^{2} x & \equiv 22 \bmod 10 & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6^{2} x & \equiv 22 \bmod 10 & \mid T \\ \Leftrightarrow 36 x & \equiv 22 \bmod 10 & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow 6 x & \equiv 42 \bmod 10 & \mid \text { Proposition 2.9.9 (3.) für } k=6 \\ \Leftrightarrow x & \equiv 7 \bmod 5 & \mid \text { Proposition 2.9.9 (1.) } \\ \Leftrightarrow x & \equiv 2 \bmod 5 & & \end{array} \)

Laut dem Tutoriumsmusterlösungen. Sollen wir die Aufgabe so rechnen könntest du mir Dabei helfen die Aufgabe, so zu rechnen

---

Man kann damit runter moden ( mit der mod 10)

---

Die Musterlösung macht auch nicht viel anderes, nur dass sie seeeeeehr umständlich das \(6^7\) vereinfacht. Sobald man sieht, dass \(6^2=36\equiv_{10}6\) folgerst du, dass für alle positiven Potenzen \(k\) gilt \(6^k\equiv_{10}6\). Am Ende kommen sie dann bei einer etwas anderen Gleichung (drittletzte Zeile), die dann auch mit der Kürzungsregel aufgelöst wird.

(Man muss übrigens nicht alles immer wie die Musterlösung machen. Die sind meistens ziemlich unintelligent, schreibintensiv und fast nie die beste Lösung sondern nur die, wo man absolut nichts falsch machen kann. Trau dir mehr zu :p )

Answer 3

Der Anfang könnte so aussehen:$$ \begin{aligned} 15.920.340.683.584.346.302.566.262.408^{9} x &\equiv 32 \bmod 10 \quad\vert\quad\textrm{Proposition 2.9.1(1.)}\\ \Leftrightarrow 8^9x &\equiv 32 \bmod 10 \quad\vert\quad\textrm{T}\\ \Leftrightarrow (2^3)^9x &\equiv 32 \bmod 10 \quad\vert\quad\textrm{T}\\ \Leftrightarrow (2^9)^3x &\equiv 32 \bmod 10 \quad\vert\quad\textrm{T}\\ \Leftrightarrow (512)^3x &\equiv 32 \bmod 10 \quad\vert\quad\textrm{Proposition 2.9.1(1.)}\\ &\dots \end{aligned} $$

(noch etwas korrigiert)

Comments

Wie kommst du auf die dritte Zeile (2^3)^9x  woher kommt die 2

---

\( 8 = 2^3 \)

---

Danke dir, ich hab glaube einfach zu kompliziert gedacht,