Nelius/Nöcker

12. Übungsblatt

MATHEMATIK FÜR INFORMATIKER I (WS 2000/01)

Abgabe: Montag, 29.1.2001 bis 13.00 Uhr !!!

Internet–Adresse der Vorlesung:

http://math–www.uni–paderborn.de/~chris/index9.html

43. Aufgabe: Seien a, b ganze Zahlen und sei p eine Primzahl. Beweise:

(a + b)^{p} ≡ a^{p} + b^{p} (mod p) (2)

44. Aufgabe: Berechne die letzten beiden Dezimalstellen von 123456789^{4921} (Hinweis: Anstatt zu rechnen wende man geeignete Sätze aus der Vorlesung an!) (3)

45. Aufgabe: Die Berechnung des größten gemeinsamen Teilers zweier Zahlen kann auf zwei verschiedene Weisen erfolgen. Das soll hier für die beiden Zahlen a = 2767198 und b = 1716495 gemacht werden. Die daür notwendigen Rechnungen sind zu dokumentieren!

a) Bestimme ggT(a, b) mit Hilfe des Euklidischen Algorithmus.

b) Zur Vorbereitung auf das zweite Verfahren berechne man alle Primzahlen zwischen 2 und 400 mit Hilfe des Siebes des Eratosthenes.

c) Berechne nun ggT(a, b) mit Hilfe der Primfaktorzerlegungen der beiden Zahlen a und b, die zuerst bestimmt werden müssen.

Bemerkung: Wenn für diese Aufgabe ein normaler Taschenrechner benutzt wird, dann ist die verwendete Zeit ein gutes Kriterium dafür, wie schnell ein Rechnerprogramm die verschiedenen Algorithmen ausführen kann. (7)

46. Aufgabe: Berechne die folgenden Summen bzw. Produkte von Matrizen. Bei Matrizen, deren Elemente Restklassen sind, sind im Ergebnis jeweils kleinstmögliche Repräsentanten ≥ 0 anzugeben.

a) ( \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix} ) + ( \begin{matrix}1 \\ −1 \end{matrix} ) b) ( \begin{matrix}[1]_{5} & [3]_{5} & [7]_{5} \\ [0]_{5} & [2]_{5} & [6]_{5} \end{matrix} ) + ( \begin{matrix}[3]_{5} & [2]_{5} & [6]_{5} \\ [12]_{5} & [−3]_{5} & [1]_{5} \end{matrix} )

c) ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix} ) · ( \begin{matrix}4 & 5 \\ 6 & 8 \\ 7 & 9 \end{matrix} ) d) ( \begin{matrix}4 & 5 \\ 6 & 8 \\ 7 & 9 \end{matrix} ) · ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix} )

e) ( \begin{matrix}1 & 2 \\ 5 & 6 \end{matrix} ) · ( \begin{matrix}4 & 5 \\ 6 & 8 \\ 7 & 9 \end{matrix} )  f) ( \begin{matrix}[15]_{7} & [14]_{7} \\ [35]_{7} & [−13]_{7} \end{matrix} ) · ( \begin{matrix}[9]_{7} & [25]_{7} \\ [5]_{7} & [93]_{7} \end{matrix} )  (4)