Znajdź rozwiązanie kongurencji

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
ivonek
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 12 paź 2010, o 17:19
Płeć: Kobieta
Lokalizacja: łódź
Podziękował: 1 raz

Znajdź rozwiązanie kongurencji

Post autor: ivonek »

\(\displaystyle{ 29x \equiv 1(mod 17)}\)
kompletnie nie wiem jak się za to zabrać, posiadam rozwiązanie, ale nie rozumiem go. Jak zastosować algorytm euklidesa w takim zadaniu ?
\(\displaystyle{ 17 | 29x -1}\), czyli
\(\displaystyle{ 29x - 1 = 17y}\)
\(\displaystyle{ 29x - 17y = 1}\)
i co dalej?
jak robię algorytm euklidesa dla 29 to dostaje \(\displaystyle{ 12*17 - 7*29}\)
brzoskwinka1

Znajdź rozwiązanie kongurencji

Post autor: brzoskwinka1 »

\(\displaystyle{ x\equiv 10 (\mbox{mod} 17 )}\)
Awatar użytkownika
vpprof
Użytkownik
Użytkownik
Posty: 492
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 26 razy
Pomógł: 64 razy

Znajdź rozwiązanie kongurencji

Post autor: vpprof »

ivonek pisze:jak robię algorytm euklidesa dla 29 to dostaje \(\displaystyle{ 12*17 - 7*29}\)
No i dobrze dostajesz, wszak \(\displaystyle{ -7 \equiv 10 \pmod{17}}\)
ODPOWIEDZ