Zadania z modulo

[Krodinor]

1. Rozwiązać kongurencje \(\displaystyle{ 3x\equiv 7 \pmod{11}}\)
Wystarczy pomnożyć razy \(\displaystyle{ 4}\) i dostaniemy, że \(\displaystyle{ x\equiv 6\pmod{11}}\)?

2. Do jakiej reszty przystaje \(\displaystyle{ 3^{10536}\mod{11}}\)?
Tutaj nie mam za bardzo pomysłu.

[szw1710]

2. Wskazówka: \(\displaystyle{ 3^5\equiv 1}\)

[ajlofmath]

W pierwszym taktycznym ruchem było by równanie \(\displaystyle{ 3x+4=11y}\)
W drugim dzięki Eulerowi wiemy, że
\(\displaystyle{ 3 ^{10530} \equiv 1\pmod{11}}\)
Więc \(\displaystyle{ 3 ^{10536} \equiv 3 ^{6}\pmod{11}}\)

Można też zauważyć, że \(\displaystyle{ 3 ^{5} \equiv 1\pmod{11}}\)
zatem \(\displaystyle{ 3 ^{10535} \equiv 1\pmod{11}}\)

[Krodinor]

A zatem wynik w drugim to będzie \(\displaystyle{ 3\mod 11}\)?

W pierwszym natomiast rozumiem, że trzeba jeszcze zauważyć, że \(\displaystyle{ NWD(3,11)}\) to \(\displaystyle{ 1}\), ale czy poza tym jest dobrze?

[ajlofmath]

3 i 11 są pierwsze, więc pominąłem to sprawdzenie i tak jest dobrze, bo to podnosisz \(\displaystyle{ 3 ^{10}}\) do potęgi 1053 to samo robisz z jedynką, więc masz jeden.

[Krodinor]

Czyli ostatecznie rozwiązania to:
1. \(\displaystyle{ x\equiv 6\pmod{11}}\)
2. \(\displaystyle{ 3 \mod 11}\)

[ajlofmath]

Czy coś ci wskazuje, że może być inaczej.