Eine Menge von n ganzen Zahlen ist ein vollständiger Rest modulo n, wenn keine zwei Elemente kongruent mod n sind.

Eine Menge von n ganzen Zahlen ist ein vollständiger Rest modulo n, wenn keine zwei Elemente kongruent mod n sind.

Ich verstehe den Satz, aber wie beweise ich ihn? Jede Hilfe wäre willkommen!

Mein Versuch.

Satz 3.17 besagt

Sei n eine natürliche Zahl. Jede Menge {a1,a2,...,an} von n ganzen Zahlen, für die keine zwei kongruent sind, ist ein vollständiges Residuensystem modulo n.

Intuitiv ergibt dies Sinn, wenn keine zwei kongruent sind, dann haben sie alle unterschiedliche Reste .

Beweis durch Widerspruch unter Anwendung des Schubfachprinzips (habe es noch nie in einem Beweis verwendet).

Angenommen, wir haben eine Menge von n ganzen Zahlen, nennen sie A={a1,a2,...an}, in der keine zwei modulo n kongruent sind, und nehmen wir an, wir haben eine Restmenge R={r1,r2...rn-1 } wobei wir weniger als n Reste haben.

Da a1 zu keinem ai für 1 kongruent mod n ist

Da a2 zu keinem ai für 2 kongruent mod n ist

Nun ist an nicht kongruent zu irgendeinem ai mod n für irgendein 1<=i<=n-1, also nach DA, an=n(qn)+rn, was impliziert, dass an kongruent zu rn mod n ist, aber dies ist unmöglich, da R weniger als n Elemente (Reste) hat, also ist an für einige n<=i<=1 mit einem ai kongruent, aber dies widerspricht, dass an mit keinem ai kongruent ist.

Dies wird normalerweise als "vollständiges Rückstandssystem" bezeichnet und oft als eine Reihe von definiert N ganze Zahlen ohne zwei kongruente mod N . Wenn Sie gebeten wurden, dies zu beweisen, wurde Ihnen wahrscheinlich eine andere Definition von "vollständiges Rückstandssystem" zur Verfügung gestellt. Welche Definition hast du?
Schubladenprinzip?
Mein Buch sagt, dass jede ganze Zahl (in Z) nur zu einem und nur einem Element in meiner Menge von n ganzen Zahlen kongruent ist!
Es folgt die Verwendung der Division mit Rest, um zu zeigen, dass jedes Element kongruent zu einer eindeutigen der Zahlen {0,1, ..., n-1} ist, und dann die Verwendung der Division mit Rest, um zu sagen, dass jede ganze Zahl kongruent zu einer eindeutigen ist diese.
Ok, was Sie sagen, ist, dass jeder Rest einzigartig sein wird? Und damit sind alle ganzen Zahlen überhaupt nicht kongruent zueinander?
Ich würde nicht sagen "und daher sind alle ganzen Zahlen überhaupt nicht kongruent", da es sich wie eine Deduktion anhört. Das ist kein Abzug, sondern eine Wiederholung Ihrer Hypothese, dass "keine zwei Elemente modulo n kongruent sind". Aber ja, diese Hypothese impliziert, dass "jeder Rest einzigartig sein wird".
Der tatsächliche Beweis hängt stark davon ab, wie formell Sie vorgehen (zum Beispiel, was ist die Definition von „Eine Menge von N ganze Zahlen?") Aber im Grunde ist das Argument der Divisionsalgorithmus und das Schubladenprinzip.
Ich habe also nie wirklich mit dem Schubladenprinzip gearbeitet, um ehrlich zu sein, glaube ich nicht, dass ich damit arbeiten könnte. Ich kann das absolut handgewellt beweisen, aber die Verwendung des Pidgeon-Loch-Prinzips würde mich umbringen
Das Schubladenprinzip ist eigentlich vielleicht die am einfachsten zu beschreibende Beweistechnik, die es gibt. (Die Verwendung kann manchmal schwierig sein, aber hier gibt es keinen Trick.) Scheuen Sie sich nicht, es zu verwenden. Lassen Sie Ihre Menge von n ganzen Zahlen die Tauben sein, und lassen Sie die Menge der Reste, die sie ergeben, wenn sie durch n dividieren, die Taubenlöcher sein. Nehmen Sie, um einen Widerspruch zu erreichen, an, dass diese Menge von Resten nicht {0, 1, 2, ..., n-1} ist, also weniger als n Elemente hat. Jetzt können Sie das Schubladenprinzip anwenden und einen Widerspruch erreichen.
Ich sehe nicht, wo Sie das Schubladenprinzip anwenden. Ich würde Folgendes ändern: Lassen Sie R speziell die Menge der Reste sein, wenn Sie jeden davon dividieren A 1 , … , A N von n. Nehmen Sie, um einen Widerspruch zu erreichen, an, dass die Menge R weniger als hat N Elemente. Verwenden Sie dann das Schubfachprinzip mit den Elementen von R als Löcher und Elemente A 1 , … , A N wie die tauben kannst du das entscheiden...

Antworten (1)

Wenn v = r mod n und w = r mod n, dann ist v = w mod n.

Per Definition ist ein vollständiger Rest modulo n eine Menge von n ganzen Zahlen { R ich } wobei keine zwei zueinander kongruent sind. Was wir beweisen müssen, ist, dass jede andere solche Menge { S ich } von n ganzen Zahlen ist ebenfalls ein vollständiger Rest.

Also { R ich } ein vollständiger Rest zu sein bedeutet, jedes S ich = R J Mod N für einige R J . Andere S k Wo S k ≠ S ich ist für manche deckungsgleich R l . Wenn R l = R J Die S ich ein S k zueinander deckungsgleich sind. Also jeder S k ist deckungsgleich mit einem anderen R J und damit jeder S ich ist in einer eindeutigen Kongruenzklasse und als { R ich } stellt alle Klassen dar und es besteht eine direkte Entsprechung zwischen { R ich } Und { S ich }, { S ich } ist ein vollständiger Rest.

Eine Menge von n ganzen Zahlen ist ein vollständiger Rest modulo n, wenn keine zwei Elemente kongruent mod n sind.
AntwortenHierDatenschutz-Bestimmungen1y, 0v