\(\displaystyle{ \begin\\
Prosze \ o \ rozwiazanie \ krok \ po \ kroku \ bo \ jestem \ w \ tym \ ciemna \ a \ chcialabym \ kolejne \ zadania \ robic \ sama \ \ \\
Korzystajac \ z \ kongruencji\ wyznacz\ reszte\ z\ dzielenia \\
1) \ 541^{541} \ przez \ 37\\
\\
Wyznacz \ dwie \ ostatnie \ cyfry \ liczby\\
2) \ 2^{999}\\
Z \ gory \ dziekuje \ za \ pomoc\
\end}\)
Korzystając z kongruencji wyznacz reszte...wyznacz ostatnie
-
Rooibos
- Użytkownik
- Posty: 37
- Rejestracja: 15 lut 2009, o 13:41
- Płeć: Kobieta
- Lokalizacja: I LO im. St. Dubois
- Podziękował: 1 raz
- Pomógł: 4 razy
Korzystając z kongruencji wyznacz reszte...wyznacz ostatnie
\(\displaystyle{ a) 541 \equiv 23 (mod 37)}\)
co czytamy 541 przy dzieleniu przez 37 daje resztę 23, bo 541 = 14*37 + 23.
podnosimy kongruencję do kwadratu:
\(\displaystyle{ 541 ^{2} \equiv 23 ^{2} \equiv 11 (mod 37)}\)
bo 23^2 przy dzieleniu przez 37 daje resztę 11.
znowu podnosimy do kwadratu:
\(\displaystyle{ 541 ^{4} \equiv 11 ^{2} \equiv 10 (mod 37)}\)
bo 11^2 = 121, a 121 daje resztę 10 z dzielenia przez 37. i dalej:
\(\displaystyle{ 541 ^{8} \equiv 100 \equiv 26 (mod 37)}\)
\(\displaystyle{ 541 ^{16} \equiv 26^{2} \equiv 10 (mod 37)}\)
\(\displaystyle{ 541 ^{32}\equiv 100 \equiv 26}\)
Następne kongruencje będą się powtarzały:
\(\displaystyle{ 541 ^{64} \equiv 10 (mod 37); 541^{128} \equiv 26 (mod 37); 541 ^{256} \equiv 10 (mod 37); 541 ^{512} \equiv 26 (mod 37)}\)
\(\displaystyle{ 541 ^{512} * 541 ^{16} * 541 ^{8} * 541 ^{4} * 541 \equiv 26 * 10 * 26 * 10 * 23 \equiv 1554800 (mod 37)}\)
\(\displaystyle{ 541 ^{541} \equiv 1554800 \equiv 23 (mod 37)}\)
2. Żeby wyznaczyć dwie ostatnie cyfry liczby, musimy wiedzieć, jaką da resztę przy dzieleniu przez 100. \(\displaystyle{ 2 \equiv 2 (mod 100)}\)
\(\displaystyle{ 2 ^{5} \equiv 32 (mod 100)}\)
\(\displaystyle{ 2 ^{6} \equiv 64 (mod 100)}\)
\(\displaystyle{ 2 ^{7} \equiv 28 (mod 100)}\) Kolejne kongruencje podnosimy do kwadratu.
\(\displaystyle{ 2 ^{8} \equiv56 (mod 100)}\)
\(\displaystyle{ 2 ^{16} \equiv56 ^{2} \equiv 36 (mod 100)}\)
\(\displaystyle{ 2 ^{32} \equiv 96 (mod 100)}\)
\(\displaystyle{ 2 ^{64} \equiv 16 (mod 100)}\)
\(\displaystyle{ 2 ^{128} \equiv 56 (mod 100)}\)
\(\displaystyle{ 2 ^{256} \equiv 36 (mod 100)}\)
\(\displaystyle{ 2 ^{512} \equiv 96 (mod 100)}\)
\(\displaystyle{ 2 ^{999} = 2 ^{512} * 2 ^{256} * 2 ^{128} * 2 ^{64} * 2 ^{32} * 2 ^{7} \equiv 96*36*56*16*96*28 \equiv 88 (mod 100)}\)
czyli ostatnie dwie cyfry to 88
co czytamy 541 przy dzieleniu przez 37 daje resztę 23, bo 541 = 14*37 + 23.
podnosimy kongruencję do kwadratu:
\(\displaystyle{ 541 ^{2} \equiv 23 ^{2} \equiv 11 (mod 37)}\)
bo 23^2 przy dzieleniu przez 37 daje resztę 11.
znowu podnosimy do kwadratu:
\(\displaystyle{ 541 ^{4} \equiv 11 ^{2} \equiv 10 (mod 37)}\)
bo 11^2 = 121, a 121 daje resztę 10 z dzielenia przez 37. i dalej:
\(\displaystyle{ 541 ^{8} \equiv 100 \equiv 26 (mod 37)}\)
\(\displaystyle{ 541 ^{16} \equiv 26^{2} \equiv 10 (mod 37)}\)
\(\displaystyle{ 541 ^{32}\equiv 100 \equiv 26}\)
Następne kongruencje będą się powtarzały:
\(\displaystyle{ 541 ^{64} \equiv 10 (mod 37); 541^{128} \equiv 26 (mod 37); 541 ^{256} \equiv 10 (mod 37); 541 ^{512} \equiv 26 (mod 37)}\)
\(\displaystyle{ 541 ^{512} * 541 ^{16} * 541 ^{8} * 541 ^{4} * 541 \equiv 26 * 10 * 26 * 10 * 23 \equiv 1554800 (mod 37)}\)
\(\displaystyle{ 541 ^{541} \equiv 1554800 \equiv 23 (mod 37)}\)
2. Żeby wyznaczyć dwie ostatnie cyfry liczby, musimy wiedzieć, jaką da resztę przy dzieleniu przez 100. \(\displaystyle{ 2 \equiv 2 (mod 100)}\)
\(\displaystyle{ 2 ^{5} \equiv 32 (mod 100)}\)
\(\displaystyle{ 2 ^{6} \equiv 64 (mod 100)}\)
\(\displaystyle{ 2 ^{7} \equiv 28 (mod 100)}\) Kolejne kongruencje podnosimy do kwadratu.
\(\displaystyle{ 2 ^{8} \equiv56 (mod 100)}\)
\(\displaystyle{ 2 ^{16} \equiv56 ^{2} \equiv 36 (mod 100)}\)
\(\displaystyle{ 2 ^{32} \equiv 96 (mod 100)}\)
\(\displaystyle{ 2 ^{64} \equiv 16 (mod 100)}\)
\(\displaystyle{ 2 ^{128} \equiv 56 (mod 100)}\)
\(\displaystyle{ 2 ^{256} \equiv 36 (mod 100)}\)
\(\displaystyle{ 2 ^{512} \equiv 96 (mod 100)}\)
\(\displaystyle{ 2 ^{999} = 2 ^{512} * 2 ^{256} * 2 ^{128} * 2 ^{64} * 2 ^{32} * 2 ^{7} \equiv 96*36*56*16*96*28 \equiv 88 (mod 100)}\)
czyli ostatnie dwie cyfry to 88
Ostatnio zmieniony 12 cze 2010, o 22:06 przez Rooibos, łącznie zmieniany 1 raz.
