Kongruencja - brak elementu odwrotnego

[jackblack]

\(\displaystyle{ 28x = 7(mod 49)}\)

Szukam elementu odwrotnego do 28 rozszerzonym algorytmem Euklidesa.

\(\displaystyle{ 28v+49w = 1}\)

\(\displaystyle{ 49 = 28 \cdot 1+21}\)
\(\displaystyle{ 28 = 21 \cdot 1+7}\)
\(\displaystyle{ 21=7 \cdot 3+0}\)

Powinienem w jednym z tych równań odtrzymać jedynkę, wstawić do wzoru i liczyć dalej.
Tym czasem tej jedynki nie ma. Co to oznacza? Równanie nie ma rozwiązania?

[szw1710]

Z równania \(\displaystyle{ 28x=49k+7}\) mamy natychmiast \(\displaystyle{ 4x=7k+1}\), więc przechodzimy na działanie modulo \(\displaystyle{ 7}\). Znajdź odpowiednie \(\displaystyle{ x}\) (myślę oczywiście o wszystkich \(\displaystyle{ x}\)) i sprawdź, że spełnia wyjściową relację.

[jackblack]

Dziękuję Panu.

EDIT:

Ale chwila, czyli teraz po prostu rozwiązać równanie
\(\displaystyle{ 4x = 1 mod 7}\) ?

[szw1710]

Tak