Fachbereich Mathematik Prof. Dr. J.H. Bruinier Martin Fuchssteiner Kay Schwieger

TECHNISCHE UNIVERSITÄT DARMSTADT

�

WS 2007/2008 9.10.2007

Lineare Algebra I

1. Tutorium mit Lösungshinweisen

(T 1) Für zwei ganze Zahlen a, c schreiben wir a|c, falls a die Zahl c teilt. Beweisen oder widerlegen Sie die folgenden Aussagen. Machen Sie sich dabei bewußt, was genau zu tun ist, um eine Aussage zu beweisen bzw. zu widerlegen.

(a) Gilt a|b und b|c, so folgt a|d.

(b) Gilt a|b und b|a, so folgt a = b oder a = −b.

(c) Gilt a|b und a|c, so gilt auch a|(b + c) und a|(b − c).

(d) Gilt a|c und b|c, so folgt (a + b)|c.

(e) Gilt a|b, so gilt für jede Zahl c auch a|b · c.

(f) Gilt a|c und b|c, so gilt auch (a · b)|c.

Lösung:

(a) Es gelte a | b und b | c. Dann gibt es k_{a}, k_{b} ∈ ℤ mit b = k_{a} · a und c = k_{b} · b. Durch Einsetzen ergibt sich c = (k_{b} · k_{a}) · a, also teilt a die Zahl c.

(b) Es gelte a | b und b | a. Dann gibt es k_{a}, k_{b} ∈ ℤ mit a = k_{b} · b und b = k_{a} · a. Durch Einsetzen ergibt sich a = k_{b} · k_{a} · a. Mit der Kürzungsregel folgt k_{b} · k_{a} = 1. Somit sind k_{a} und k_{b} beide 1 oder beide −1. Es ergibt sich a = k_{a}b = ±b.

(c) Es gelte a | b und b | c. Dann gibt es k_{b}, k_{c} ∈ ℤ mit b = k_{b} · a und c = k_{c} · a. Durch Einsetzen ergibt sich b ± c = k_{b} a + k_{c} a = (k_{b} + k_{c}) · a, also a | (b ± c).

(d) Gegenbeispiel: Es gilt 1 | 1 und 1 | 1, aber nicht (1 + 1) | 1.

(e) Es gelte a | b. Außerdem sei c ∈ ℤ eine ganze Zahl. Wegen a | b gibt es eine Zahl k ∈ ℤ mit b = k · a. Durch Multiplikation von c erhalten wir c b = c k a, also a | (c · b).

(f) Gegenbeispiel: Es gilt 2 | 2 und 2 | 2, aber nicht (2 · 2) | 2.

(T 2) Schreiben Sie die Aussagen aus Aufgabe T1 mit Hilfe des Quantors ∀ (Für alle), des Zeichens ∧ für “und”, des Zeichens ∨ für “oder” und mit Hilfe des Implikationspfeils ⇒. Die Aussage aus Aufgabe T1 a) läßt sich z.B. durch “∀ a, b, c ∈ ℤ : a | b ∧ b | c ⇒ a | c” kurz schreiben.

Lösung:

(a) ∀a, b, c ∈ ℤ : (a | b ∧ b | c) ⇒ a | c

(b) ∀a, b ∈ ℤ : (a | b ∧ b | a) ⇒ (a = b ∨ a = −b).

(c) ∀a, b ∈ ℤ : (a | b ∧ a | c) ⇒ (a | (b + c) ∧ a | (b − c)).

(d) ∀a, bc ∈ ℤ : (a | c ∧ b | c) ⇒ (a + b) | c.

(e) ∀a, b ∈ ℤ : a | b ⇒ (∀c ∈ ℤ : a | b · c).

(f) ∀a, b ∈ ℤ : (a | c ∧ b | c) ⇒ (a · b) | c.

(T 3) Kongruenzklassen

Es sei n ≥ 2 eine natürliche Zahl. Wir nennen zwei Zahlen a, b kongruent modulo n, falls die ganze Zahl a − b durch n teilbar ist. Wir schreiben in diesem Fall a ≡ b (mod n).

