Úloha takéhoto typu je detailne vyriešená v inom topicu (akurát sú tam iné čísla): viewtopic.php?t=1346Overte, že $113$ je prvočíslo. Vypočítajte pomocou Euklidovho algoritmu čomu sa rovná $\inv a$ v $\mathbb Z_{113}$ pre $a=42$.
Takže sem iba napíšem priamo výpočty
$$
\begin{array}{|c|c|c|}
\hline
&113&42 \\\hline
113 & 1 & 0 \\\hline
42 & 0 & 1 \\\hline
13 &-1 & 3 \\\hline
3 & 3 &-8 \\\hline
1 &-13&35 \\\hline
\end{array}
$$
Dostali sme, že $$1=113\cdot(-13)+42\cdot35,\tag{*}$$ z čoho vidíme aj to, že v $\mathbb Z_{113}$ platí $42\cdot35=1$, a teda
$$\inv{42}=35.$$
Samozrejme, priamym výpočtom si vieme ľahko skontrolovať, či sme sa nepomýlili a rovnosť $(*)$ skutočne platí.
Spoiler:
\begin{align*}
6\cdot19&=114\\
7\cdot16&=112
\end{align*}
Teda v $\mathbb Z_{113}$ platia rovnosti $6\cdot19=1$ a $7\cdot16=-1$, t..
\begin{align*}
\inv 6&=19\\
\inv 7&=-16=97
\end{align*}
Potom ak ešte trochu počítame v $\mathbb Z_{113}$, tak dostaneme
$$\inv{42}=\inv{(7\cdot6)}=\inv6\cdot\inv7=-19\cdot16=35.$$
(Pri tomto výpočet bolo treba spočítať čomu sa rovná $19\cdot16$ modulo $113$.)
Zadanie bolo také, že som chcel, aby ste naozaj použili Euklidov algoritmus; ale chcel som aspoň spomenúť, že niečo čo je pomerne blízko výsledku sa dalo aj zbadať. (Resp. že aspoň pre niektoré prvky - ako napríklad $6$ a $7$ - sa dal multiplikatívny inverz pomerne ľahko zbadať.)