Angabe: {{:pruefungen:nebenfach:mathematik:klausur_elementarezahlentheorie.pdf|Elementare Zahlentheorie}}

====== Aufgabe 1 ======

Euklidischer Algo:
<code>
98 362 = 6 * 15 878 + 3094
...
68 = 2 * 34 + 0
</code>
Also ist ggT der zwei Zahlen gerade 34, {{https://www.wolframalpha.com/input/?i=gcd%2898362%2C15878%29|WolframAlpha stimmt überein}}.

====== Aufgabe 2 ======

<code>
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
</code>

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]'' ({{https://www.wolframalpha.com/input/?i=%283%5E%28160%29%29+mod+13|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}''

{{https://www.wolframalpha.com/input/?i=2100+in+base+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:
<code>
5525 = 3 * 1575 + 800
1575 = 1 *  800 + 775
 800 = 1 *  775 +  25
</code>

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

Dann mittels TR kürzen:
<code>
1575       63
------ = -----
5525      221
</code>
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).