Element odwrotny 14 modulo 31. Ciemny123321: Witam, zadanie : Znajdz element odwrotny do 14 modulo 31. A więc NWD(31,14) = d 31 = 2 * 14 + 3 14 = 4 * 3 + 2 3 = 1 * 2 + 1 d = 1 NWD(31,14) = 1, więc element odwrotny istnieje. Tylko nie wiem co dalej. A średnio rozumiem wszystko co wygooglam, czy to będzie wyglądać : x * 14 (mod 31) − przystaje do 1 (mod 31) ? i szukac x? Pozdrawiam

Trivial: Tu podobny problem. https://matematykaszkolna.pl/forum/212333.html

Ciemny123321: Hmm czyli do takiej treści zadania mogę sobie napisać kongurencję x * 14 (mod 31) przystaje do 1 (mod 31) , jeśli tak to : 1 = 3 − 1 * 2 = = 3 − 1 * (14 − 4 * 3) = = −1 * 14 − 5 * 3 = = −1 * 14 − 5 * (31 − 2 * 14) = −5 * 31 + 9 * 14 −−−−−−−−−−−−−−−−−−−−−−−− − 5 * 31 znika bo k * 31 (mod 31) zawsze bedzie 0 gdzie k nalezy do z wiec elementem odwrotnym jest 9, mam rajcę?

Ciemny123321: Chwila, podstawiłem pod x = 9 I mi wyszlo 2 (mod 31) przystaje do 1 (mod 31) Czy to moj blad rozumowania czy blad obliczen?

Trivial: Łatwo sprawdzić poprawność, wystarczy pomnożyć 14*9 i sprawdzić, czy wyjdzie 1 (mod 31). 14*9 = 126 = 4*31 + 2 ≡ 2 (mod 31) Nie, nie masz racji.

Ciemny123321: Właśnie widzę, a podpowiesz mi jeszcze czy to błąd obliczeń czy rozumowania?

wredulus_pospolitus: = 3 − 1 * (14 − 4 * 3) = = −1 * 14 + 5 * 3 =

Trivial: 1 = 3 − 1*2 = 3 − 1*(14 − 4*3) = 5*3 − 1*14 = 5*(31 − 2*14) − 1*14 = 5*31 − 11*14 −11*14 = −154 = (−5)*31 + 1 ≡ 1 (mod 31). Zatem elementem odwrotnym jest −11 ≡ 20 (mod 31).

wredulus_pospolitus: błąd w obliczeniach

Ciemny123321: Skończyłem sprawdzać 3 raz − okazało się że jak zwykle pochrzaniłem znaki − chciałem napisać ale widzę uprzedziliście mnie. Dzięki za pomoc !