Rozwiązać kongruencje

[karl153]

\(\displaystyle{ 5x\equiv 1 \pmod{11}}\)
rozw.
\(\displaystyle{ 5x\equiv 1 \pmod{11} / \cdot 9}\)
\(\displaystyle{ 45x\equiv 9 \pmod{11}}\)
\(\displaystyle{ x\equiv 9 \pmod{11}}\)
\(\displaystyle{ x=11k+9}\), dla pewnego \(\displaystyle{ k \in Z}\)
Przez 9 ponieważ:
\(\displaystyle{ NWD(5,11)=NWD(5,1)=1}\)
\(\displaystyle{ 1=11-2 \cdot 5}\)
\(\displaystyle{ 1\equiv (-2) \cdot 5 \pmod{11}}\)
\(\displaystyle{ -2\equiv 9 \pmod{11}}\)
No o.k ale jak by ktoś mógł wyjaśnić linijka po linijce będę bardzo wdzięczny.

[radwaw]

\(\displaystyle{ 5x \equiv 1 \pmod{11}}\)

\(\displaystyle{ 5x \equiv 1 \pmod{11}}\) mnożę stronami przez 9

\(\displaystyle{ 45x \equiv 9 \pmod{11}}\) odejmuję stronami \(\displaystyle{ 44x \equiv 0 \pmod{11}}\)

\(\displaystyle{ x \equiv 9 \pmod{11}}\) z definicji kongruencji orzymujemy równość

\(\displaystyle{ x = 11k + 9}\) łatwo sprawdzić, że jest to prawdą dla każdego \(\displaystyle{ k \in Z}\)

gdzie \(\displaystyle{ Z}\) to zbiór zawierający wszystkie całkowite nie wiem po co ten bełkot o NWD

[karl153]

mógłbyś wyjaśnić dlaczego akurat przez \(\displaystyle{ 9}\) potem \(\displaystyle{ 44}\) ?
Czy to jest równoważne temu: \(\displaystyle{ x=11k-2}\) ?

[radwaw]

przez 9 a potem -44 bo dążymy do postaci

\(\displaystyle{ x \equiv}\) "coś" \(\displaystyle{ \pmod{11}}\)

\(\displaystyle{ -2 \equiv 9 \quad \pmod{11}}\) (to chyba rozwiązuje twój problem)

[karl153]

ok, tutaj jest \(\displaystyle{ \pmod{11}}\) więc moim \(\displaystyle{ x}\) będzie liczba \(\displaystyle{ 0-10}\), ale jak się ma taki sposób do takiego przykładu: \(\displaystyle{ 24x\equiv 42 \pmod{101}}\) tutaj tak ławo już sobie nie odgadnę przez co pomnożę, co odejmę bo już mam przedział \(\displaystyle{ 0-100}\) może dlatego prowadzący wprowadził NWD() bo wiąże się to z jakąś metodą ?

[Sambard]

W tym zadaniu chodzi o wyznaczenie odwrotności liczby \(\displaystyle{ 5}\) \(\displaystyle{ \pmod {11}}\), a ten bełkot o NWD to chyba bardzo skrócone wykorzystanie rozszerzonego algorytmu Euklidesa.

P. S. Moim zdaniem dużo ładniejszy sposób obliczania tego pokazano tu: 196822.htm