Ein Repository für den Kurs Lineare Algebra 1, WiSe 2020–21.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1.4 KiB

Berechnung von $a^{b}\mod c$

Ein Beispiel:

Berechne $13^{1003}\mod 5$.

Es gilt $13^{1003}\mod 5=3^{1003}\mod 5$

Jetzt berechnen wir tabellarisch die multiplikative Untergruppe $\langle 3\rangle$:

$n$ $3^{n}$
$0$ $3^0=\boxed{1}$
$1$ $3^{1}=\boxed{3}$
$2$ $3^{2}=9\equiv \boxed{4}$
$3$ $3^{3}=3^2\cdot 3\equiv 4\cdot 3 =12\equiv \boxed{2}$
$4$ $3^{\boxed{4}}=3^3\cdot 3\equiv 2\cdot 3 =6\equiv \boxed{1}$

Darum gilt für alle $k,r\in\mathbb{N}$:

$3^{4k+r}=3^{4k}\cdot 3^{r}=(3^{4})^{k}\cdot 3^{r}\equiv 1^{k}\cdot 3^{r}=1\cdot 3^{r}=3^{r}$

modulo $5$. Das heißt, es reicht aus (in diesem konkreten Fall) den Exponenten modulo $4$ zu berechnen, und dann $3^{\text{Rest}}$ zu berechnen:

$1003=4\cdot 250 + \boxed{3}$

Also gilt $3^{1003}\equiv 3^{3}\equiv 2\mod 5$.

Beachte! Wenn $n\in\mathbb{P}$ (wie oben), dann für $k\in{1,2,\ldots,n-1}$ gilt $k^{e}\not\equiv 0$. Warum? (1) da $n$ prim ist, ist jedes $1\leq a <n$ invertierbar (bzgl. Multiplikation) in $\intgr/n\intgr$. Sei $a$ das Inverse von $k$. Dann gilt $a^{e}\cdot k^{e} = (ak)^{e}\equiv 1^{e}=1$, sodass $k^{e}$ bzgl. Multiplikation invertierbar ist und damit insbesondere niemals gleich $0$ sein kann (modulo $n$).

Aber, wenn $n\notin\mathbb{P}$, dann kann es durchaus sein, dass ein $k\in{1,2,\ldots,n-1}$ existiert, so dass $k^{e}\equiv 0\mod n$ für ein $e\in\ntrl$. Zum Beispiel $n=81$ und $k=3$. Dann $k^{4}\equiv 0\mod n$.