Subtraktion von Restklassen?

Schönen guten Tag,

Restklassen sind eigentlich kein schwieriges Thema, jedoch machen mich die ganzen Beweise fertig, da ich dafür einfach keine passende Herangehensweise zu finden scheine. Da ich bei folgender Aufgabe wirklich gar nicht weiterkomme, wollte ich euch zu Rate beten, ob ihr mehr wisst als ich. :D

Die Frage ist folgende. Es gilt a≡b (mod n) und c≡d(mod n). Zeigen Sie dass dann auch gilt: a-c ≡ b-d (mod n).

Mir fällt es bei solchen Beweisen einfach super schwer, den Anfang zu finden. Das heißt ich weiß nicht einmal nach was ich das Ganze umstellen soll, oder wie auch immer. Ich dachte mir, dass dies eventuell mit der Tatsache zu beweisen geht das für die kongruenz von Restklassen folgendes gilt: wenn a≡b (mod n), so gilt auch: n | a - b, aber wie schon erwähnt habe ich einfach keine Idee auf was das letztendlich hinauslaufen soll.

lg John

2 Antworten

Quotenbanane

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

25.05.2021, 17:11

a≡b (mod n) heißt nichts anderes, als dass es eine ganze Zahl q gibt, sodass a = q*n + b.

Äquivalent dazu gibt es für c≡d(mod n) eine ganze Zahl p, sodass c = p*n + d

Jetzt müsstest du selbst weiter wissen.

Woher ich das weiß:Studium / Ausbildung – Mathematik-Studium

Klossar086000

Beitragsersteller

26.05.2021, 12:46

Vielen Dank für ihre Antwort. Sie hat mir auf jeden Fall erst einmal in sofern weitergeholfen, dass ich jetzt weiß, um das Ganze beweisen zu können muss es eine Zahl x geben für die gilt a-c = x*n + b-d.

Mit der Gleichung die sie oben hergeleitet haben, komme ich jedoch nicht darauf, da sich das n, welches ich ja benötige immer wegkürzt und daher wollte ich sie um einen weiteren Denkanstoß beten. :)

Quotenbanane

26.05.2021, 12:56

@Klossar086000

da sich das n, welches ich ja benötige immer wegkürzt

??? Inwiefern kürzt sich das n weg.

Offenbar kann man die Gleichung zu a - c = q*n - p*n + b - d umstellen.

Klossar086000

Beitragsersteller

27.05.2021, 13:02

@Quotenbanane

Entschuldigen Sie, ich hatte hier einen fatalen Denkfehler.

Danke trotzdem für ihre Antwort!

Quotenbanane

27.05.2021, 14:12

@Klossar086000

Kein Stress, mittlerweile müsstest du sicher draufgekommen sein, dass a - c = n*(q - p) + b - d sich zu a-c = b-d mod n umwandeln lässt.

Klossar086000

Beitragsersteller

30.05.2021, 12:57

@Quotenbanane

Ja korrekt. Vielen Dank nochmals für ihre Hilfe.

eterneladam

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

25.05.2021, 17:09

Wenn a ≡ b (mod n), dann a-c ≡ b-c (mod n), das ist trivial.

Und weiter a-c ≡ b-c ≡ b-d (mod n).

Ähnliche Beiträge

Äquivalenzrelation Modulo Division?

Folgende Aufgabe:

Sei m ∈ N. Beweisen Sie, dass die Relation

𝑅 = {(a, b) ∈ Z × Z ∣ a ≡ b (mod m)}

eine Äquivalenzrelation i

n Z ist!

----------------------------------------------------------

Eine Äquivalenzrelation muss ja folgende Eigenschaften aufweisen:

symmetrisch, reflexiv, transitiv

Reflexiv: Jede Zahl steht mit sich selbst in Relation und lässt bei Division durch m logischerweise den selben Rest (da es ja die selbe Zahl ist) --> Kann man das beweisen oder würde da dieser Antwortsatz reichen?
∀a ∈ Z : a ≡ a(mod m) -

