Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Nebenfächer » mathematik » Aufgabe 1   (Übersicht)

Dies ist eine alte Version des Dokuments!


Inhaltsverzeichnis

Angabe: Elementare Zahlentheorie

Aufgabe 2

254 = 6 * 41 + 8
 41 = 5 *  8 + 1
  8 = 8 *  1 + 0
  
1 = 41 - 5*8 = 41 - 5*(254 - 6*41) = 31*41 - 5*254

Daher ist 31 Inverses von 41 modulo 254.

Aufgabe 3

  • Es gilt: phi(13) = 13 - 1 = 12 und 3 und 13 sind teilerfremd ⇒ Satz von Euler anwendbar
  • [3^{160}] = [3^{12*13} * 3^4] = [3^{12}]^{13} * [3^4] = [3^4] = [81] = [3] (WolframAlpha stimmt überein)
  • Hier ist [.]: Z → Z/(13Z) die kanonische Surjektion. In der EZT-Vorlesung wurde die mit overline typischerweise notiert.
  • 3^{160} hat bei Division durch 13 also den Rest 3.

Aufgabe 4

  • Konstruiertes x nach Schema in der VL: x = 14 364 ≡ 1104 (mod 1105)
  • Lösungsmenge ist L = 1104 + 1105ℤ