Witam.
Jak sprawdzić czy 25 ma element odwracalny w \(\displaystyle{ Z_{72}}\) i jak go wyznaczyć??
Z góry dzięki!
Element odwracalny
-
- Użytkownik
- Posty: 2278
- Rejestracja: 11 kwie 2007, o 18:49
- Płeć: Kobieta
- Lokalizacja: Dąbrowa Górnicza
- Podziękował: 41 razy
- Pomógł: 602 razy
Element odwracalny
\(\displaystyle{ NWD(72,25)=1\\
72=2\cdot 25+22\\
25=1\cdot 22+3\\
22=7\cdot 3+1}\)
zatem: \(\displaystyle{ 1=22-7\cdot 3=22-7(25-1\cdot 22)=22-7\cdot 25+7\cdot 22=8\cdot 22-7\cdot 25=8(72-2\cdot 25)-7\cdot 25=8\cdot 72-16\cdot 25-7\cdot 25=8\cdot 72-23\cdot 25}\)
czyli \(\displaystyle{ 25^{-1}=-23=49 (mod 72)}\)
72=2\cdot 25+22\\
25=1\cdot 22+3\\
22=7\cdot 3+1}\)
zatem: \(\displaystyle{ 1=22-7\cdot 3=22-7(25-1\cdot 22)=22-7\cdot 25+7\cdot 22=8\cdot 22-7\cdot 25=8(72-2\cdot 25)-7\cdot 25=8\cdot 72-16\cdot 25-7\cdot 25=8\cdot 72-23\cdot 25}\)
czyli \(\displaystyle{ 25^{-1}=-23=49 (mod 72)}\)