szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 9 kwi 2010, o 22:51 
Użytkownik

Posty: 2
Lokalizacja: Irlandia
\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
Góra
Kobieta Offline
PostNapisane: 12 cze 2010, o 20:14 
Użytkownik
Avatar użytkownika

Posty: 37
Lokalizacja: I LO im. St. Dubois
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:
541 ^{2}  \equiv 23 ^{2}  \equiv 11 (mod 37)
bo 23^2 przy dzieleniu przez 37 daje resztę 11.
znowu podnosimy do kwadratu:
541 ^{4}  \equiv  11 ^{2} \equiv 10 (mod 37)
bo 11^2 = 121, a 121 daje resztę 10 z dzielenia przez 37. i dalej:
541 ^{8} \equiv 100 \equiv 26 (mod 37)
541 ^{16}  \equiv 26^{2}  \equiv 10 (mod 37)
541 ^{32}\equiv 100 \equiv 26
Następne kongruencje będą się powtarzały:
541 ^{64} \equiv 10 (mod 37);  541^{128} \equiv 26 (mod 37); 541 ^{256} \equiv 10 (mod 37); 541 ^{512} \equiv 26 (mod 37)
541 ^{512} * 541 ^{16} * 541 ^{8} * 541 ^{4} * 541 \equiv 26 * 10 * 26 * 10 * 23  \equiv 1554800 (mod 37)

541 ^{541}  \equiv 1554800  \equiv 23 (mod 37)


2. Żeby wyznaczyć dwie ostatnie cyfry liczby, musimy wiedzieć, jaką da resztę przy dzieleniu przez 100. 2  \equiv 2 (mod 100)
2 ^{5} \equiv 32 (mod 100)
2 ^{6} \equiv 64 (mod 100)
2 ^{7} \equiv  28 (mod 100) Kolejne kongruencje podnosimy do kwadratu.
2 ^{8} \equiv56 (mod 100)
2 ^{16} \equiv56 ^{2}  \equiv  36 (mod 100)
2 ^{32}  \equiv 96 (mod 100)
2 ^{64} \equiv 16 (mod 100)
2 ^{128}  \equiv 56 (mod 100)
2 ^{256} \equiv  36 (mod 100)
2 ^{512}  \equiv 96 (mod 100)
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
Góra
Mężczyzna Offline
PostNapisane: 12 cze 2010, o 20:50 
Użytkownik

Posty: 255
\equiv \equiv ;)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wyznacz liczby 5-cio cyfrowe podzielne przez 36  tuti  2
 Które liczby przy dzieleniu przez 3 dają resztę 2.  apacz  1
 Wyznacz ostatnia cyfre danej liczby.  tomik  2
 Udowodnij korzystając z kongruencji  Lotos  1
 Wyznacz - zadanie 2  bart-17  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl