Zadania z kongruencji

[brunetka11]

Podaj najmniejszą liczbę naturalną, która spełnia następujący układ kongruencji:

\(\displaystyle{ \begin{cases} x \equiv 1 (mod 29) \\ x \equiv 2 (mod 31) \\ x \equiv 3 (mod 53) \end{cases}}\)

Podaj najmniejszą liczbę naturalną, która spełnia następujący układ kongruencji:

\(\displaystyle{ \begin{cases} x \equiv 1 (mod 10) \\ x \equiv 2 (mod 9) \\ x \equiv 3 (mod 11) \\ x \equiv 4 (mod 29) \end{cases}}\)

Podaj liczbę dodatnich rozwiązań układu kongruencji
\(\displaystyle{ \begin{cases} x \equiv 1 (mod 101) \\ x \equiv 2 (mod 102) \\ x \equiv 3 (mod 103) \end{cases}}\)
mniejszych od 106

Czy układ kongruencji
\(\displaystyle{ \begin{cases} x \equiv 1 (mod 1111) \\ x \equiv 22 (mod 22222) \\ x \equiv 444 (mod 444444) \end{cases}}\)
ma rozwiązanie?

Znajdź najmniejszą liczbę x taką, że \(\displaystyle{ \phi (x)=44}\)

Podaj liczbę elementów odwracalnych w pierścieniu \(\displaystyle{ \Z_{1440}.}\)

Podaj liczbę rozwiązań równania \(\displaystyle{ \phi(x) = 22.}\)

Jaka jest reszta z dzielenia liczby \(\displaystyle{ 7^2222}\)przez 10?

Podaj dwie ostatnie cyfry liczby \(\displaystyle{ 82^{82}.}\)

Bardzo proszę o pomoc mam 4 godziny zeby wysłać to wykładowcy !!! Niektóre z tych zadań mam rozwiązane ale nie jestem pewna .. Z góry dziękuje za pomoc !!

[arek1357]

A ja z dołu proszę o czytelność.

[zuza995]

Podpisuję się pod prośbą o pomoc w rozwiazaniu.

[Chewbacca97]

Którym? Jakieś próby samodzielnego rozwiązania? Jakieś wątpliwości? Gdzie jest problem?

[zuza995]

Wykładowca nam tego nie wyjasniał, a musimy to rozwiązać...-- 29 lis 2016, o 23:32 --Zawsze jak wyliczam z pierwszych dwoch k, to jest ono takie ze nic sie nie da z nim zrobic. Nie umiem szukac x przy trzech rownaniach (wychodzilo mi np. 22k, a potem potrzebowalam po prostu k)

[Chewbacca97]

Zadanie pierwsze.
Zajmiemy się najpierw pierwszymi dwoma równaniami:
\(\displaystyle{ \begin{cases} x \equiv {\blue 1} \pmod {29} \\ x \equiv {\red 2} \pmod {31} \end{cases}}\)

Ponieważ \(\displaystyle{ \left( 29,31\right) = 1}\), to istnieją takie liczby \(\displaystyle{ a}\) i \(\displaystyle{ b}\), że \(\displaystyle{ 29a + 31b = 1}\). Korzystając z rozszerzonego algorytmu Euklidesa, otrzymujemy: \(\displaystyle{ a=15}\) oraz \(\displaystyle{ b=-14}\). Teraz wiemy, że \(\displaystyle{ x \equiv {\red 2} \cdot 29a + {\blue 1} \cdot 31b \pmod {29 \cdot 31}}\), a wiemy to konkretnie z Chińskiego Twierdzenia o resztach. Choć zapewne wynika to jeszcze z jakichś innych własności. Ostatecznie: \(\displaystyle{ x \equiv 2 \cdot 29 \cdot 15 - 1 \cdot 31 \cdot 14 \equiv 436 \pmod{899}}\).

Nasz układ wygląda teraz tak:
\(\displaystyle{ \begin{cases} x \equiv 436 \pmod {899} \\ x \equiv 3 \pmod {53} \end{cases}}\)

Powtarzając czynność opisaną powyżej powinnaś dostać: \(\displaystyle{ x \equiv 28305 \pmod{47647}}\), co oznacza, że iks jest postaci \(\displaystyle{ 47647k + 28305}\) dla \(\displaystyle{ k\in\ZZ}\). Czyli najmniejsza liczba naturalna to \(\displaystyle{ 28305}\).

[zuza995]

Dziękuję a ja się z tym czwartą godzinę męczę

[Chewbacca97]

Zadanie czwarte.
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod {1111} \\ x \equiv 22 \pmod {22222} \\ x \equiv 444 \pmod {444444}\end{cases}}\)

Pytanie do starszych kolegów. Czy pokazanie, że (biorąc pod uwagę pierwsze i trzecie równanie):
\(\displaystyle{ \begin{cases}x \equiv 1 \pmod{11} \\ x \equiv 4 \pmod{11}\end{cases}}\)
wystarczy, aby powiedzieć, że poniższy układ kongruencji nie posiada rozwiązania?

[Premislav]

Chyba "powyższy". ^^

Tak, wystarcza. Ładne podejście.

-- 30 lis 2016, o 02:59 --

To podam szkice dwóch rozwiązań, żeby nie spamować.

Jaka jest reszta z dzielenia liczby \(\displaystyle{ 7^{2222}}\) przez \(\displaystyle{ 10}\)?

Indukcyjnie dowodzimy, że \(\displaystyle{ 7^{4k+2}\equiv 9 \pmod{10}}\) dla \(\displaystyle{ k \in \NN}\)
i po sprawie, bo \(\displaystyle{ 2222=4\cdot 555+2}\)
(można też od razu wprost z własności kongruencji: \(\displaystyle{ 7^2\equiv -1\pmod{10}, 7^{4}\equiv 1\pmod{10}}\) itd.)

Podaj dwie ostatnie cyfry liczby \(\displaystyle{ 82^{82}}\).

Wystarczy sprawdzić resztę z dzielenia \(\displaystyle{ 82^{82}}\) przez \(\displaystyle{ 100=4\cdot 25}\).
Skorzystam z twierdzenia Eulera: \(\displaystyle{ \phi(25)=20}\) i \(\displaystyle{ \NWD(25,82)=1}\), więc \(\displaystyle{ 82^{20}\equiv 1\pmod{25}}\) i \(\displaystyle{ 82^{82}=(82^{20})^4 \cdot 82^2}\)
oraz \(\displaystyle{ 82\equiv 7\pmod{25}}\), więc podnosząc stronami do kwadratu, \(\displaystyle{ 82^2equiv 24pmod[25}}\), a stąd ostatecznie \(\displaystyle{ 82^{82}\equiv 24\pmod{25}}\).
Zatem już stąd wynika, że dwie ostatnie cyfry \(\displaystyle{ 82^{82}}\) to \(\displaystyle{ 24, 49, 74}\) lub \(\displaystyle{ 99}\), ale \(\displaystyle{ 82}\) jest parzyste, więc \(\displaystyle{ 82^{82}}\) jest podzielne przez cztery, stąd odpadają wszystkie możliwości oprócz \(\displaystyle{ 24}\) (cecha podzielności przez \(\displaystyle{ 4}\)).