(a) Für welche Zahlen a gilt a ≡ 0 (mod 2), für welche gilt a ≡ 1 (mod 2)?

(b) Zeige, daß a ≡ 0 (mod n) genau dann gilt, wenn n|a gilt.

Hinweis: Die Satzkonstruktion ”genau dann …, wenn“ beinhaltet zwei Implikationen.

(c) Zeige, daß a ≡ b (mod n) genau dann gilt, wenn a und b denselben Rest bei Division durch n haben. Formuliere hierzu vor dem Beweis genau, was du unter dem Rest bei Division durch n verstehst.

(d) Zeige: Gilt a ≡ b (mod n) und c ≡ d (mod n), so gilt auch

a ± c ≡ b ± d (mod n) und a · c ≡ b · d (mod n) .

Lösung:

(a) a ≡ 0 (mod 2) gilt genau für alle geraden Zahlen, und a ≡ 1 (mod 2) gilt genau für alle ungerade Zahlen.

(b) Nach Definition gilt a ≡ 0 (mod n) genau dann, wenn die Differenz a − 0 = a durch n teilbar ist.

(c) Definition: Sei a eine ganze Zahl. Der Rest von a bei Division durch n ist diejenige (eindeutig bestimmte) Zahl r_{a} ∈ {0, 1, …, n − 1}, für welche es eine ganze Zahl k gibt mit

a = k · n + r_{a} .

Eine Implikation: Seien a, b ganze Zahlen mit a ≡ b (mod n). Wir bezeichnen mit r_{a} bzw. r_{b} den Rest von a bzw. b bei Division durch n. Nach Definition gibt es ganze Zahlen k_{a}, k_{b} mit

a = k_{a} · n + r_{a} ,  b = k_{b} · n + r_{b} .

Wegen a ≡ b (mod n) ist die Differenz a − b = (k_{a} − k_{b}) · n + (r_{a} − r_{b}) durch n teilbar. Weil das Produkt (k_{a} − k_{b}) · n trivial durch n teilbar ist, folgt mit Aufgabe T1 (c), daß auch die Differenz r_{a} − r_{b} = (a − b) − (k_{a} − k_{b}) · n durch n teilbar ist. Wegen 0 ≤ r_{a}, r_{b} ≤ n − 1, gilt für die Differenz −n + 1 ≤ r_{a} − r_{b} ≤ n − 1. Die einzige durch n teilbare Zahl in diesem Intervall ist 0, also r_{a} − r_{b} = 0.

Die andere Implikation: Seien a, b ganze Zahlen mit demselben Rest r ∈ {0, …, n − 1} bei Division durch n. Dann gibt es ganze Zahlen k_{a}, k_{b} mit

a = k_{a} · n + r ,  b = k_{b} · n + r .

Die Differenz a − b = (k_{a} − k_{b}) · n somit durch n teilbar.

(T 4)

(a) Zeige, daß es für jede natürliche Zahl a genau eine Zahl k ∈ {0, 1, 2, 3} mit a ≡ k (mod 4) gibt!

Hinweis: Die Satzkonstruktion ”genau eine“ ist gleichbedeutend mit ”eine und nur eine“.

(b) Wieviele Primzahlen p gibt es mit p ≡ 0 (mod 4), wieviele mit p ≡ 2 (mod 4)?

(c) Gibt es unendlich viele Primzahlen p mit p ≡ 3 (mod 4)? Die folgenden Teilaufgaben können dir vielleicht bei deiner Entscheidung helfen:

1. In der Vorlesung wurde gezeigt, daß es unendlich viele Primzahlen gibt. Diskutiere in deiner Gruppe die wesentlichen Schritte des Beweises!

2. Zeige, daß für alle natürlichen Zahlen a_{1}, …, a_{n} gilt:

∏_{i=1}^{n}(4a_{i} + 1) ≡ 1 (mod 4) ,

