Odwrotność modulo, kongruencja Paweł: Witam, potrzebuje pomocy w znalezieniu błędu, mianowicie poszukuje odwrotności liczby 1878 w modulo 673 aby rozwiązać kongruencje 1878 (przystaje) 1 (mod 673) Zaczynam od zastosowania roz. algorytmu Euklidesa: 1878 = 2 x 673 + 532 673 = 1 x 532 + 141 532 = 3 x 141 + 109 141 = 1 x 109 + 32 109 = 3 x 32 + 13 32 = 2 x 13 + 6 13 = 2 x 6 + 1 6 = 1 x 6 + 0 następnie korzystając ze wzoru w_n = w_i−2 − q_i−1 x w_i−1 (mod r₀) w₀ = 0 , w₁ = 1 w₂ = 0 − 2x1 = 671 mod 673 w₃ = 1 − 1x671 = 3 mod 673 w₄ = 671 − 3x3 = 662 mod 673 w₅ = 3 − 1x662 = 14 mod 673 w₆ = 662 − 3x14 = 620 mod 673 w₇ = 14 −2x620 = 120 mod 673 w₈ = 620 − 2x120 = 380 mod 673 wychodzi 380 a poprawny wynik to 105

Iryt: Odwrócony algorytm: 1=13−2*6=13−2*(32−2*13)=13−2*32+4*13=5*13−2*32= =5*(109−3*32)−2*32=5*109−17*32=6*109−17*(141−1*109)=−17*141+22*109= =−17*141+22*(532−3*141)=−83*141+22*532= =−83*(673−1*532)+22*532=105*532−83*673= =105*(1878−2*673)−83*673=105*1878−210*673−83*673= =105*1878−293*673 =================

Paweł: Dziękuję za odpowiedz , tą metodą również udało mi się poprawnie rozwiązać zadanie. Jakiś pomysł dlaczego metoda z w_n nie działa w tym przypadku?