Lösung dieser Aufgabe mit Hilfe einer linearen Kongruenz

Question

Aufgabe \( 3- \) lineare Kongruenzen

In der METHODISCH GEORDNETEN AUFGABENSAMMLUNG aus dem Jahre 1880 befindet sich fol-
gende Aufgabe:

Multipliziert man eine ganze Zahl mit 71 und eine zweite ganze Zahl mit \( 21, \) so ist das
erste Produkt um 10 gröser als das zweite. Wie heißen diese Zahlen?

a) Begründen Sie, dass die Lösung dieser Aufgabe mit Hilfe der linearen Kongruenz
$$ 71 x \equiv 10 \quad(\bmod 21) $$
bestimmt werden kann.

b) Weisen Sie nach, dass diese Kongruenz lösbar ist. Ermitteln Sie anschließend alle \( x \in \mathbb{Z} \), welche diese Kongruenz erfüllen. Geben Sie die drei größten negativen ganzen Zahlen an, welche die Kongruenz erfüllen.

c) Untersuchen Sie, ob es unter den ersten 50 natürlichen Zahlen zwei gibt, welche die ursprüngliche Aufgabe lösen.

Answer 1

Lösbar genau dann, wenn ggT(71,21) die 10 teilt. Das ist der Fall, da ggT(71,21)=1.

\(71x=10 \pmod{21} \Leftrightarrow 50x\equiv 10 \pmod{21} \Leftrightarrow 10\equiv 2\, \operatorname{mod}\left(\frac{21}{\operatorname{ggT}{(5,21)}}\right) \\ \Leftrightarrow 10x \equiv 2 \pmod{21} \Leftrightarrow x\equiv 2(10)^{-1}\pmod {21}\).

Wir suchen nun das Inverse von \(10\) modulo \(21\) (geschrieben \(10^{-1}\). Das machst du mit dem Lemma von Bezout und dem erweiterten euklidischen Algorithmus.

Comments

meine Lösung wäre 17+21k also aber was sollen dann bitte die drei größten negativen zahlen sein?

---

Welche restriktiven Eigenschaften kannst du denn aus dem Urproblem ableiten?

---

meine Lösung wäre 17+21k also aber was sollen dann bitte die drei größten negativen zahlen sein?

17 - 21 = -4
-4 - 21 = -25
-25 - 21 = -46

Die drei größten negativen Zahlen sind also -4, -25 und -46.

---

alles gut, hatte einen Denkfehler bezüglich dessen was die drei größten negativen Zahlen sind