wat een saai-ogende vragen

We zoeken $x$ zodat $7 \cdot x^{25} \equiv 10 \pmod{83}$
$$\iff x^{25} \equiv \frac{10}{7} \equiv 37 \pmod{83}$$ want $37 \cdot 7 - 10 = 83 \cdot 3$.
We willen de exponent van $x$ reduceren tot $1$. Merk op dat wegens de kleine stelling van Fermat geldt dat $x^{82} \equiv 1 \pmod{83}$ (tenzij $x=83$, maar dat is duidelijk geen oplossing).
Merk vervolgens op dat wegens Bézout er gehele getallen $a,b$ bestaan op dat $25a-82b=1$ een oplossing heeft, daar $gcd(25,82) = 1$. We vinden dat $a=23, b=7$ deze oplossing geven.
Nu geldt er dat $$(x^{25})^{23} \equiv x^{575} \equiv x^{82 \cdot 7} \cdot x \equiv x \equiv 37^{23} \pmod {83}.$$
Nu is $37^2 = 1369 \equiv 41 \pmod{83},
37^4 \equiv 41^2 = 1681 \equiv 21 \pmod{83}, 37^8 \equiv 21^2 = 441 \equiv 26 \pmod{83}$ en $37^{16} \equiv 26^2 = 676 \equiv 12 \pmod{83}.$

Dat betekent dat $x \equiv 12 \cdot 21 \cdot 37 \cdot 41 \pmod{83}.$
Nu is $12 \cdot 21 = 252 \equiv 3 \pmod {83}$
Ook is $37 \cdot 3 = 111 \equiv 28 \pmod {83}$
en $28 \cdot 41 \equiv (2 \cdot 41) \cdot 14 \equiv -1 \cdot 14 \equiv 69 \pmod{83}$
Dus $x \equiv 69 \pmod {83}$ en bijgevolg is $x = 69$ de kleinste oplossing.