Obliczyć

[gollum]

Oliczyć \(10^{-1} mod 67\) może ktoś mi powiedzieć po kolei co zrobić?

[sebnorth]

\(67 = 6 \cdot 10 + 7 \\

10 = 1 \cdot 7 + 3 \\

7 = 2 \cdot 3 + 1\)

czyli:

\(1 = 7 - 2 \cdot 3 = 67 - 6\cdot 10 - 2 \cdot (10 - 1 \cdot 7 ) = 67 - 8\cdot 10 + 2 \cdot ( 67 - 6\cdot 10) = \\

= 3\cdot 67 - 20 \cdot 10\)

modulo \(67\):

\(1 = (- 20) \cdot 10 = 47 \cdot 10\)

czyli \(10^{-1} = 47\)

[gollum]

jest jakiś wzór na to?

[sebnorth]

nie bardzo, raczej algorytm Euklidesa, chodzi o to, żeby znaleźć całkowite \(x,y\) takie, że \(ax + by = NWD(a,b)\)

w tym zadaniu \(NWD(a,b) = 1\)

[gollum]

zakładając że a=19, b=67?

[sebnorth]

w poście na początku było \(10\) nie \(19\)

[gollum]

tak tak, pomyliło mi się z innym przykładem. oczywiście chodziło mi o 10

[sebnorth]

tak, wtedy \(a = 19, b = 67\) albo \(a = 67, b = 19\)