Computational Mathematics Technische Universit¨at Braunschweig Prof. Dr. A. Kemnitz [email protected] Rebenring 31 38106 Braunschweig Tel: 0531/391-7516 dm.jpbode.de PD Dr. Jens-P. Bode [email protected] Blatt 10 13. Januar 2015 Diskrete Mathematik fu¨r Informatiker Hausaufgabe 19 a) F¨ ur n ≥ 2 beweise man: an − bn ∈ P =⇒ n ∈ P und a − b = 1. b) Die Zahlen Mn = 2n − 1, n ∈ N, heißen Mersenne-Zahlen. Man zeige, dass M n h¨ochstens dann eine Primzahl sein kann, wenn n eine Primzahl ist. Hausaufgabe 20 k Die Zahlen Fk = 22 + 1, k = 0, 1, 2, . . ., heißen Fermat-Zahlen. a) Man beweise Fn = F0 F1 F2 . . . Fn−1 + 2 f¨ ur n ∈ N. b) Man zeige, dass die Fermat-Zahlen paarweise teilerfremd sind. ¨ Ubungsaufgabe 21 Man berechne den gr¨oßten gemeinsamen Teiler und das kleinste gemeinsame Vielfache von 2262 und 1781 mit dem euklidischen Algorithmus und bestimme Zahlen x, y ∈ Z mit x · 1781 + y · 2262 = ggT(1781, 2262). ¨ Ubungsaufgabe 22 a) Es seien n, m ∈ N und ggT(n, m) = 1. Man zeige: 2 falls n ≡ m ≡ 1 (mod 2), ggT(n2 + m2 , n + m) = 1 sonst. Tipp: Betrachten Sie Linearkombinationen von n 2 + m2 und n + m, die nur noch von m bzw. n abh¨angig sind. b) Eine Zahl n ist in ihrer Dezimaldarstellung a k ak−1 . . . a1 a0 angegeben. Man zeige: Die k P Zahl n ist genau dann durch 3 teilbar, wenn ihre Quersumme ai durch 3 teilbar ist. i=0 ¨ Abgabe der Hausaufgaben: Dienstag, 20. Januar, vor der großen Ubung. ¨ ¨ Die Ubungsaufgaben werden in den kleinen Ubungen am 21. und 22. Januar besprochen.