Äquivalenzrelation und Äquivalenzklassen

21.11.2024, 23:23

Äquivalenzrelation

Äquivalenzrelation und Äquivalenzklassen

Hallo, ich habe eine Aufgabe zu Äquivalenzrelationen und Äquivalenzklassen zu bearbeiten wo ich nicht mehr weiterweiß. Die Aufgabe lautet so:

Bestimmen Sie für die folgenden Äquivalenzrelationen auf den natürlichen Zahlen N für jede Äquivalenzklassen einen Vertreter.

Dann gibt es mehrere Teile und bei diesem Teil habe ich jetzt ein Problem:

$\begin{eqnarray*} xRy \Leftrightarrow \end{eqnarray*}$ es existiert eine natürliche Zahl $\begin{eqnarray*} m \end{eqnarray*}$ sodass $\begin{eqnarray*} x*y-m^2 \end{eqnarray*}$ durch 13 teilbar ist.

In der Aufgabe steht zwar, dass wir uns Äquivalenzrelationen ansehen, aber handelt es sich hier tatsächlich um eine Äquivalenzrelation? Ich habe nämlich glaube ich etwas gefunden, was die Relation nicht transitiv macht und dann kann es ja keine Äquivalenzrelation mehr sein, oder?

Bei dieser Relation ist nämlich 1R13 da wir m=13 nehmen und dann $\begin{eqnarray*} 1*13-13^2=-156 \end{eqnarray*}$ haben und das ist durch 13 teilbar. Außerdem ist 13R2 da wieder m=13 ist und dann $\begin{eqnarray*} 13*2-13^2=-143 \end{eqnarray*}$ und das ist auch durch 13 teilbar. Also muss auch 1R2 sein, aber da finde jetzt einfach keine Möglichkeit etwas für m auszuwählen. Mit einer Tabelle habe ich das auch schon bis m=10000 ausgerechnet und es kam kein einziges passendes dabei raus.

22.11.2024, 08:24

Elvis

Auf diesen Beitrag antworten »

Die Frage läuft auf die Gleichung $\begin{eqnarray*} m^2=13k+2 \end{eqnarray*}$ hinaus, also auf die Frage, ob 2 quadratischer Rest Modulo 13 ist. Dem ist nicht so $\begin{eqnarray*} ^{(*)} \end{eqnarray*}$ , also zeigt dein Beispiel, dass die Relation nicht transitiv, also keine Äquivalenzrelation ist.

$\begin{eqnarray*} ^{(*)} \end{eqnarray*}$ 2. Ergänzungssatz zum quadratischen Reziprozitaetsgesetz: $\begin{eqnarray*} (\frac 2{13})=(-1)^{(13^2-1)/8}=(-1)^{21}=-1 \end{eqnarray*}$

22.11.2024, 13:21

HAL 9000

Auf diesen Beitrag antworten »

Sollte das schwere Geschütz Reziprozitätsgesetz gerade nicht verfügbar sein, so erfüllt auch die einfache Überprüfung von $\begin{eqnarray*} m^2\bmod 13 \end{eqnarray*}$ für $\begin{eqnarray*} m=0,1,2,3,4,5,6 \end{eqnarray*}$ diesen Zweck:

0,1,4,9,3,12,10

Keine 2 dabei, Ok.

Zitat:

Original von Äquivalenzrelation
Mit einer Tabelle habe ich das auch schon bis m=10000 ausgerechnet und es kam kein einziges passendes dabei raus.

Die Mühe hättest du dir sparen können:

Wenn es für $\begin{eqnarray*} m \end{eqnarray*}$ nicht klappt, dann weder für
a) $\begin{eqnarray*} -m \end{eqnarray*}$ noch für
b) $\begin{eqnarray*} m+13n \end{eqnarray*}$ für beliebige ganzzahlige $\begin{eqnarray*} n \end{eqnarray*}$

Begründung:

a) $\begin{eqnarray*} xy-m^2 = xy-(-m)^2 \end{eqnarray*}$
b) $\begin{eqnarray*} xy - (m+13n)^2 = xy-m^2 - 13n(2m+13n) \end{eqnarray*}$ lässt den selben Rest bei Division durch 13 wie $\begin{eqnarray*} xy-m^2 \end{eqnarray*}$

Was letztlich heißt, dass man nur $\begin{eqnarray*} m=0,1,2,3,4,5,6 \end{eqnarray*}$ überprüfen muss - wenn's da nicht klappt, dann nie.

Neue Frage »

Antworten »

Äquivalenzrelation und Äquivalenzklassen

Verwandte Themen