\(\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?
Kongruencja - brak elementu odwrotnego
Kongruencja - brak elementu odwrotnego
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ę.