Zadania z kongruencjami i algorytmem Euklidesa.

[trivim]

Proszę o pomoc z poniższymi zadaniami:

2.
\(\displaystyle{ x\equiv 1 mod7}\)
\(\displaystyle{ x\equiv 7 mod10}\)
\(\displaystyle{ x\equiv 10 mod11}\)

3. Stosując algorytm Euklidesa wyznaczyć liczby \(\displaystyle{ a,b \in Z}\) takie że
\(\displaystyle{ 97a + 17b= 1}\). Obliczyć \(\displaystyle{ 97^{-1} mod17 , 17^{-1} mod 97}\)

[Fl3t05]

2. ... yk.C5.82ad <- przeanalizuj i sprobuj rozwiazac.

3. Wiemy jak dziala algorytm Euklidesa? Poszukaj przykladow rozwiazania rownania diofantycznego.

[trivim]

\(\displaystyle{ x = 1 + 7i}\)
dla \(\displaystyle{ i = 8:\ x = 1 + 56 \pmod{10} = 7 \rightarrow}\)
czyli spełnia założenia z 2 równania

teraz mamy \(\displaystyle{ 57 \equiv (7 \cdot 10) \rightarrow x = 57 + 70i}\)

\(\displaystyle{ 57 + 2 \cdot 70 = 197 \pmod{11} = 10}\)

czyli całość \(\displaystyle{ 197 + (7 \cdot 10 \cdot 11)K}\)

o takie coś chodzi ?

Nie ma jakiegoś bardziej "naukowego" sposobu na liczenie tego ? Z tego co pamiętam na zajęciach liczyliśmy to trochę inaczej.


W tym trzecim mam znaleźć największy wspólny dzielnik \(\displaystyle{ 97}\) i \(\displaystyle{ 17}\) ? Jeżeli tak to co dalej ?

[bakala12]

Nie ma jakiegoś bardziej "naukowego" sposobu na liczenie tego ? Z tego co pamiętam na zajęciach liczyliśmy to trochę inaczej.

... ongruencji

\(\displaystyle{ 97a + 17b= 1}\)

Znajdź \(\displaystyle{ a,b}\) korzystając z rozszerzonego algorytmu Euklidesa.