szukanie zaawansowane
 [ Posty: 11 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 4 lip 2011, o 19:45 
Użytkownik

Posty: 5
Lokalizacja: Poznań
Witam mam podobny problem co kolega z reszta dzielenia, zadania poprzednie byly o tyle proste ze latwo bylo znalezc potege 2 lub 3. Ja natomiast mam zadanie w stylu
407 ^{136} \equiv x (mod27)
oraz 154  ^{84} przez 15 :|
siedze juz pare godzin niby proste a nie potrafie rozgryzc zasady liczenia.
Góra
Mężczyzna Offline
PostNapisane: 4 lip 2011, o 20:04 
Użytkownik
Avatar użytkownika

Posty: 2859
Lokalizacja: Biała Podlaska
Zauważ, że 407 \equiv 2\pmod{27}  \Rightarrow 407^{136} \equiv 2^{136} \pmod{27} ale z twierdzenia Eulera wynika 2^{18} \equiv 1 \pmod{27}  \Rightarrow 2^{126} \equiv 1\pmod{27}  \Rightarrow 2^{136} \equiv 2^{10} \cdot 2^{126} \equiv 2^{10} \equiv 25\pmod{27}

Podobnie 2 przykład, 154^{84} \equiv 4^{84} \pmod{15} ale 4^2 \equiv 1\pmod{15}  \Rightarrow 4^{84} \equiv 1 \pmod{15}
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 06:55 
Użytkownik

Posty: 5
Lokalizacja: Poznań
jedno male pytanie skad sie wzielo2 ^{18} ?
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 10:13 
Użytkownik
Avatar użytkownika

Posty: 683
Lokalizacja: Gliwice
\varphi(27)=18
a^{\varphi(n)}\equiv 1 \pmod{n} to jest twierdzenie Eulera
gdzie \varphi(n) to funkcja Eulera
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 10:14 
Użytkownik
Avatar użytkownika

Posty: 785
Lokalizacja: Wrocław
A to co kolega wyżej mnie uprzedził :) jest z kolei potrzebne do wspomnianego twierdzenia Eulera.
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 10:22 
Użytkownik

Posty: 5
Lokalizacja: Poznań
\varphi(27)=18\\

\varphi(27) = 27 * 1 - \frac{1}{9} * 1 -  \frac{1}{3}\\

Mnie wychodzi 16 ? :|
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 10:24 
Użytkownik
Avatar użytkownika

Posty: 785
Lokalizacja: Wrocław
Chwilkę ale skąd ty to wziąłeś? ;p

funkcja eulera przyporządkowuje argumentowi liczbę, mniejszych od niego liczb z nim względnie pierwszych :)

Czyli w tym wypadku: 2,4,5,7,8,10 ... a takich liczb jest 18 :)
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 10:29 
Użytkownik

Posty: 5
Lokalizacja: Poznań
No mam taki sposob liczenia w notatkach, chyba dzis sie wybiore poprostu na uczelnie i spytam :)
Np. w notatkach dla \varphi(65) = 65 * 1 - \frac{1}{5} * 1 -  \frac{1}{13}\\ co jest równe 48. A wiec założylem ze 5 * 13 = 65 i stad sie to bierze:) w poprzednim zadaniu mielismy 27 wiec założylem ze 3 * 9 = 27 :)
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 10:39 
Użytkownik
Avatar użytkownika

Posty: 785
Lokalizacja: Wrocław
ah wiem skąd wziąłeś ten wzór.

http://pl.wikipedia.org/wiki/Funkcja_%CF%86 <- z tego prawda?

Ale tam bierze się liczby p_{i} które są pierwszymi czynnikami liczby n bez powtórzeń. Czyli p_{i}  \in {3}

Co daje nam \varphi(27) = 27  \cdot (1 -  \frac{1}{3}) = 18
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 10:47 
Użytkownik

Posty: 5
Lokalizacja: Poznań
czyli i tak nalezaloby wypisac wszystkie liczby pierwsze i usunac powtarzajace sie wowczas zostalyby 3 liczby ... coz wydawalo mi sie iz jest na zasadzie ktora opisalem edytujac swoj poprzedni post.
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2011, o 11:08 
Użytkownik
Avatar użytkownika

