Beweis der Injektivität mit Modulo

09.06.2008, 00:04

aRo

Beweis der Injektivität mit Modulo

Hallo zusamme!

Nach dem schönen Sieg gegen Polen ruft leider wieder ein Arbeitsblatt, wo ich an einer Stelle leider klemme.

Ich möchte zeigen, dass eine Funktion injektiv ist.

genauer:
Die Funktion $\begin{eqnarray*} h_i(x)=(h^{\star}(x) + \frac{i(i+1)}{2}) mod 2^k \end{eqnarray*}$ für ein k größer gleich 1 soll so betrachtet werden: Man nehme x als fest an. Und betrachte die Funktion als Funktion über i. Für i werden Werte von 0..2^k-1 eingesetzt.
(die Funktion soll dann auf die Werte 0..2^k-1 abbilden).

Über $\begin{eqnarray*} h^{\star} \end{eqnarray*}$ ist weiter nichts bekannt.

Habt ihr da eine Idee? Ich hoffe die Informationen hier genügen.

Setze ich $\begin{eqnarray*} (h^{\star}(x) + \frac{i(i+1)}{2}) mod 2^k = (h^{\star}(x) + \frac{j(j+1)}{2}) mod 2^k \end{eqnarray*}$ müsste ich ja folgern dass i=j.

Irgendwie mag ich den Modulo da aber nicht. Wie kriege ich den geschickt weg? Augenzwinkern

09.06.2008, 00:45

Auf diesen Beitrag antworten »

Auf den Punkt gebracht willst du zeigen:

$\begin{eqnarray*} \frac{i(i+1)}{2} \equiv \frac{j(j+1)}{2} \mod 2^k \quad \Longrightarrow \quad i\equiv j\mod 2^k \end{eqnarray*}$

Na, dann versuch doch die linke Seite etwas umzuformen - in einem ersten Schritt z.B. so

$\begin{eqnarray*} 0 \equiv \frac{i(i+1)}{2} - \frac{j(j+1)}{2} = \frac{(i-j)(i+j+1)}{2} \mod 2^k \end{eqnarray*}$

Wie geht's jetzt wohl weiter? Augenzwinkern

09.06.2008, 01:09

aRo

Auf diesen Beitrag antworten »

guten Abend Arthur!

hm..naja, da $\begin{eqnarray*} i,j \in [0..2^k-1] \end{eqnarray*}$ kann $\begin{eqnarray*} \frac{(i-j)(i+j+1)}{2} \end{eqnarray*}$ kein Vielfaches von 2^k sein, muss also 0 sein.
Damit gilt $\begin{eqnarray*} i=-j-1 \vee i=j \end{eqnarray*}$

Die erste Lösung fällt aufgrund des Intervalls wieder flach und wir haben, was wir wollen.

Ein Problem gibt es allerdings:

Ich verstehe nicht recht, warum die Umformung, wie du sie gemacht hast, korrekt ist.

Es ist doch z.B. $\begin{eqnarray*} (9-7) mod M \neq 9 mod M - 7 mod M \end{eqnarray*}$

09.06.2008, 07:38

Auf diesen Beitrag antworten »

Zitat:

Original von aRo
Es ist doch z.B. $\begin{eqnarray*} (9-7) mod M \neq 9 mod M - 7 mod M \end{eqnarray*}$

Ja und? Ich habe nur

$\begin{eqnarray*} a \mod M = b \mod M \quad\Longrightarrow\quad a-b\equiv 0 \mod M \end{eqnarray*}$

benutzt, und diese Implikation kannst du mir gern widerlegen.

Zitat:

Original von aRo
hm..naja, da $\begin{eqnarray*} i,j \in [0..2^k-1] \end{eqnarray*}$ kann $\begin{eqnarray*} \frac{(i-j)(i+j+1)}{2} \end{eqnarray*}$ kein Vielfaches von 2^k sein, muss also 0 sein.

Das ist mir etwas schlecht begründet. Für den leicht veränderten Term $\begin{eqnarray*} \frac{(i-j)(i+j)}{2} \end{eqnarray*}$ wäre so eine Folgerung z.B. falsch - ebenso für $\begin{eqnarray*} (i-j)(i+j+1) \end{eqnarray*}$ .

09.06.2008, 09:39

aRo

Auf diesen Beitrag antworten »

Guten morgen!

Zitat:

Original von Arthur Dent

$\begin{eqnarray*} a \mod M = b \mod M \quad\Longrightarrow\quad a-b\equiv 0 \mod M \end{eqnarray*}$
benutzt, und diese Implikation kannst du mir gern widerlegen.

Ok, sehe ich doch ein.

Zur Begründung:
Hmm...aber die Begründung stimmt wenigstens. Wies besser, offensichtlicher, geht, sehe ich aber nicht.

Wenn ich mit sowas hier anfange:

$\begin{eqnarray*} \frac{(i-j)(i+j+1)}{2} = x \cdot 2^k \end{eqnarray*}$ komme ich ja in Teufelsküche... verwirrt

09.06.2008, 10:09

Auf diesen Beitrag antworten »

Das Wort "offensichtlich" wird offensichtlich manchmal verwendet, wenn man sich dann doch nicht ganz so sicher im Beweis ist... Augenzwinkern

Also: Warum klappt der Schluss z.B. für $\begin{eqnarray*} (i-j)(i+j+1) \end{eqnarray*}$ nicht?

09.06.2008, 10:41

aRo

Auf diesen Beitrag antworten »

jetzt hast du mich.

Ich habe nochmal ein bisschen rumgerechnet und gemerkt, dass das, was ich mir gestern gedacht habe, falsch war.
Ich habe nämlich gedacht, der Term könne nicht größer als $\begin{eqnarray*} 2^k-1 \end{eqnarray*}$ werden, aber da habe ich das Maximum natürlich genau auf der falschen Seite gesucht.

Wir haben auch noch keine Analysis mit zwei Variablen betrieben.

D.h. nun: Ich verstehe jetzt selbst nicht mehr, warum meine Behauptung doch gestimmt hat. Ich muss ja irgendwie zeigen, dass es jedenfalls kein ganzzahlig Vielfaches von 2^k werden kann und stecke schon wieder "in der Klemme"...

09.06.2008, 11:07

Auf diesen Beitrag antworten »

Na ich hatte in etwa sowas erwartet: $\begin{eqnarray*} \frac{(i-j)(i+j+1)}{2} \equiv 0\mod 2^k \end{eqnarray*}$ ist zunächst äquivalent zu $\begin{eqnarray*} (i-j)(i+j+1) \equiv 0\mod 2^{k+1} \end{eqnarray*}$ .

Da von den beiden Faktoren $\begin{eqnarray*} (i-j) \end{eqnarray*}$ und $\begin{eqnarray*} (i+j+1) \end{eqnarray*}$ nur genau eine gerade sein kann, muss diese dann auch durch $\begin{eqnarray*} 2^{k+1} \end{eqnarray*}$ teilbar sein. Für $\begin{eqnarray*} (i+j+1) \end{eqnarray*}$ ist dies jedoch wegen $\begin{eqnarray*} 1\leq i+j+1 \leq 2^k-1+2^k-1+1 = 2^{k+1}-1 \end{eqnarray*}$ nicht möglich, also ist es $\begin{eqnarray*} i-j \end{eqnarray*}$ , woraus $\begin{eqnarray*} i=j \end{eqnarray*}$ folgt.

09.06.2008, 11:20

aRo

Auf diesen Beitrag antworten »

ok, eingesehen.

danke dir!

Neue Frage »

Antworten »

Beweis der Injektivität mit Modulo

Verwandte Themen