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

Angabe: Elementare Zahlentheorie

Aufgabe 1

Euklidischer Algo:

98 362 = 6 * 15 878 + 3094
...
68 = 2 * 34 + 0

Also ist ggT der zwei Zahlen gerade 34, WolframAlpha stimmt überein.

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ℤ

Aufgabe 5

2100_{10} = 6060_{7}

WolframAlpha stimmt überein.

Aufgabe 6

Zuerst vollständig kürzen. Dazu ggT von Zähler und Nenner berechnen, entweder per TR (wenn es euer TR kann) oder wie folgt manuell:

5525 = 3 * 1575 + 800
1575 = 1 *  800 + 775
 800 = 1 *  775 +  25

Vorzeitiger Abbruch, da ggT(5525, 1575) = ggT(775, 25) = 25, letztere Gleichheit „abgelesen“ (da 775 „offensichtlich“ durch 25 teilbar)

Dann mittels TR kürzen:

1575       63
------ = -----
5525      221

Es gilt ggT(221, 10) = 1. (Denn Teiler wie 2 oder 5 würde man an 221 an der letzten Ziffer erkennen.) Daher hat der gegebene Bruch eine reinperiodische Dezimalbruchentwicklung (Satz 7.2 im Skript vom WS 20/21).