Posty: 785
Lokalizacja: Wrocław
Dla 65 jest tak ponieważ czynniki pierwsze liczby 65 to: 5 i 13
i tu analogicznie jedynym pierwszym czynnikiem 27 jest 3 bo 3*3*3 = 27
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 11 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Reszty z dzielenia dużych liczb
Witajcie. Chciałbym sobie przypomnieć jak oblicza się reszty z dzielenia dużych liczb przy pomocy małego twierdzenia Fermata, a może innych narzędzi? Na przykład, jak policzyć 7^{13131313} w \mathbb{Z}_{13}...
 Boolean  3
 Reszta z dzielenia - zadanie 122
Witam. Mam wyliczyć resztę z dzielenia liczby 12^{33} przez 17. Wytłumaczy ktoś tak łopatologicznie? Mam teraz tak a=12 \quad p=17 więc NWD \left&#4...
 Ramzesso  4
 Reszta z dzielenia - zadanie 112
Mamy do policzenia 23^{5} \pmod{63} Znalazlem taki sposob, tylko nie wiem dlaczego tak to dziala. 23^{2} \pmod{63} \equiv 529 \pmod{63} \equiv 25\\ 23^{4} \pmod{63} \equiv 625 \pmod{63} \equiv -5\\ 23^{5} ...
 pajkul  3
 Algorytm dzielenia z reszta w Z
Założenia: * a,b Z,b 0 * b nie dzieli a Teza: * is...
 GothicIIIbez  1
 Wlasnosci mnozenia/dzielenia
Nie wiem czy moj tytul jest dobry - pewnie nie. Ale nie wiem jak zatytulowac to zadanie: Dla kazdego m \in N_{29} \setminus \left\{ 0\right\} istnieje jeden x_{m} \in N_{29} \setminus \left\{ 0\right\} \...
 dzejkej  2
 reszta z dzielenia - zadanie 52
wydaje mi sie ze reszta z dzielenia bedzie \frac{9}{37}...
 wiosna  7
 Znajdz resztę z dzielenia
Pewna liczba daje resztę 1 z dzielenia przez 3 oraz resztę 6 z dzielenia przez 7. Znajdz resztę jaka daje ta liczba z dzielenia przez 21. Tak na palcach to 13, ale jak to pokazać?...
 Citizen  5
 modulo z dzielenia dwóch liczb
Witam, mam problem z obliczeniem modulo z dzielenia liczby: 4847^{1525} przez liczbę 407 Nie mam pojęcia jak to policzyć. Mam notatki według których ktoś najpierw dzieli liczbę 1525 na 2, następnie 762 itd do samego 0, ...
 humphreyhojo  3
 reszta z dzielenia - zadanie 107
Oblicz, 18^{4567} (mod 13). Czy ktoś byłby uprzejmy pokazać mi jak się takie coś rozwiązuje? Dziękuję...
 omgcozadebil  2
 Reszta z dzielenia - zadanie 94
Wyznacz resztęz dzielenia liczby 2^{9768} przez 3 oraz 3^{73} przez 4....
 Kanodelo  8
 Weryjikacja zadania z resztą z dzielenia
Polecenie brzmi: wyznacz resztę z dzielenia: 3^{1000000} \ mod \ 91 a więc wiemy, że liczby 3 i 91 są względnie pierwsze, możemy przy tym zastosować Twierdzenie Eulera i dostajemy, że: 3^{\varphi{91}}\equiv...
 szatek  2
 dzielenie z resztą - zadanie 12
Witam, proszę o pomoc w rozwiązaniu tego zadania. Gdy oddział wojska ustawimy w szyk siódemkowy, to ostatni szereg liczy sześciu żołnierzy. W przypadku ustawienia w szyk trzynastkowy i 17-stkowy ostatni szereg liczy odpowiednio 8 i 15 żołnierzy. Ilu...
 gocha92  1
 Wyznaczyć resztę z dzielenia - zadanie 3
Pomoże ktoś rozwiązać bo sama nie potrafię? :/ Znaleźć resztę z dzielenia: a) 16^{231}+550 przez 17 b) 3 \cdot 18^{18}-500 \cdot 5^{120} przez 8 c) 423^{200} \cdot 562^{100}[...
 kordi1221  2
 Jaka reszta?
Pewna liczba trzycyfrowa przy dzieleniu przez 15 daje reszte 10 ,jaka reszte daje przy dzieleniu przez 3?...
 damiana01  4
 Reszta z dzielenia - zadanie 125
Oblicz resztę z dzielenie 5555^{7777}&#40;mod 191&#41;. Mam już wyznaczoną resztę z dzielenia: 5555^{190}\equiv 1&#40;mod 191&#41; czyli 5555^{190*40}\equiv 1^{40}&#40;mod 191&#4...
 nitka  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com