Modulo Aussagen

Neue Frage »

darbo47 Auf diesen Beitrag antworten »
Modulo Aussagen
Hallo, bei solchen Aufgaben habe ich Schwierigkeiten.
m,n,d natürliche Zahlen bis auf die 1, a und b ganze Zahlen.
a) Beweise: wenn a kongruent b mod m und d teilt m, dann a kongruent b mod d.
b) Beweise: Gilt ggT(m,n)=1, a kongruent b mod m und a kongruent b mod n, dann auch a kongruent b mod m*n
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Hi darbo47,

für a) hilft es, erstmal die Definitionen für "a kongruent b mod m" und "d teilt m" aufzuschreiben, in Formeln.
Dann sollte schnell klar werden, warum (und "wie") a und b auch modulo d kongruent sind.

Für b) tust du das am besten auch erstmal, anhand der Gleichungen könntest du dann auch schon notwendige Bedingungen erkennen. Und du musst dir überlegen, wo die Bedingung ggT(n, m) = 1 eingehen kann.
 
 
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
zur a) a kongruent b mod m kann doch auch als m teilt a-b geschrieben werden.
d teilt m bedeutet, dass gilt: d*x=b

zur b) ggT(n,m) heißt n und m sind teilerfremd.
a kongruent b mod m kann wieder als m teilt a-b geschrieben werden,
a kongruent b mod n dementsprechend als n teilt a-b.

Nur wie gehts weiter?
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Zitat:
Original von darbo47
zur a) a kongruent b mod m kann doch auch als m teilt a-b geschrieben werden.
d teilt m bedeutet, dass gilt: d*x=b


Am besten erledigen wir erstmal die a).
Genau. Was heißt jetzt noch m teilt a-b und was heißt dann weiter a kongruent b modulo d?
Schreib die Aussagen vielleicht mal als Gleichungen untereinander auf, dann sollte dir etwas auffallen.
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
m teilt a-b => (a-b)*y=m
d*x=b

a kongruent b mod d
wäre d teilt a-b => (a-b)*x=d
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
ich meinte d*x=m
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Habe noch ein Fehler bemerkt. Jetzt die richtige Fassung:
a-b=m*x
d*y=m
a-b=d*z
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Okay, gut.
Jetzt steht die Lösung schon fast da.
Es gibt ganze Zahlen x und y, sodass die ersten beiden Gleichungen erfüllt sind.
Wie zeigst du nun, dass ein z existiert, welches die dritte Gleichung erfüllt?
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
m in der ersten gleichung kann ersetzt werden:
a-b=d*y*x
=> a-b=d*z
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Super, genauso klappt's. Freude

Wenn a und b kongruent modulo m = yd sind, dann ist
a - b = xm = xyd, also weil z = xy auch eine ganze Zahl ist, sind a und b auch modulo d kongruent.

Dann mal auf zu Teil b).
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
OK,
a kongruent b mod m ist ja wieder m teilt a-b, also (a-b)*x=m,
a kongruent b mod n ist dementsprechend n teilt a-b, also (a-b)*y=n,

a kongruent b mod m*n ist m*n teilt a-b, also (a-b)*z=m*n
nur wie kann man jetzt die Tatsache, dass m und n teilerfremd sind, reinbringen?
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Jetzt hast du wieder m teilt a-b falsch "übersetzt"...
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Das ist so verwirrend, sorry!
a-b=m*x
a-b=n*y
a-b=m*n*z
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Genau.
Und jetzt benutzt du die ersten beiden Aussagen -- das sind ja deine Voraussetzungen -- und folgerst zusammen mit der Teilerfremdheit von n und m die dritte. : )
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Nur wie kann ich den ggT reinbringen?
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Wie kannst du denn die ersten beiden Aussagen erstmal zu einer neuen kombinieren?
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Wieder durch Einsetzen
m*x=n*y
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Genau.
Die Gleichung kannst du jetzt in einem einfachen Schritt noch weiter umformen und dann die Voraussetzun ggT (n, m) = 1 benutzen um eine Bezehung zwischen x und y festzustellen, die dir letztendlich die zu zeigende Aussage liefert. smile
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Also:
a-b=m*x
a-b=n*y
a-b=m*n*z

