Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » allgemeine kongruenz

allgemeine kongruenz

Universität / Fachhochschule

Elementare Zahlentheorie

Teilbarkeit

Tags: Elementare Zahlentheorie, Teilbarkeit

lars174 aktiv_icon

13:32 Uhr, 22.06.2018

Hallo es seien

n, m \in N > 0

a, b \in Z

.

zz ist :

x \equiv a

mod

m

x \equiv b

mod

n

hat genau dann eine Lösung wenn :

a \equiv b

mod

g g t (n, m)

gilt .

ich habe mir mal überlegt wenn es so ein x gibt das beide Kongruenzen erfüllt dann ist wegen

d ∣ n, m

und

x \equiv a

mod

m

x \equiv b

mod

n

auch

a \equiv b

mod

d

.

und umgekehrt :
wenn

a \equiv b

mod

d

, und

d = y n + z m

mit

y, z \in Z

hier sehe ich nicht wie ich eine Lösung finde .

kann mir jemand helfen? Danke !

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

michaL aktiv_icon

15:03 Uhr, 22.06.2018

Hallo,

aus

d ∣ b - a

mit

d := ggT (m, n)

und

b - a = k \cdot d

folgt doch aus

d = p m + q n

die Gleichung

b - a = k d = k p m + k q n

. Insbesondere folgt daraus

a + k p m = b - k q n = : x

. Damit folgt für dieses

x

x \equiv a

mod

m

x \equiv b

mod

n

Umgekehrt: Wenn es eine Lösung

x_{0}

für

x \equiv a

mod

m

x \equiv b

mod

n

gibt, so gibt es offenbar

p, q

mit

a + p m = x = b + q n \Rightarrow b - a = p m - q n

. Insbesondere gilt, dass

b - a \in 〈 m, n 〉 = 〈 d 〉

gilt.
Das bedeutet also, dass

d ∣ b - a

.

Mfg Michael

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1431734

1431720

	Status: nicht eingeloggt	Noch nicht registriert?