% Elementare Zahlentheorie --- An exercise in Plain TeX
% $Id: ezt-braindump.tex,v 1.6 2024/02/05 11:23:03 oj14ozun Exp $
% https://wwwcip.cs.fau.de/~oj14ozun/src+etc/ezt-braindump.tex

% (Springe ganz an das Ende der Datei für den eigentlichen Inhalt)

% \tracingall

\newif\ifmitloesungen           %Berechne Lösungen?
\mitloesungentrue

\newif\iffranz                  %Französische Überschrift?
\franzfalse

\input amstex                   %we need this to...
\loadmsbm                       %load blackboard fonts

\font\ueberschrift=cmssbx17
\font\unterschrift=cmcsc10
\font\loesungsschrift=cmss10

\def\modeq#1#2#3{#1 \equiv #2 \mod{#3}}
\def\uu#1{\underline{\underline{#1}}}

\newcount\aufgaben
\def\aufgabe{
\vskip 0.25cm
\filbreak
\advance \aufgaben by 1
\noindent{\bf{}Aufgabe \the\aufgaben}
\par\noindent
}

\newcount\d
\newcount\n
\newcount\q
\newcount\r
\newcount\a
\newcount\b
\newcount\c
\newcount\s
\newcount\t
\newcount\x
\newcount\y
\newcount\z
\newcount\e
\newcount\i
\newcount\ii
\newcount\m
\newcount\summe
\newcount\produkt
\newcount\iseq
\newtoks\str

\def\kopf#1{
\noindent\hrulefill{}
\vskip 0.25cm
\centerline{
\unterschrift Ged\"achnisprotokoll der Klausur vom #1
\ifmitloesungen
--- mit autoge-\TeX'en L\"osungen!
\fi
}
\vskip 0.5cm
\iffranz
\centerline{
\ueberschrift
T\,H\,\'E\,O\,R\,I\,E
\;
\'E\,L\,\'E\,M\,E\,N\,T\,A\,I\,R\,E
\;
D\,E\,S
\;
N\,O\,M\,B\,R\,E\,S
}
\centerline{(Dt.:\ \it Elementare Zahlentheorie)}
\else
\centerline{
\ueberschrift
E\,L\,E\,M\,E\,N\,T\,A\,R\,E
\enspace
Z\,A\,H\,L\,E\,N\,T\,H\,E\,O\,R\,I\,E
}
\fi
\vskip 0.5cm
{\it Wie immer:} Keine Garantie auf Richtigkeit.  Angaben sollten mehr
oder weniger passen.  Fehler und Verbesserungen an
die FSI-Informatik Melden: {\tt fsi\@cs.fau.de}.  Der Quelltext sollte
im PDF-Anhang sein.

{\it Allgemeine Informationen:} Die meisten Taschenrechner ``Teilen
mit Rest'' ($\div \roman{R}$), Primfaktorzerlegung ({\tt FACT}, auf
Casio-Ger\"aten), und ggT ({\tt GCD}) berechnen k\"onnen, auf wenn
nicht programmierbar.  Gegebenenfalls ist es notwendig sein eigenes
Papier in die Klausur zu nehmen.  {\bf Alle Antworten sollten in Form
eines Antwortsatzes sein.}  Die Klausur dauert 60 Minuten, und sollte
in N\"urnberg stattfinden.

\noindent\hrulefill{}
}

\newif\iftracediv
\def\divmod#1#2{
  \n = #1
  \d = #2

  \ifnum #2 = 0
    \errmessage{Division by zero}
  \fi

  % division by repeated subtraction
  \iftracediv \item{$\bullet$} ${\the\n} \div {\the\d}$ \fi
  \r = \n
  \q = 0
  \loop
      \e = \d
      \advance \e by -1         %we need this for >= instead of >
    \ifnum \r > \e
      \advance \r by -\d
      \advance \q by 1
  \repeat
  \iftracediv ist ${\the\q}\;\slanted{R}\;{\the\r}$. \fi
}

\def\euclid#1#2{
\a = #1
\b = #2

\loop
\ifnum \b > 0
{
  \divmod{\a}{\b}
  \global \a = \b
  \global \b = \r
}
\repeat
\iftracediv\item{$\bullet$} $\the\a \div 0$ terminiert.\fi
}

