[ 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: 2852
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 
 Definicja dzielenia.
Czy istnieje jakaś formalna definicja dzielenia czy jest to działanie intuicyjne?...
 Nasio  4
 Dzielenie i reszta...
Liczby całkowite a,b,c przy dzieleniu przez 7 dają resztę odpowiednio 1, 2, 3.Oblicz resztę z dzielenia liczby a^2 +b^2+c^2 przez 7....
 Adamcio121  2
 Reszty z dzielenia
Dane są liczby całkowite a, b &#949; { 0,1,2,..., 100}. Wiadomo, że reszty z dzielenia liczb a i b przez m są równe, oraz że reszty z dzielenia liczb a i b przez n są równe. Czy stąd wynika, że a = b, jeżeli a) m = 16, n = 20; b) m = 13, n = 17; c) m...
 Marta24  0
 reszta z dzielenia - dowód - zadanie 20
wykaż, że kwadrat liczby całkowitej dającej z dzielenia przez 3 resztę 2 przy dzieleniu przez 3 daje resztę 1. Jestem w nowym liceum i na wejście dostaliśmy takie zadanie. nie proszę o rozwiązanie ( choć oczywiście nie pogniewałbym się) ale zastanaw...
 parkur22  3
 Reszty z dzielenia liczb - zadanie 2
Znajdź reszty z dzielenia liczb 8^{1786} i 7^{1786} przez 21 Nie wiem jak się za to zabrać ;( Proszę o pomoc...
 blackbird936  20
 oblicz reszte z dzielenia przez 4...
Weźmy sobie jedną liczbę tej postaci np. dla n=3 tą liczbą jest 11, teraz sprawdźmy jaką daje resztę z dzielenie przez 4 (musimy zapisać ją jako sumę liczby będącej wielokrotnością 4 i liczby będącej resztą) 11=8+3=4\cdot 2+3[/tex:y6sdy...
 PiroBoss  3
 Dzielenie z resztą - zadanie 13
Potrzebuję wyznaczyć x z równania: 16575838=x^{11539223} \mod 20288243...
 Johny94  2
 Reszta z dzielenia - zadanie 113
Potrzebuję pomocy w przykładzie: 2003^{2005}\pmod{100} a=2003, p=100, zauważam, że NWD&#40;a,p&#41;=1, więc mogę skorzystać z: a^{p-1}=1\pmod{p}[/te...
 freevolity  3
 Reszta z dzielenia przez 90, 15.
Mam problem z pewnym zadaniem. Pewnie dla was to nie żaden problem, ale cóż. Kto pyta nie błądzi. Oto ono: Pewną liczbę naturalną c podzielono przez 90 i otrzym...
 alicce  6
 Reszta z dzielenia - zadanie 109
Czy obliczając resztę z dzielenia liczby 359 ^{359} przez 21 mogę zastosować małe twierdzenie Fermata?...
 XMukiX  1
 reszta z dzielenia przez liczbę pierwszą
Pilnie potrzebuję uzasadnić, że dla każdej liczby pierwszej p zachodzi &#40;p-1&#41;! = p \cdot k + p-1 co jest równoznaczne temu, że reszta z dzielenia &#40;p-1&#41;![/tex:133sc...
 habbababba  2
 Reszta z dzielenia - zadanie 124
Witam, może ktoś krok po kroku wytłumaczyć? 7^{2012} = \pmod{26}...
 gunit  1
 Zadanko - reszta z dzielenia wielomianu
Witam, Proszę o pomoc przy rozwiązaniu zadania: Znajdź resztę z dzielnia wielomianu x^{2006} - x^{2005} + 2 przez x^{3} - x. Uzasadnij. Z góry dzieki !...
 Mateusz Kempa  5
 Reszta z dzielenia - zadanie 114
Jeśli mam otrzymać resztę z dzielenia a^x przez p a NWD&#40;a,p&#41;=1, to nie ma problemu, bo przyjmuję a^{p-1}\equiv1\pmod{p} i dale...
 freevolity  8
 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 = 1946^{1972} b = 26 b) a = 1946^{1972} + 1972^{1946}...
 zxc18  10
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com