Kleines zahlentheoretisches Problem

Lieber Besucher, herzlich willkommen bei: MastersForum. Falls dies Ihr erster Besuch auf dieser Seite ist, lesen Sie sich bitte die Hilfe durch. Dort wird Ihnen die Bedienung dieser Seite näher erläutert. Darüber hinaus sollten Sie sich registrieren, um alle Funktionen dieser Seite nutzen zu können. Benutzen Sie das Registrierungsformular, um sich zu registrieren oder informieren Sie sich ausführlich über den Registrierungsvorgang. Falls Sie sich bereits zu einem früheren Zeitpunkt registriert haben, können Sie sich hier anmelden.

El_Marinero

Meister

Beiträge: 2 606

Beruf: GER

12.01.2010, 21:13

Kleines zahlentheoretisches Problem

Moin,

für einen Beweis fehlt mir folgender Zwischenschritt:
Seien x, y \in N
Offensichtlich gilt: Wenn x mod m != y mod m, dann ist x != y.
Ich möchte nun zeigen, dass für jede denkbare Kombination von x und y das kleinste m = m_min <= log(x+y) ist.

Das Argument hat irgendwas mit Primzahlen zu tun, aber ich werde aus meiner eigenen Mitschrift nicht ganz schlau.

Zum Seitenanfang

AtroX_Worf

Erleuchteter

Beiträge: 11 465

Wohnort: Hamburg

Beruf: GER

12.01.2010, 21:49

Was für ein m meinst du genau? Und ich schätze mal log2 meinst du, oder?

Wenn du eine Kombination x,y mit x|y nimmst, dann gilt doch die Voraussetzung nicht, welches m suchst du dann? Oder meinst du für jede Kombination (x,y), für welche die Voraussetzung gilt?

Meinst du wirklich Vor => x != y und nicht eher sowas wie x|y?

Zum Seitenanfang

El_Marinero

Meister

Beiträge: 2 606

Beruf: GER

12.01.2010, 22:16

Also, es geht darum zu zeigen: x!=y, ohne die Zahlen direkt zu vergleichen.

Wenn x!=y ist, dann gibt es mindestens ein m, so dass x mod m != y mod m, richtig?

Wenn es irgendein m gibt, dann gibt es auch ein kleinstes m = m_min. Zu zeigen ist jetzt, dass dieses m_min <= c \log(x+y) ist.
Und ja, der Logarithmus ist binär, spielt aber wegen dem c keine Rolle (hatte ich vergessen hinzuschreiben - sorry).

Zum Seitenanfang

AtroX_Worf

Erleuchteter

Beiträge: 11 465

Wohnort: Hamburg

Beruf: GER

12.01.2010, 22:54

m = 1 <= log2(1+1) erfüllt es immer.

Und wo ist dieses c?

€dit: ah, c*log2(x+y)

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »AtroX_Worf« (12.01.2010, 22:56)

Zum Seitenanfang

El_Marinero

Meister

Beiträge: 2 606

Beruf: GER

12.01.2010, 23:11

Hmm, stimmt, aber das ist nicht Sinn der Sache, bzw. es nützt so nichts. Dann stimmt vorher irgendwas nicht... ach kacke, man müsste seine eigene Schrift von vor 2 Jahren lesen können... sei es drum.

Zum Seitenanfang

El_Marinero

Meister

Beiträge: 2 606

Beruf: GER

12.01.2010, 23:21

Wahrscheinlich fehlte zusätzlich noch die Bedingung, dass
x mod m <= c log m und
y mod m <= c log m sein sollte.
Nur dann macht das Ganze wirklich Sinn.

Zum Seitenanfang