\def\ggt#1#2{\aufgabe Berechnen Sie den gr\"o{\ss}ten gemeinsamem
Teiler der Zahlen #1 und #2 mit Hilfe des Euklidischen Algorithmus.

\ifmitloesungen
{\loesungsschrift
Die Rechenschritte sind:
\tracedivtrue
\euclid{#1}{#2}
\tracedivfalse

L\"osung ist das Letzte $a_i$ wo $b_i = 0$, d.h.\ $\uu{\the\a}$.
}
\fi
}

\newif\iftraceeuclid
\def\eeuclid#1#2{
  % https://en.wikipedia.org/wiki/extended_euclidean_algorithm#pseudocode
  \x=#1 \r=#2
  \y=1  \s=0
  \z=0  \t=1

  \iftraceeuclid
    \item{$\bullet$}
    $r  = \the\r$,
    $r' = \the\x$,
    $s  = \the\s$,
    $s' = \the\y$,
    $t  = \the\t$,
    $t' = \the\z$
  \fi
  \loop
  \iseq=0
  \ifnum \r=0 \iseq=1 \fi
  \ifnum \iseq = 0
  {
    {
      \divmod{\x}{\r}
      \global\q=\q
    }
    % (old_r, r) := (r, old_r − quotient × r)
    \summe     = \x
    \produkt   = \q
    \multiply  \produkt by -\r
    \advance   \summe     by \produkt
    \global \x = \r
    \global \r = \summe
    % (old_s, s) := (s, old_s − quotient × s)
    \summe     = \y
    \produkt   = \q
    \multiply  \produkt by -\s
    \advance   \summe     by \produkt
    \global \y = \s
    \global \s = \summe
    % (old_t, t) := (t, old_t − quotient × t)
    \summe     = \z
    \produkt   = \q
    \multiply  \produkt by -\t
    \advance   \summe by \produkt
    \global \z = \t
    \global \t = \summe
    \iftraceeuclid
      \item{$\bullet$}
      $r  = \the\r$,
      $r' = \the\x$,
      $s  = \the\s$,
      $s' = \the\y$,
      $t  = \the\t$,
      $t' = \the\z$
    \fi
  }
  \repeat
}

\def\inverse#1#2{
  \eeuclid{#1}{#2}
  \i=\z
  \ifnum \i < 0
    \loop
    \ifnum \i < 0
      \advance \i by #1
    \repeat
  \fi
  \ifnum \i > #1
    \loop
    \ifnum \i > #1
      \advance \i by -#1
      \message{(\the\i, #1)}
    \repeat
  \fi
  \global\i=\i
  \global\ii=\z
}

\def\repr#1#2{\aufgabe Bestimmen Sie den Repr\"asentanten $1 \leq x
< #1$ des Inversen $\overline{#2}^{-1} \in {\Bbb Z}/#1{\Bbb Z}$.
\ifmitloesungen
{\loesungsschrift

Man benutzt den Erweiterten Euklidischen Algorithmus (iterativ)
auf $(a, b) = (#1, #2)$ um die Parameter $x$ und $y$ zu finden, mit
denen $xa + yb = \roman{ggT}(a, b)$ gilt:

\traceeuclidtrue
\inverse{#1}{#2}
\traceeuclidfalse

Wir m\"ussen sicherstellen, dass das Ergebnis im gefordertem Intervall liegt
$$\modeq{\the\ii}{\the\i}{#1}.$$

Die Inverse von $\overline{#2}^{-1}$ in ${\Bbb Z}/#1{\Bbb Z}$ ist
demnach $\uu{\the\i}$.  Mit dem Taschenrechner kann man \"uberpr\"ufen
ob
\e = \i
\multiply \e by #2
$$\modeq{\the\i \cdot #2 = \the\e}{1}{#1}.$$
}
\fi
}

\def\sam#1#2#3{
\c=1
\b=#1
\e=#2
\i=0
\item{$\bullet$} $c_{\the\i} = \the\c, e_{\the\i} = \the\e, b_{\the\i} = \the\b$
\loop
\ifodd \e
{
\multiply \c by \b
\divmod{\c}{#3}
\global\c=\r
}
\fi
\divide \e by 2
{
\multiply \b by \b
\divmod{\b}{#3}
\global\b=\r
}
\advance \i by 1
\item{$\bullet$} $c_{\the\i} = \the\c, e_{\the\i} = \the\e, b_{\the\i} = \the\b$
\ifnum \e > 0
\repeat
}

\def\rest#1#2#3{
\aufgabe Welchen Rest hat $#1^{#2}$ bei Division durch
#3?
\ifmitloesungen
{\loesungsschrift

Die Aufgabe kann mit dem Euler-Theorem und der Euler'schen
$\varphi$-Funktion gel\"ost werden, oder mit dem ``Square and
Multiply'' Algorithmus,
$$\eqalign{
c_{n+1} &= \hbox{\bf if}\;e_n\;\hbox{ungerade}\;\hbox{\bf then}\; (c_n
b_n) \bmod m\;\hbox{\bf else}\;c_n,\cr
e_{n+1} &= \left\lfloor\frac{e_n}{2}\right\rfloor,\cr
b_{n+1} &= b_n^2 \bmod m,}\;$$
wo $c_0 = 1$, $e_0 = #2$, $b_0 = #1$ und $m = #3$.

Dieses wird iteriert, bis ein $i$ erreicht wird, wo $e_i = 0$ gilt:
\sam{#1}{#2}{#3}

Das Endergebnis ist demnach das $c_i$ der letzten Iteration $\uu{\the\c}$.
} \fi }

\def\crs#1#2#3#4#5#6{
\aufgabe Bestimmen Sie die L\"osungsmenge des
Gleichungssystem $$\modeq{x}{#1}{#2} \qquad \modeq{x}{#3}{#4} \qquad
\modeq{x}{#5}{#6}.$$
\ifmitloesungen
{\loesungsschrift

Gegeben sind die Parameter $(a_1, a_2, a_3) = (#1, #3, #5)$ und $(m_1,
m_2, m_3) = (#2, #4, #6)$.  Wir m\"ussen zun\"achst die
Zwischenparameter des Chinesischen Restsatzes berechnen:

\m = #2
\multiply \m by #4
\multiply \m by #6

\summe = 0

\produkt = #4
\multiply \produkt by #6
\item{$\bullet$} $q_1 = {\prod_{i=1}^3 m_i \over m_1} = #4 \cdot #6 = \the\produkt$
{
\inverse{#2}{\produkt}
\item{$\bullet$} $q_1^{-1} = \the\i$ bez\"uglich ${\Bbb Z}/#2{\Bbb Z}$
}
\multiply \produkt by \i
\multiply \produkt by #1
\advance \summe by \produkt

\produkt = #2
\multiply \produkt by #6
\item{$\bullet$} $q_2 = {\prod_{i=1}^3 m_i \over m_2} = #2 \cdot #6 = \the\produkt$
{
\inverse{#4}{\produkt}
\item{$\bullet$} $q_2^{-1} = \the\i$ bez\"uglich ${\Bbb Z}/#4{\Bbb Z}$
}
\multiply \produkt by \i
\multiply \produkt by #3
\advance \summe by \produkt

\produkt = #2
\multiply \produkt by #4
\item{$\bullet$} $q_3 = {\prod_{i=1}^3 m_i \over m_3} = #2 \cdot #4 = \the\produkt$
{
\inverse{#6}{\produkt}
\item{$\bullet$} $q_3^{-1} = \the\i$ bez\"uglich ${\Bbb Z}/#6{\Bbb Z}$
}
\multiply \produkt by \i
\multiply \produkt by #5
\advance \summe by \produkt

Es ist zu pr\"ufen ob jedes $(q_i, m_i)$ paarweise Teilerfremd sind
(trivial wenn alle $m_i$ verschiedene Primzahlen sind).

Eine L\"osung berechnet sich aus
\divmod{\summe}{\m}
$$x = \sum_{i=1}^3 a_iq_iq_i^{-1} = \modeq{\the\summe}{\the\r}{\the\m}$$
und daraus kann man die L\"osungsmenge
$${\Bbb L} = \left\{x \;\vert\; \modeq{x}{\uu{\the\r}}{\the\m} \right\}$$
bestimmen.
}
\fi
}

\def\bruch#1#2{\aufgabe Begr\"unden Sie, warum der Bruch $#1 \over #2$
eine endliche, reinperiodische oder gemischtperiodische
Dezimalbruchentwicklung hat.
\ifmitloesungen
{\loesungsschrift

Es ist als erstes notwendig den Bruch zu k\"urzen, indem man
{
\euclid{#1}{#2}
$$
\roman{ggT}(#1, #2) = \the\a
$$
berechnet, und damit dann
\x = #1 \divide \x by \a
\y = #2 \divide \y by \a
$$
{#1 \over #2} = {#1 / \the\a \over #2 / \the\a} = {\the\x \over \the\y}
$$
vereinfachen kann (das kann alles auch der Taschenrechner direkt f\"ur
einen machen).

Man betrachte den Nenner, und pr\"uft ob dieser dargestellt werden
kann durch die spezifische Primzahlendekomposition $\the\y = 2^i 5^j$,
f\"ur $i, j \in {\Bbb N}$?

\s = 0
\t = 0
\x = \y
\loop
    \divmod{\y}{2}
  \ifnum \r = 0
    \y = \q
    $\to_{\div 2} \the\y$
    \advance \s by 1
\repeat
\loop
    \divmod{\y}{5}
  \ifnum \r = 0
    \y = \q
    $\to_{\div 5} \the\y$
    \advance \t by 1
\repeat

\ifnum \y = 1
  Ja, der Nenner ist darstellbar durch die Primzahlendekomposition
  $2^{\the\s} 5 ^{\the\t}$.  Wir k\"onnen daraus schlie{\ss}en, der
  Bruch hat eine endliche BDE.
\else
  Nein, der Nenner ist darstellbar durch die Primzahlendekomposition.
  Als n\"achstes berechnen wir
  \euclid{\x}{10}
  $$\roman{ggT}(\the\x, 10) = \the\r$$
  \ifnum \r = 1
    Da der $\roman{ggT}$ gleich 1 ist, k\"onnen wir daraus
    schlie{\ss}en, der  Bruch eine rein-periodische BDE hat.
  \else
    Da der $\roman{ggT}$ nicht gleich 1 ist, k\"onnen wir daraus
    schlie{\ss}en, der  Bruch eine gemischt-periodische BDE hat.
  \fi
\fi
}
}
\fi
}

% From https://tex.stackexchange.com/questions/36034
\def\reverse #1%
  {\edef #1{\expandafter \reverseloop #1\relax \marker }}
\def\reverseloop #1#2\marker
  {\ifx#1\relax\reverseend\fi \reverseloop #2\marker #1}
\def\reverseend #1\marker #2{}

\def\basis#1#2{\aufgabe Bestimmen Sie die Darstellung der Zahl #1 zur
Basis #2.
\ifmitloesungen
{\loesungsschrift

Um die Darstellung der Zahl zur Basis #2 zu bestimmen, teilen wir #1
iterativ bis nichts mehr \"ubrig bleibt und merken uns die Restwerte:
\tracedivtrue
\q = #1
\str = {}
\loop
  {
    \divmod{\q}{#2}
    \global\q = \q
    \global\r = \r
  }
  \ifcase\r
    \str=\expandafter{\the\str 0}\or
    \str=\expandafter{\the\str 1}\or
    \str=\expandafter{\the\str 2}\or
    \str=\expandafter{\the\str 3}\or
    \str=\expandafter{\the\str 4}\or
    \str=\expandafter{\the\str 5}\or
    \str=\expandafter{\the\str 6}\or
    \str=\expandafter{\the\str 7}\or
    \str=\expandafter{\the\str 8}\or
    \str=\expandafter{\the\str 9}\or
    \str=\expandafter{\the\str a}\or
    \str=\expandafter{\the\str b}\or
    \str=\expandafter{\the\str c}\or
    \str=\expandafter{\the\str d}\or
    \str=\expandafter{\the\str e}\or
    \str=\expandafter{\the\str f}\else
    \errmessage{Radix overflow}
  \fi
\ifnum 0 < \q
\repeat
\tracedivfalse

\edef\result{\the\str}
\reverse\result

In dem man die Reste von unten nach oben durchlie{\ss}t, k\"onnen wir
das Endergebnis $\uu{\result_{(#2)}}$ bestimmen.

}
\fi
}

% Hier steht der Inhalt der Klausur, und nur hier muss man etwas
% anpassen wenn man einen neuen Braindump schreiben will:
\kopf{2024-02-01}

\ggt{47753}{89787}
\repr{356}{47}
\rest{9}{322}{11}
\crs{2}{13}{3}{11}{3}{7}
\bruch{1980}{3315}
\basis{423}{5}

\bye

%%% Local Variables:
%%% mode: plain-tex
%%% TeX-engine: xetex
%%% TeX-master: t
%%% End: