UNIVERSITÄT DES SAARLANDES FACHRICHTUNG 6.1 – MATHEMATIK Prof. Dr. Jörg Eschmeier Dipl.-Math. Michael Wernet �

Übungen zur Vorlesung Mathematik für Informatiker I

Wintersemester 2011/2012

Blatt 4 Abgabetermin: Freitag, 18.11.2011

Aufgabe 13 (1+1+2=4 Punkte)

Seien a, b, c, a_{1}, …, a_{r} ∈ ℤ. Zeigen Sie:

(i) a|b und b|c ⇒ a|c.

(ii) a|a_{i} für i = 1, …, r ⇒ a| ∑_{i=1}^{r} u_{i}a_{i} für alle u_{1}, …, u_{r} ∈ ℤ.

(iii) ggT(a, b) = 1 und a|bc ⇒ a|c.

Endlich viele ganze Zahlen a_{1}, …, a_{r} heißen teilerfremd, falls ggT(a_{1}, …, a_{r}) = 1.

Aufgabe 14 (2+2+2=6 Punkte)

Seien a_{1}, …, a_{r} ∈ ℤ. Zeigen Sie:

(a) Ist r ≥ 2 und d = ggT(a_{1}, …, a_{r−1}), so ist ggT(d, a_{r}) = ggT(a_{1}, …, a_{r}).

(b) a_{1}, …, a_{r} besitzen einen größten gemeinsamen Teiler (In der Vorlesung wurde dies nur für den Fall r = 2 begründet).

(c) a_{1}, …, a_{r} sind teilerfremd ⇔ ∃u_{1}, …, u_{r} ∈ ℤ mit 1 = ∑_{i=1}^{r} u_{i}a_{i}.

Aufgabe 15 (4 Punkte)

Ein chinesischer Schäfer hat eine Herde von höchstens 200 Tieren. Um sie exakt zu zählen, lässt er sie des Abends immer zu zweit durch ein Gatter laufen und stellt fest, dass ein Tier übrig bleibt. Am nächsten Abend lässt er die Tiere immer zu dritt durchs Gatter laufen und stellt ebenfalls fest, dass eins übrig bleibt. Am dritten Tage macht er dasselbe mit 5 Schafen und stellt wieder fest, dass eines übrig bleibt. Am vierten Abend schlielich lässt er 7 Schafe auf einmal durchs Gatter und es bleibt kein Schaf übrig. Wie groß ist die Herde?

(bitte wenden)

Aufgabe 16 (4+2^{∗} Punkte)

(a) Seien n, m ∈ ℤ_{>0} teilerfremd. Zeigen Sie, dass die Abbildung

φ : ℤ/nm → ℤ/n × ℤ/m, [x]_{nm} ↦ ([x]_{n}, [x]_{m}) wohldefiniert und bijektiv ist. Rechts sind die Äquivalenzklassen von x in ℤ/nm, ℤ/n und ℤ/m gemeint.

(b)^{∗} Sei n ∈ ℤ_{>0} und x̄ ∈ ℤ/n. Zeigen Sie:

ggT(x, n) = 1 ⇔ ∃ȳ ∈ ℤ/n mit x̄ȳ = ¯1.