MastersForum

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.

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).

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.

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.