Wyznacz wszystkie wartości x spełniające podane kongruencje

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
KubaK96
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 5 maja 2016, o 19:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 5 razy

Wyznacz wszystkie wartości x spełniające podane kongruencje

Post autor: KubaK96 »

W każdym z podanych przypadków, wyznacz wszystkie wartości \(\displaystyle{ x}\) spełniające podane kongruencje:
a) \(\displaystyle{ 3x \equiv 5\pmod{7}}\)
b) \(\displaystyle{ 13x \equiv 2\pmod{7}}\)
c) \(\displaystyle{ 110x \equiv 2\pmod {273}}\)
Proszę o pomoc.
Wiem, że na początku muszę policzyć NWD (dla a) \(\displaystyle{ NWD(3,7)}\) i tak dalej)
potem z rozszerzonego algorytmu Euklidesa: \(\displaystyle{ r=a-b \cdot q}\)
W pierwszym podpunkcie dochodzę do momentu \(\displaystyle{ 1=7-3 \cdot 2}\) a dalej nie wiem co robić
Ostatnio zmieniony 22 maja 2016, o 19:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Częściowy brak LaTeX-a. Temat umieszczony w złym dziale.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Wyznacz wszystkie wartości x spełniające podane kongruencje

Post autor: Premislav »

Proponuję poczytać np. lub

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Algorytm_Euklidesa#Rozszerzony_algorytm_Euklidesa
.

Chyba nie oczekujesz, że będziemy Ci wykładać teorię...
dec1
Użytkownik
Użytkownik
Posty: 714
Rejestracja: 21 mar 2016, o 21:42
Płeć: Mężczyzna
Pomógł: 191 razy

Wyznacz wszystkie wartości x spełniające podane kongruencje

Post autor: dec1 »

1)
\(\displaystyle{ 3x\equiv 5\,\, (\mathrm{mod}\,\, 7) \\
x\equiv 5\cdot3^{-1} \,\,(\mathrm{mod}\,\, 7)\\
3^{-1} \,\,\mathrm{mod}\,\, 7 = 5 \\
5\cdot 5 \,\,\mathrm{mod}\,\, 7 = 4 \\
x\equiv 4\,\, (\mathrm{mod}\,\, 7)\\
x=7k+4}\)
Ukryta treść:    
ODPOWIEDZ