Reszta z dzielenia liczb / male tw Fermata i tw Eulera
-
- Użytkownik
- Posty: 92
- Rejestracja: 12 gru 2007, o 14:29
- Płeć: Mężczyzna
- Lokalizacja: Szczecin
- Podziękował: 65 razy
- Pomógł: 1 raz
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
mam taki problem, nie wiem jak policzyc takie cos :
Oblicz reszte z dzielenia liczby a przez b:
a) a = \(\displaystyle{ 1946^{1972}}\) b = \(\displaystyle{ 26}\)
b) a = \(\displaystyle{ 1946^{1972} + 1972^{1946}}\), b = \(\displaystyle{ 26}\)
c) a = \(\displaystyle{ 5555^{190}}\) b =\(\displaystyle{ 191}\)
Bede bardzo wdzieczny za pomoc, dziekuje i pozdrawiam[/latex]
EDIT : jeszcze raz prosze o pomoc, to sa wazne zadania a nikt ze znajomych nie potrafi mi pomoc :/
Oblicz reszte z dzielenia liczby a przez b:
a) a = \(\displaystyle{ 1946^{1972}}\) b = \(\displaystyle{ 26}\)
b) a = \(\displaystyle{ 1946^{1972} + 1972^{1946}}\), b = \(\displaystyle{ 26}\)
c) a = \(\displaystyle{ 5555^{190}}\) b =\(\displaystyle{ 191}\)
Bede bardzo wdzieczny za pomoc, dziekuje i pozdrawiam[/latex]
EDIT : jeszcze raz prosze o pomoc, to sa wazne zadania a nikt ze znajomych nie potrafi mi pomoc :/
Ostatnio zmieniony 20 kwie 2008, o 10:57 przez zxc18, łącznie zmieniany 1 raz.
- Majorkan
- Użytkownik
- Posty: 128
- Rejestracja: 14 paź 2007, o 18:45
- Płeć: Mężczyzna
- Lokalizacja: Kraków/Jasło
- Podziękował: 13 razy
- Pomógł: 33 razy
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
Rozwiązanie punktu c) to bezpośredni wniosek z tw. Eulera.
Ponieważ 191 jest liczbą pierwszą i 191 nie dzieli 5555, to 191 i 5555 są względnie pierwsze.
Zatem \(\displaystyle{ 5555^{\varphi(191)} \equiv 1 (mod 191)}\)
gdzie \(\displaystyle{ \varphi}\) oznacza funkcję Eulera.
Ponieważ 191 jest pierwsza, to \(\displaystyle{ \varphi(191)=190}\)
Czyli szukana reszta to 1.
Niestety nie można powtórzyć tego rozumowania dla a) i b) gdyż 26 i 1946 nie są względnie pierwsze, tak więc nie wiem jak to zrobić.
Ponieważ 191 jest liczbą pierwszą i 191 nie dzieli 5555, to 191 i 5555 są względnie pierwsze.
Zatem \(\displaystyle{ 5555^{\varphi(191)} \equiv 1 (mod 191)}\)
gdzie \(\displaystyle{ \varphi}\) oznacza funkcję Eulera.
Ponieważ 191 jest pierwsza, to \(\displaystyle{ \varphi(191)=190}\)
Czyli szukana reszta to 1.
Niestety nie można powtórzyć tego rozumowania dla a) i b) gdyż 26 i 1946 nie są względnie pierwsze, tak więc nie wiem jak to zrobić.
-
- Użytkownik
- Posty: 92
- Rejestracja: 12 gru 2007, o 14:29
- Płeć: Mężczyzna
- Lokalizacja: Szczecin
- Podziękował: 65 razy
- Pomógł: 1 raz
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
Ty sie Undre nie śmiej , ale pomóż.... no po prostu mała literówka Ale nie zaprzeczysz, iż by się przydało twierdzenie Formata
-
- Użytkownik
- Posty: 95
- Rejestracja: 10 lis 2007, o 09:27
- Płeć: Mężczyzna
- Lokalizacja: Wawa
- Podziękował: 28 razy
- Pomógł: 5 razy
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
Dobra Maciek. Po kilku godzinach prób chyba doszedłem jak zrobić tego typu zadania. Bombnijmy podpunkt
a):
\(\displaystyle{ 1946^{1972} : 26}\)
Wiemy, że \(\displaystyle{ 26=2*13}\) oraz \(\displaystyle{ 1946 = 0mod2}\), więc niczego nie zmieni w naszym rozumowaniu.
Dalej przyjmujemy, że \(\displaystyle{ b=13}\)
Rozpisujemy sobie potęgę do obliczeń: \(\displaystyle{ 1972= 13*151+9}\)
Tutaj stosujemy małe twierdzenie Fermata:
\(\displaystyle{ 1946^{13}=1mod13}\)
\(\displaystyle{ 1946^{13^{151}}=1mod13}\)
\(\displaystyle{ 1946=9mod13}\)
\(\displaystyle{ 1946^2=3mod13}\)
\(\displaystyle{ 1946^4=9mod13}\)
\(\displaystyle{ 1946^8=3mod13}\)
\(\displaystyle{ 1946^9=1mod13}\)
Mnożąc obustronnie stronami:
\(\displaystyle{ 1946^{1972}=(1*1)mod13=1mod26}\)
Mam nadzieję, że reszta z dzielenia faktycznie wynosi 1...
a):
\(\displaystyle{ 1946^{1972} : 26}\)
Wiemy, że \(\displaystyle{ 26=2*13}\) oraz \(\displaystyle{ 1946 = 0mod2}\), więc niczego nie zmieni w naszym rozumowaniu.
Dalej przyjmujemy, że \(\displaystyle{ b=13}\)
Rozpisujemy sobie potęgę do obliczeń: \(\displaystyle{ 1972= 13*151+9}\)
Tutaj stosujemy małe twierdzenie Fermata:
\(\displaystyle{ 1946^{13}=1mod13}\)
\(\displaystyle{ 1946^{13^{151}}=1mod13}\)
\(\displaystyle{ 1946=9mod13}\)
\(\displaystyle{ 1946^2=3mod13}\)
\(\displaystyle{ 1946^4=9mod13}\)
\(\displaystyle{ 1946^8=3mod13}\)
\(\displaystyle{ 1946^9=1mod13}\)
Mnożąc obustronnie stronami:
\(\displaystyle{ 1946^{1972}=(1*1)mod13=1mod26}\)
Mam nadzieję, że reszta z dzielenia faktycznie wynosi 1...
-
- Użytkownik
- Posty: 3921
- Rejestracja: 10 gru 2007, o 20:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 36 razy
- Pomógł: 1194 razy
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
Niestety muszę Cię zmartwić; nie słyszałem jeszcze, żeby przy dzieleniu liczby parzystej przez liczbę parzystą można było dostać resztę nieparzystą.
-
- Użytkownik
- Posty: 95
- Rejestracja: 10 lis 2007, o 09:27
- Płeć: Mężczyzna
- Lokalizacja: Wawa
- Podziękował: 28 razy
- Pomógł: 5 razy
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
No to jeszcze inaczej:
\(\displaystyle{ 1946=22mod26}\)
\(\displaystyle{ 1946^2=16mod26}\)
\(\displaystyle{ 1946^3=14mod26}\)
\(\displaystyle{ 1946^4=22mod26}\)
\(\displaystyle{ 1946^5=16mod26}\)
\(\displaystyle{ 1946^6 = 14mod26}\)
.
.
.
itd.
Otrzymujemy funkcję okresową o T=3;
\(\displaystyle{ 1972 : 3 = 657\frac{1}{3}}\)
Ta 1 z \(\displaystyle{ \frac{1}{3}}\) to 22mod26, więc to 22 jest resztą. Zaraz sprawdzę dla drugiego przykładu...
[ Dodano: 20 Kwietnia 2008, 15:12 ]
Działa, więc teraz bombardujemy podpunkt b):
Pierwszą liczbę mamy juz obliczoną i wiemy, że \(\displaystyle{ 1946^{1972}=22mod26}\)
Teraz liczymy resztę dla drugiej cyfry z zadania:
\(\displaystyle{ 1972=22mod26}\)
\(\displaystyle{ 1972^2=16mod26}\)
\(\displaystyle{ 1972^3=14mod26}\)
\(\displaystyle{ 1972^4=22mod26}\)
\(\displaystyle{ 1972^5=16mod26}\)
.
.
.
itd.
\(\displaystyle{ 1946 : 3 =648 \frac{2}{3}}\)
Z tego faktu wnioskujemy, że \(\displaystyle{ 1972^{1946}=16mod26}\)
Na koniec dodajemy kongruencje stronami i:
\(\displaystyle{ 1972^{1946}+1946^{1972}=(22+16)mod26=12mod26}\)
Reszta z dzielenia wynosi 12 uff...
\(\displaystyle{ 1946=22mod26}\)
\(\displaystyle{ 1946^2=16mod26}\)
\(\displaystyle{ 1946^3=14mod26}\)
\(\displaystyle{ 1946^4=22mod26}\)
\(\displaystyle{ 1946^5=16mod26}\)
\(\displaystyle{ 1946^6 = 14mod26}\)
.
.
.
itd.
Otrzymujemy funkcję okresową o T=3;
\(\displaystyle{ 1972 : 3 = 657\frac{1}{3}}\)
Ta 1 z \(\displaystyle{ \frac{1}{3}}\) to 22mod26, więc to 22 jest resztą. Zaraz sprawdzę dla drugiego przykładu...
[ Dodano: 20 Kwietnia 2008, 15:12 ]
Działa, więc teraz bombardujemy podpunkt b):
Pierwszą liczbę mamy juz obliczoną i wiemy, że \(\displaystyle{ 1946^{1972}=22mod26}\)
Teraz liczymy resztę dla drugiej cyfry z zadania:
\(\displaystyle{ 1972=22mod26}\)
\(\displaystyle{ 1972^2=16mod26}\)
\(\displaystyle{ 1972^3=14mod26}\)
\(\displaystyle{ 1972^4=22mod26}\)
\(\displaystyle{ 1972^5=16mod26}\)
.
.
.
itd.
\(\displaystyle{ 1946 : 3 =648 \frac{2}{3}}\)
Z tego faktu wnioskujemy, że \(\displaystyle{ 1972^{1946}=16mod26}\)
Na koniec dodajemy kongruencje stronami i:
\(\displaystyle{ 1972^{1946}+1946^{1972}=(22+16)mod26=12mod26}\)
Reszta z dzielenia wynosi 12 uff...
-
- Użytkownik
- Posty: 4
- Rejestracja: 27 maja 2010, o 20:48
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
Sory za nekrofilię, ale co oznacza ten zapis (i kolejne)?unikat900 pisze:No to jeszcze inaczej:
\(\displaystyle{ 1946=22mod26}\)
przecież
\(\displaystyle{ 22 mod 26 = 22 \neq 1946}\)
Może mi to ktoś wyjaśnić?
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
Tutaj chodzi o przystawanie, powinno być:
\(\displaystyle{ 1946 \equiv 22 \left( mod 26 \right)}\)
Czyli innymi słowy:
\(\displaystyle{ 26 | \left(1946-22\right)}\)
Przez znak równości wyszedł taki skrót myślowy.
\(\displaystyle{ 1946 \equiv 22 \left( mod 26 \right)}\)
Czyli innymi słowy:
\(\displaystyle{ 26 | \left(1946-22\right)}\)
Przez znak równości wyszedł taki skrót myślowy.
-
- Użytkownik
- Posty: 120
- Rejestracja: 2 mar 2010, o 19:56
- Płeć: Mężczyzna
- Lokalizacja: Kielce
- Podziękował: 13 razy
- Pomógł: 2 razy
Reszta z dzielenia liczb / male tw Fermata i tw Eulera
A te poszczególne \(\displaystyle{ 1946^2, 1946^3}\)itd. to policzyłeś w pamięci rozumiem... Czyli żeby obliczyć "ręcznie" zadania a nie kalkulatorem i tak użyłeś kalkulatora... troszku się z celem mija
WIADOMOŚĆ DO STUDENTÓW PWR:
NIE SKUMACIE TEGO CO POWYŻEJ! ODSYŁAM WAS TAM:
SKORO JA TO ROZKMINIŁEM TO WY TEŻ MOŻECIE!!! POWODZENIA
WIADOMOŚĆ DO STUDENTÓW PWR:
NIE SKUMACIE TEGO CO POWYŻEJ! ODSYŁAM WAS TAM:
Kod: Zaznacz cały
http://www.cauchy.pl/kolko/gimnazjum/34/ro/
SKORO JA TO ROZKMINIŁEM TO WY TEŻ MOŻECIE!!! POWODZENIA