Praxis — Klausuraufgaben

1. ggT: Berechne ggT(252, 198) mit Euklid.
   Lösung

   252 = 1·198 + 54. 198 = 3·54 + 36. 54 = 1·36 + 18. 36 = 2·18 + 0. ggT = 18.

2. Primfaktoren: Faktorisiere 360.
   Lösung

   360 = 2³ · 3² · 5.

3. Wochentag: Heute Donnerstag. Welcher Tag in 365 Tagen?
   Lösung

   365 mod 7 = 1. Also Freitag.

4. Inverses mod n: Was ist 5⁻¹ mod 11?
   Lösung

   5 · 9 = 45 = 4·11 + 1 → 5 · 9 ≡ 1 mod 11. Inverses: 9.

5. Großes Modulo: Berechne 7^100 mod 11. (Tipp: Fermat.)
   Lösung

   11 prim, 7 nicht durch 11 teilbar → 7^10 ≡ 1 mod 11. 7^100 = (7^10)^10 ≡ 1^10 = 1 mod 11.

6. kgV: Berechne kgV(36, 48).
   Lösung

   ggT(36,48) = 12. kgV = (36·48)/12 = 144.

7. Anwendung: Wie viele teilerfremde Zahlen zu 12 gibt es zwischen 1 und 12?
   Lösung

   φ(12) = φ(4·3) = φ(4)·φ(3) = 2·2 = 4. Zahlen: { 1, 5, 7, 11 }.