modulo z niewiadomą

[zander666]

Witam,
zwracam się z gorącą prośbą aby ktoś pomógł mi obliczyć niewiadomą z tego równania:
\(\displaystyle{ 17 \cdot d \pmod{3120} \equiv 1}\)

W miarę możliwości prosiłbym też o tzw. "łopatologiczne" wytłumaczenie co, z czego, gdzie i jak.
Z góry dziękuję,
zander

[bb314]

\(\displaystyle{ \blue 17 \cdot d \pmod{3120} \equiv 1}\)

\(\displaystyle{ 17\cdot d=k\cdot 3120+1\ \ \ -}\) gdzie \(\displaystyle{ k}\) jest dowolną liczbą całkowitą (dodatnią lub ujemną)

\(\displaystyle{ d=\frac{k\cdot3120+1}{17}}\)

[Ponewor]

Nie wiem dlaczego odrzuciłaś \(\displaystyle{ k=0}\), a zostawiłaś dodatnie i ujemne. Ponadto, a raczej przede wszystkim \(\displaystyle{ d}\) powinno być całkowite, a u Ciebie wystarczy położyć \(\displaystyle{ k=1}\), by przekonać się, że nie jest. Trzeba by rozstrzygnąć dla jakich \(\displaystyle{ k}\):
\(\displaystyle{ k \cdot 3120 \equiv -1 \pmod{17}}\), co jest po prostu inaczej zapisaną treścią zadania i rozwiązanie tego twoją metodą spowodowałoby powrót do wyjściowego równania.

[zander666]

Dziękuję za odpowiedź, ale niestety nic mi to nie daje. A to dlatego, że z mojego punktu widzenia (człowieka którego piętą achillesową jest matematyka), aby obliczyć niewiadomą \(\displaystyle{ d}\) potrzebna jest mi niewiadoma \(\displaystyle{ k}\). Dodam jeszcze, że w zadaniu które próbuję rozwiązać z waszą pomocą \(\displaystyle{ d = 2753}\). Natomiast nie jest podana metoda jego obliczenia, a to jest mi potrzebne.

[Ponewor]

\(\displaystyle{ 17d-3120k =1}\), a ponieważ \(\displaystyle{ \nwd \left(17, \ 3120 \right)=1}\), to można skorzystać tutaj z rozszerzonego algorytmu Euklidesa.

[zander666]

Coś przeczuwałem, że pojawi się tu właśnie rozszerzony algorytm Euklidesa. Problem w tym, że absolutnie nie mam pojęcia jak ten algorytm wykorzystać.

[Ponewor]

A czy informacje z wiki, bądź Googla nie wystarczą? Jak nie, to proszę tutaj zapisać obliczenie \(\displaystyle{ nwd}\) za pomocą algorytmu.