a ≡ b, muss die Kongruenzgleichung stimmen?

Question

Aufgabe bzw. Problem/Ansatz:

Wenn jetzt beim Beweisen ein Gegenbeispiel zu a kongruent zu b dran ist. Muss dann die Kongruenzgleichung stimmen, oder? Also ich kann dann nicht Zahlen für a und b wählen, die nicht kongruent zueinander sind oder?

Comments

Was soll bewiesen werde?

---

Dass a² ≡ b² (mod m) gilt, dann gilt auch a ≡ b (mod m)

Answer 1

3^2 = 9  und 5^2 = 25   also 3^2 ≡ 5^2 mod 4, da 25=9+4*4

aber 3≡5 mod 4 gilt nicht, da es kein m∈ℤ gibt mit 5=3+4m.

Answer 2

Die Aussage

        \(\forall a,b\in \mathbb{Z}\ \forall m\in\mathbb{N}\setminus\{0\}\ \left(a^2 \equiv b^2\mod m \implies a\equiv b\mod m\right)\)

kann nicht bewiesen werden, weil sie nicht wahr ist.

Um sie zu widerlegen, genügt es, \(a,b\in \mathbb{Z}\) und \(m\in\mathbb{N}\setminus\{0\}\) so anzugeben, dass

        \(a^2 \equiv b^2\mod m\)

ist, aber

        \(a \not \equiv b \mod m\)

ist.

Grund ist:

1. Die Verneinung obiger Allaussage ist eine Existenzaussage. Existenzaussagen können bewiesen werden indem ein Beispiel dessen angegeben wird, wessen Existenz behauptet wird.
2. Eine Aussage der Form \(A\implies B\) ist genau dann falsch, wenn \(A\) wahr und \(B\) falsch ist.
   

Ein geeignetes Beispiel ist \(a=1\), \(b=-1\), \(m=3\).

Answer 3

Du kannst durch geschickte Umformung relativ schnell sehen, wieso hier etwas schiefgehen kann:

$$a^2\equiv b^2 \mod m \Leftrightarrow a^2-b^2 \equiv \boxed{(a+b)(a-b)\equiv 0 \mod m}$$

Jetzt siehst du sofort, dass wenn

\(a-b \not \equiv 0 \mod m\) gilt, trotzdem

\(a+b \equiv 0 \mod m\) sein kann und damit immer noch

\(a^2\equiv b^2 \mod m\) gilt.

Auf der Grundlage dieser Beobachtung kannst du nun ein Gegenbeispiel konstruieren. Das bekommst du bestimmt hin.