arytmetyka studia help: Znaleźć, jeśli istnieje element odwrotny do k modulo n: k = 35, n = 101. Prosiłbym o rozwiązanie element istnieje bo NWD = 1, niestety nie wiem jak to zapisać, żeby Pan profesor nie miał uwag. Wcześniejsze zadanie jakie miałem miało małe liczby i wystarczyło podstawiać kolejne liczby naturalne, tu jednak przy 9 już zwątpiłem, czy jest na to jakiś matematyczny sposób ? Z góry bardzo dziekuję

Adamm: 35x=1 mod 101 algorytm Euklidesa 101=2*35+31 35=31+4 31=7*4+3 4=3+1 podstawiamy odwrotnie 1=4−3 1=4−(31−7*4)=8*4−31 1=8*(35−31)−31=8*35−9*31 1=8*35−9*(101−2*35)=26*35−9*101 zatem 26*35=1 mod 101 skąd elementem odwrotnym jest 26