Symmetrisch: Bei der Modulo Schreibweise handelt es sich ja um eine Kongruenz, welche beidseitg ist. Also a ≡ b (mod m) ist äquivalent zu b ≡ a (mod m)
∀a,b ∈ Z : a ≡ b(mod m) ⇒ b ≡ a(mod m)

Transitiv: ∀a, b, c ∈ Z : a ≡ b(mod m) und b ≡ c(mod m) ⇒ a ≡ c(mod m)

Das wäre ja die allgemeine Defintion. Wie kann man aber transitiv allgemein beweisen?

Mir geht es mehr darum, wie man sowas allgemein beweisen kann. Bei Reflexivität weiß ich, dass es so ist, aber wie beweißt man das?

a ≡ b(mod m)⇔∃k∈Z∶ a-b=k*m <-- So könnte man die Äquivalenz auch ausdrücken

...zum Beitrag

Wie wurde hier bewiesen/umgeformt (Modulo)?

Hallo, ich habe die folgende Folie

Ich habe, wie man sieht schon selbst etwas drauf geschrieben, aber manches verstehe ich einfach nicht.

1) Warum gilt diese Äquivalenz (ich habe es in schwarz aufgeschrieben, über den Fragezeichen)? Also wieso ist (a mod m) mod m = a mod m?

2) Wie kommt man auf diese Kongruenzen ? bzw wieso ist die summe von a_i mod 3 = 0?

Ich hoffe meine Fragen sind verständlich? Falsch nicht bitte schreiben und ich versuche es erneut:) Mir ist es aber sehr wichtig dies hier zu verstehen

...zum Beitrag

Wenn p eine Primzahl ist, dann gilt 2^(2p-2)≡ 1(mod 2^(p)-1)?

Wie Beweise ich das?

...zum Beitrag

Restklasse vom Binomialkoeffizienten?

Hallo allesamt :)

ich habe Folgendes im Buch

104 Number Theory Problems

von Titu Andreescu, Dorin Andrica, Zuming Feng

gesehen:

Warum wird hier der Binomialkoeffizient so angeschrieben,

und es kommt zuerst 1 raus, woraus aber gefolgert wird, dass es 2 mod 4 ist…

Warum, was ist das für eine Regel?

...zum Beitrag

Wie beweise ich den Satz von Euler?

a^phi(n) mod n ist kongruent zu 1. (wobei die 1 hier nicht der Rest ist oder? Ist ja eine Kongruenz)

Also ist das doch das Gleiche wie a^phi(n) mod n = 1 mod n?

Ich persönlich habe es glaube ich verstanden, aber wie begründe ich das mathematisch korrekt? Das Internet hat mir da bis jetzt nicht weitergeholfen. Ich müsste ja also eigentlich beweisen, dass zwei teilerfremde Zahlen kongruent zu 1 sind oder? Vor allem darf der Beweis nicht zu lang sein.

Ich danke euch schon einmal sehr stark, wenn ihr mir helfen könnt. Das ist so das Hauptding, bei dem ich gerade noch in meiner Seminararbeit hänge.

...zum Beitrag

Beweis modulo m?

Seien x, y, r, s ∈ℤ und m ∈ℕ. Zeigen Sie: Wenn x Ξ r mod m und

y Ξ s mod m gilt, dann folgt x + y Ξ r + s mod m.

kann ich einfach folgendes machen:

x+y= r mod m + s mod m

= (r+s) mod m

also praktisch aber dieses mod m ausklammern?

...zum Beitrag

Beweis durch strukturelle Induktion?

Wir haben folgende Funktionen:

prod :: [Int] -> Int

prod [] = 1 -- prod.1

prod (x:xs) = x * prod xs -- prod.2

foldl :: (b -> a -> b) -> b -> [a] -> b

foldl f acc [] = acc -- foldl.1

foldl f acc (x:xs) = foldl f (f acc x) xs -- foldl.2

Aufgabe:

Man soll mit struktureller Induktion beweisen, dass folgende Aussage gilt:

foldl (*) 1 xs = prod xs

Ich habe momentan:

foldl (*) 1 xs = prod xs

I.A. (xs = []):

foldl (*) 1 [] = prod []

foldl f acc [] = acc prod [] = 1 -- foldl.1 & plod.1

foldl f 1 [] = 1

1 = 1

I.V.: Wir nehmen an, dass die Aussage gilt für ein beliebiges xs

I.S. (xs -> x:xs):

foldl (*) 1 (x:xs) = prod (x:xs) -- foldl.2 & prod.2

foldl (*) ((*) 1 x) xs = x * prod xs

Problem: Ich weiß nun nicht wie ich mit dem Induktionsschritt fortfahren soll.

...zum Beitrag

Struktuelle Induktion auf Bäumen?

Aufgabe:

Betrachten wir die folgenden Funktionsdefinitionen :

data Tree a = Leaf a | Node a (Tree a) (Tree a)

sumLeaves :: Tree a -> Integer

sumLeaves (Leaf x) = 1

sumLeaves (Node _ lt rt) = sumLeaves lt + sumLeaves rt

sumNodes :: Tree a -> Integer

sumNodes (Leaf x) = 0

sumNodes (Node _ lt rt) = 1 + sumNodes lt + sumNodes rt

Beweisen Sie mittels struktureller Induktion, dass für alle endlichen Bäume t :: Tree a gilt:

sumLeaves t = sumNodes t + 1

...zum Beitrag

Identität beweisen vollständige Induktion?

Im Unterricht haben wir gezeigt, dass für zwei reelle Zahlen s, t die Identität |st| = |s||t| gilt. Es sei nun u ∈ R. Benutze die oben angeführte Identität, um mithilfe vollständiger Induktion die folgende Behauptung zu beweisen.

Behauptung: Für alle n ∈ N gilt |uⁿ| = |u|ⁿ

Wie muss ich diese Aufgabe berechnen?

...zum Beitrag

Aussagenlogik Beweise führen (DNF, KNF)?

Komme auf folgende Aufgabe nicht klar:

zu i) Wieso soll ich zeigen, dass der Konjuntionsterm mindestens zwei positiven Literale hat. Ist das nicht in der Aufgabenstellung ('enthält mind. zwei EInsen' ) defininiert.

gleiches gilt für ii)

iii) Wenn die zweielementigen Teilmengen als n über 2 definiert sind und die DFN mindestens zwei positive Literale hat, dann hat sie doch schon mal mindestens zwei Teilemengen, oder?

iv) Eine DNF mit möglichst wenig Konjunktionstermen. Wenn D mindestens zwei pos. Literale enthält, wäre das wenigstense doch zwei, oder?

...zum Beitrag

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zum Beitrag

Beweisen Sie, dass die folgenden Aussagen äquivalent sind?

Hallo,

ich hänge bei dir Folgenden Aufgabe fest kann mir da jemand weiterhelfen?

Beweisen Sie, dass die folgenden Aussagen äquivalent sind:

i) f ist injektiv.

ii) Für alle Mengen A, B ⊂ X gilt :

iii) Für alle Mengen A ⊂ X gilt :

danke schon einmal :)

...zum Beitrag

Mathematik Satz beweisen?

Guten Tag,

ich übe gerade für eine kommende Mathematikklausur und in einer Aufgabe muss man folgenden Satz beweisen: "Für jede ganze Zahl m gilt: Ist m^2 +6m + 4 ungerade, so ist m ungerade." Mir ist klar, das wenn m ungerade ist, ist 6m gerade da das Produkt mit einer geraden Zahl immer gerade ist und m^2 ist ungerade da das Produkt aus 2 ungeraden Zahlen immer ungerade ist. Dadurch ist dann die Summe des Ganzen auch ungerade, jedoch weiß ich nicht wie ich das formal richtig aufschreiben/beweisen soll. Kann mir da jemand helfen? Danke im Voraus.

Mit freundlichen Grüßen,

Minepika

...zum Beitrag

Epsilon lösen?

Hallo,

ich möchte folgende Aufgabe lösen:

Meine Lösung lautet:

Betrag von ( f(x) - f(x0) ) < Epsilon

= Betrag von ( (x^2+x-2) -(x0^2 + x0 -2) ) < Epsilon

= (x^2+x - x0^2 -x0) < Epsilon

= Betrag von (x-xo) < Epsilon - x0^2 -x^2

-> Delta = -x0^2 -x^2