¨Ubungen zur LAG+ im Sommer 2016 – Blatt 3

Prof. Dr. Felix Leinen
04. Mai 2016
Übungen zur LAG + im Sommer 2016 – Blatt 3
Abgabe der Aufgaben bis Mittwoch, 11. Mai 2016 um 10:00 Uhr.
1. Es seien a = 366324959 und b = 220598911 . Führen Sie die folgenden Berechnungen durch und
geben Sie dabei alle Zwischenschritte vollständig an.
(a) Berechnen Sie den größten gemeinsamen Teiler d der Zahlen a und b.
[2 P]
(b) Berechnen Sie das kleinste gemeinsame Vielfache der Zahlen a und b.
[1 P]
(c) Bestimmen Sie die Primzerlegungen der Zahlen a und b.
[3 P]
(d) Berechnen Sie ganze Zahlen s und t mit d = s · a + t · b.
[2 P]
(e) Berechnen Sie ganze Zahlen u und v mit d = u · a + v · b und u > 0 .
[2 P]
2. Wir betrachten natürliche Zahlen a > 1 und n ≥ m > 0 . Zeigen Sie:
(a) Genau dann ist am −1 ein Teiler von an −1 , wenn m ein Teiler von n ist.
(b) Ist ggT (n, m) = d, so gilt ggT an −1, am −1 = ad −1 .
[4 P]
[3 P]
(c) Bestimmen Sie nun den größten gemeinsamen Teiler der beiden Zahlen
7
(2 370305 −1)
−1
und
7
(2 162963 −1)
−1 .
[2 P]
3. Die Zahlen cn und dn (n ∈ N) seien rekursiv definiert durch
c0 = 169,
d0 = 3,
c1 = −221
und
cn = cn−2 − 13 cn−1
für alle
n ≥ 2,
d1 = 4
und
dn = dn−2 + 13 dn−1
für alle
n ≥ 2.
(a) Bestimmen Sie ggT (c793 , c792 ) .
[3 P]
(b) Zeigen Sie, daß dn und dn+1 die Bezout-Koeffizienten zu cn+1 und cn sind.
[3 P]
(c) Sind cn+1 und cn auch die Bezout-Koeffizienten zu dn und dn+1 ?
[2 P]
(Begründung!)
4. Beim Bestimmen des größten gemeinsamen Teilers zweier natürlicher Zahlen a0 > a1 > 0 mit
dem Euklidischen Algorithmus entstehen die Zahlen a0 > a1 > a2 > . . . . . . > an = ggT (a0 , a1 ) .
(a) Zeigen Sie:
(b) Folgern Sie:
ak−1 ak
2
< a0 a1 .
ak ak+1 <
2n−1
für 1 ≤ k ≤ n − 1 .
(c) Wieviele Schritte benötigt der Euklidische Algorithmus höchstens für die Bestimmung des
größten gemeinsamen Teilers zweier 750-stelliger natürlicher Zahlen ?
[2 P]
[1 P]
[2 P]

Download Report