Einsetzen der ersten in die zweite Gleichung ergibt:
m*x=n*y

m=(n*y)/x Umstellen nach m bringt nichts. Das a-b muss doch irgendwie darein.

Ich weiß echt nicht weiter.
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Zitat:
Original von darbo47
m=(n*y)/x Umstellen nach m bringt nichts.

Dann stell doch mal nach etwas anderem als m um Augenzwinkern
Wenn du da dann die Teilerfremdheit von n und m benutzt, kannst du eine Eigenschaft von
y/m (oder x/n, jenachdem welchen Weg du gehst) folgern, die dir weiterhilft.

Zitat:
Das a-b muss doch irgendwie darein.

Das a-b spielt weiter eine Rolle, wenn du weißt, was die besondere Eigenschaft von y/m (bzw. x/n) ist.
Denn a-b = mx = ny gilt ja nach wie vor.
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Umstellen bringt dann:
y/m=x/n
Weil m und n teilerfremd sind, ist dann y auch teilerfremd zu m und x zu n.

y*x/((a-b)*m*n) => (a-b)*m*n*z
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Nein, y und m sind nicht teilerfremd!
Was du mit der Implikation unten meinst, verstehe ich auch nicht.

Und die Umformung y/m = x/n bringt dir so nicht besonders viel, erstmal.

Du sollst rausfinden, dass y/m (und damit auch x/n) ganzzahlig ist. Warum ist das so? Was bedeutet das weiter für a-b = mx = ny?
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Ich glaube ,ich krieg das gar nicht mehr raus.
y/m ist ganzzahlig, weil sowohl y ein Vielfaches von n und x ein von m ist. Ist ja einleuchtend, dass das so ist, aber ich komme einfach nicht auf die Lösung.
Wenn die beiden ganzzahlig sind, heißt dass, dass m*x und n*x auch ganzzahlig.
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
mx ist sowieso ganzzahlig, denn das war ja genau a-b.
y ist nicht unbedingt Vielfaches von n und x ist nicht unbedingt Vielfaches von m.

Es gilt doch mx = ny, also auch x = ny/m. Und weil n und m teilerfremd sind, ny/m aber ganzzahlig ist, muss m bereits y teilen. (m teilt ny und ggT(m, n) = 1. Daraus folgt m teilt y.)

Und jetzt machst du weiter mit a-b = mx = ny und zeigst a-b = mnz für ein ganzzahliges z.
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Ok,
Einsetzen bringt an dieser Stelle nichts.
Egal, wie ich das umstelle, habe das mit Zahlen für die Buchstaben probiert. Ich bekomme das nicht raus.
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Was genau tust du denn?
Vielleicht beschreibst du das mal etwas präziser und ausführlicher, dann fällt es leichter, dir die richtige Hilfestellung zu geben.

An welchem Schritt genau hängst du fest, welche Ideen hast du?
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
a-b=m*x=n*y

So wenn ich für x=n*y/m einsetze kommt ja logischerweise a-b=n*y heraus.

Ich muss ja in der Gleichung irgendwie auf M*N kommen, nur wie soll das funktionieren?
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
m teilt ja y und n teilt x
, vielleicht deswegen y=m*z x=n*z
und dann einsetzen z.B für m*x=m*n*z
carlf Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Sieht doch gut aus! Freude

m teilt y, es gibt also ein z mit mz = y.
Damit ist a-b = ny = nmz = mn z, also teilt mn auch a-b.
a und b sind also kongruent modulo mn.
darbo47 Auf diesen Beitrag antworten »
RE: Modulo Aussagen
Danke für deine Geduld und Hilfe ;-)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »