szukanie zaawansowane
 [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Kobieta Offline
PostNapisane: 11 paź 2015, o 09:14 
Użytkownik
Avatar użytkownika

Posty: 2780
Mam obliczyć resztę z dzielenia przez 13 liczby 2016^{2015}.

Oczywiście w tym celu wykorzystuję kongruencje i działanie \pmod{13}.
Akurat 13 | 2016. Czy to oznacza wtedy, że mogę zapisać: 2016^{2015} \equiv 2016^{0} \equiv 1 i mam już gotowy wynik?
Góra
Kobieta Offline
PostNapisane: 11 paź 2015, o 09:39 
Użytkownik
Avatar użytkownika

Posty: 2505
Ale trzynastka nie dzieli 2016, bo 2016 = 13 \cdot 155 + 1. Rozwiązanie wygląda więc tak:

2016^{2015} \equiv 1^{2015} \equiv 1 \pmod {13}.
Góra
Kobieta Offline
PostNapisane: 11 paź 2015, o 14:14 
Użytkownik
Avatar użytkownika

Posty: 2780
Chodziło mi o to, że trzynastka dzieli 2015. Zrobiłam literówkę. Miałoby być 13 | 2015.
Góra
Mężczyzna Offline
PostNapisane: 11 paź 2015, o 14:22 
Użytkownik

Posty: 1424
Lokalizacja: Warszawa
Wygląda to tak, jakbyś chciała skorzystać z własności: jeśli x\equiv y\pmod{m}, to a^x\equiv a^y\pmod{m}, a taka własność nie jest w ogólności prawdziwa. Sprawdź sobie sama na jakichś małych liczbach.
Góra
Kobieta Offline
PostNapisane: 11 paź 2015, o 14:27 
Użytkownik
Avatar użytkownika

Posty: 2780
No faktycznie nie jest, więc ten sposób odpada..

Ale za to implikacja a \equiv b  \Rightarrow a^k \equiv b^k jest prawdziwa.
Góra
Mężczyzna Offline
PostNapisane: 11 paź 2015, o 14:31 
Użytkownik

Posty: 1424
Lokalizacja: Warszawa
Tak, i z tego skorzystała Medea 2.
Góra
Kobieta Offline
PostNapisane: 11 paź 2015, o 14:31 
Użytkownik
Avatar użytkownika

Posty: 2505
Weź x = 9, y = 18, a = 2 i m = 9. Wtedy \textstyle a^y - a^x = 261632 = 29070 + \frac 29.

Inny kontrprzykład, mniejszy: x = 1, a = 2, m = 3 i y = 4. 8-)
Góra
Kobieta Offline
PostNapisane: 11 paź 2015, o 18:17 
Użytkownik
Avatar użytkownika

Posty: 2780
A z jakiej własności należałoby skorzystać, gdyby zamiast 2016^{2015} było 2017^{2015}?

Wtedy 2017 \equiv 2 \pmod{13}  \Rightarrow 2017^{2015} \equiv 2^{2015}, ale co dalej?
Góra
Mężczyzna Offline
PostNapisane: 11 paź 2015, o 18:22 
Użytkownik
Avatar użytkownika

Posty: 10614
Lokalizacja: Wrocław
Dalej \phi(13)=12 (\phi to funkcja Eulera, możesz o niej poczytać, przyporządkowuje ona liczbie naturalnej \ge 2 liczbę liczb całkowitych dodatnich względnie z nią pierwszych), więc z twierdzenia Eulera 2^{12}\equiv 1\pmod{13}, bo \NWD(2,13)=1.
Góra
Mężczyzna Offline
PostNapisane: 11 paź 2015, o 18:41 
Użytkownik

Posty: 1424
Lokalizacja: Warszawa
Warto zaznaczyć, że w definicji funkcji Eulera chodzi o liczby nie większe niż n, bo inaczej dla każdego n mielibyśmy \varphi(n)=\infty. Poza w tym akurat wypadku wystarczy małe twierdzenie Fermata.
Góra
Mężczyzna Offline
PostNapisane: 11 paź 2015, o 18:41 
Użytkownik
Avatar użytkownika

Posty: 10614
Lokalizacja: Wrocław
Słuszna uwaga.
Góra
Kobieta Offline
PostNapisane: 11 paź 2015, o 18:52 
Użytkownik
Avatar użytkownika

Posty: 2780
No to teraz będzie:
(2^{12})^{167} \cdot 2^{11} \equiv 1 \cdot 2^{11}
Góra
Mężczyzna Offline
PostNapisane: 11 paź 2015, o 18:57 
Użytkownik
Avatar użytkownika

Posty: 10614
Lokalizacja: Wrocław
Zgadza się. A 2^{11}=2048 to taka malutka liczba, że resztę z dzielenia tej liczby przez 13 liczy się w pamięci. A jeśli ktoś nie lubi, to 2^{6}\equiv -1\pmod{13} itd.
Góra
Kobieta Offline
PostNapisane: 11 paź 2015, o 19:09 
Użytkownik
Avatar użytkownika

Posty: 2780
Ok, oczywiście 2^{11} to już "fajna" liczba do rachunków :P Ale spróbuję też w ten drugi zadany przez Ciebie sposób.

2^{11} \equiv 2^{6}  \cdot 2^{5} \equiv -1  \cdot 2^{5} \equiv -32 \equiv 7

Dobrze?
Góra
Mężczyzna Offline
PostNapisane: 11 paź 2015, o 19:11 
Użytkownik
Avatar użytkownika

Posty: 10614
Lokalizacja: Wrocław
Dobrze.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 reszta z dzielenia - zadanie 63  aska0  12
 Reszta z dzielenia - zadanie 70  Tera_SS  2
 Reszta z dzielenia - zadanie 88  Itak  2
 Reszta z dzielenia - zadanie 66  angelst  2
 Reszta z dzielenia - zadanie 26  bujal  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl