Element odwrotny Mera: jak najszybciej policzyć 11⁻¹ mod 142?

iryt: Algorytm Euklidesa, albo tabliczka mnożenia. 11x≡1 (mod142) /*13 143x≡13 (mod142) 142x+1x≡13 (mod142) 1x≡13 (mod142)

Mera: dlaczego mnożysz *13?

iryt: Liczę wielokrotności 11 bliskie 142. 11*11=121 nie pasuje 11*12=132 nie pasuje 11*13=143=142+1 11*13=1 (mod142)

Mera: dzięki bo ogólnie liczyłam to z nwd, ale czasem potrzebuję element odwrotny tak na szybko, a tamto jest dość zajmujące czasowo

Mera: a jakoś nie mogę policzyć 27⁻¹ mod71

iryt: Tu trzeba raczej z algorytmu. NWD(71,27)=1 Próbowałaś? 27⁻¹ to 50 71=2*27+17 27=1*17+10 17=1*10+7 10=1*7+3 7=2*3+1 1=1*7−2*3=1*7−2*(10−1*7)=1*7−2*10+2*7=3*7−2*10= =3*(17−1*10)−2*10=3*17−3*10−2*10=3*17−5*10= =3*17−5*(27−1*17)=3*17−5*27+5*17=8*17−5*27= =8*(71−2*27)−5*27=8*71−16*27−5*27=8*71−21*27 −21+71=50

Mera: z algorytmu robiłam, ale myślałam, że każdy przykład może da się tak szybko zrobić z mnożenia. Czyli ogólnie, kiedy można stosować ten trik z mnożeniem?

iryt: Jeżeli masz dość małe n w modulo.