∏_{i=1}^{n}(4a_{i} + 3) ≡ (−1)^{n} (mod 4) .

(d) (Für Interessierte) Gibt es unendlich viele Primzahlen p mit p ≡ 1 (mod 4)?

Lösung:

(a) Sei a eine natürliche Zahl. Sei k ∈ {0, 1, 2, 3} ihr Rest bei Division durch n. Dann gilt a ≡ k (mod 4) mit Aufgabe T3 (c).

(b) Es gibt keine Primzahl mit p ≡ 0 (mod ) und genau eine Primzahl mit p ≡ 2 (mod 4), nmlich 2.

(c) 1….

2. Für jede natürliche Zahl a gilt 4a + 1 ≡ 1 (mod 4) und 4a + 3 ≡ (−1) (mod 4) (siehe Aufgabe T3 (d)). Mit Aufgabe T3 (d) ergibt sich deshalb für die Produkte:

(4a_{1} + 1)(4a_{2} + 1) … (4a_{n} + 1) ≡ \underbrace{1 · 1 · . . . · 1}_{n Stck} ≡ 1 (mod 4) ,
(4a_{1} + 3)(4a_{2} + 3) … (4a_{n} + 3) ≡ \underbrace{(−1) · (−1) · . . . · (−1)}_{n Stck} = (−1)^{n} (mod 4) .

Es gibt unendlich viele Primzahlen p mit p ≡ 3 (mod 4). Wir führen den Beweis völlig analog zu dem Beweis aus der Vorlesung für die Existenz unendlich vieler Primzahlen: Wir nehmen an, daß es nur endlich viele solche Primzahlen p_{1}, …, p_{n} gibt. Weil all diese Primzahlen den Rest 3 bei Division durch 4 haben, gibt es natürliche Zahlen a_{1}, …, a_{n} mit p_{i} = 4a_{i} + 3 für jeden Index i. Wir betrachten die Zahl

p̂:= p_{1} · p_{2} · . . . · p_{n} + 3 − (−1)^{n} = ∏_{i=1}^{n}(4a_{i} + 3) + 3 − (−1)^{n} .

I. p̂ ≡ 3 (mod 4): Nach Aufgabenteil T4 (c) 2 ist das Produkt p_{1} … p_{n} = ∏_{i=1}^{n}(4a_{i} + 3) kongruent zu (−1)^{n} modulo 4. Für p̂ gilt also

p̂ ≡ (−1)^{n} + 3 − (−1)^{n} = 3 (mod 4) .

II. p̂ ist durch kein p_{i} teilbar. Bei Division durch eine der Primzahlen p_{i} ergibt sich für p̂ der Rest 3 − (−1)^{n}, denn es gilt

p̂ = p_{1}p_{2} … p_{n} + 3 − (−1)^{n} ≡ 0 + 3 − (−1)^{n} (mod p_{i}) .

Wäre p̂ durch eine der Primzahlen p_{i} teilbar, so müsste sich der Rest 0 ergeben.

III. p̂ ist nicht durch 2 teilbar. Wäre p̂ durch 2 teilbar (also p̂ gerade), so müsste sich bei der Division durch 4 der Rest 0 oder Rest 2 ergeben. Es gilt jedoch p̂ ≡ 3 (mod 4).

Zerlegen wir p̂ in Primfaktoren p̂ = q_{1} · . . . · q_{m}, so treten dabei nur Primzahlen q_{i} mit q_{i} ≡ 1 (mod 4) auf. Für jede solche Primzahl q_{i} gibt es eine natürliche Zahl b_{i} mit q_{i} = 4b_{i} + 1. Damit ergibt sich p̂ als Produkt

p̂ = ∏_{i=1}^{m}(4b_{i} + 1) .

Nach Aufgabenteil T4 (c) 2 besitzt ein solches Produkt den Rest 1 bei Division durch 4. Dies steht jedoch im Widerspruch zu p̂ ≡ 3 (mod 4).

(d) Ja, weil … – finde es doch selbst heraus!