szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 14 gru 2010, o 22:20 
Użytkownik

Posty: 85
Lokalizacja: podkarpackie
Zetknęłam się z tematem kongruencji pierwszy raz i proszę o pomoc w zrozumieniu problemu.
Mam takie zadanie jak w temacie - wyznaczyć resztę z dzielenia liczby 2008^{2009} przez 7.
(lub inaczej: "do czego przystaje liczba 2008^{2009} modulo 7?").

Kolejność postępowania:
1. Wyznaczam resztę z dzielenia liczby 2008 przez 7 czyli otrzymam resztę 6.
2. Sprawdzam jaką resztę otrzymam z dzielenia liczby 6^{2}przez 7 - otrzymam 1.
3. Podnoszę liczbę 6^{2} do takiej potęgi aby otrzymać 6^{2009}. Niestety mogę podnieść jedynie do potęgi 1004 a wtedy dostanę 6^{2008}.


Zatem 6^{2008} przystaje do 1^{2008} (modulo 7) .

No i co dalej? Jak dojść do 2009?
W odpowiedzi mam 6^{2009} przystaje do 6 (modulo 7). Nie wiem skąd się to "sześć" wzięło. Wiem, że to jest reszta z dzielenia 6^{2009} przez 7 ale skąd to wiemy?

Będę wdzięczna za pomoc z dokładnym wyjaśnieniem. Chyba nie bardzo zrozumiałam te kongruencje.:(
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2010, o 23:44 
Użytkownik

Posty: 231
Lokalizacja: Zbąszynek
6 \equiv -1 (mod 7)
Góra
Kobieta Offline
PostNapisane: 14 gru 2010, o 23:56 
Użytkownik

Posty: 85
Lokalizacja: podkarpackie
Prosiłabym o jakiś komentarz, bo same cyfry nic mi nie mówią.
Góra
Mężczyzna Offline
PostNapisane: 15 gru 2010, o 00:24 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Kończąc Twój sposób myślenia - mnożymy stronami przez 6 kongruencję:
6^{2008} \equiv 1 \mod 7
i dostajemy:
6^{2009} \equiv 6 \mod 7

Dużo prościej natomiast jest zauważyć, że:
2008 \equiv -1 \mod 7
podnieść stronami do potęgi 2009:
2008^{2009} \equiv -1 \mod 7
i z uwagi na -1 \equiv 6 \mod 7 zapisać:
2008^{2009} \equiv -1 \equiv 6 \mod 7

Q.
Góra
Kobieta Offline
PostNapisane: 15 gru 2010, o 11:54 
Użytkownik

Posty: 85
Lokalizacja: podkarpackie
Tak właśnie myślałam, ale nie byłam pewna. Teraz już rozumiem. :)
Dziękuję bardzo.
Góra
Kobieta Offline
PostNapisane: 22 gru 2010, o 19:43 
Użytkownik

Posty: 85
Lokalizacja: podkarpackie
Mam jeszcze wyznaczyć resztę z dzielenia przez 10 liczby 2^{2034}, wykorzystując kongruencje.

Po ciężkich trudach doszłam do tego, ale może jest jakaś szybka metoda, a nie takie długie rozpisywanie?

rozpisałam potęge: 2034 = 2*1017
2^{2} \equiv 4 (mod 10)

(2^{2})^{1017} \equiv 4^{1017}(mod 10)
czyli 2^{2034} \equiv 4^{1017}

i teraz znowu zajmuje sie zgadywaniem do czego przystaje 4^{1017} (mod 10)
1017 = 9*113
zatem:
4^{1017} = (4^{9})^{113}
4^{3} \equiv 4(mod 10)
4^{9} \equiv 4^{3}(mod 10) \equiv 4 (mod 10)
podnosimy wszystko do potęgi 113:
(4^{9})^{113} \equiv 4^{113} (mod 10)
no i znowu nie wiadomo do czego przystaje 4^{113}
(...)

i tak rozpisywałam po kolei bardzo długo, aż w końcu doszłam do tego że 2^{2034} \equiv 4 (mod 10)
ale musi być jakiś inny sposób, prawda?

Uczę się sama kongruencji i może po prostu nie znam jakiegoś wzoru, sposobu, zasady itp.
Proszę o pomoc!
Góra
Mężczyzna Offline
PostNapisane: 22 gru 2010, o 19:48 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Zauważ, że:
2^5 \equiv 2 \mod 10
skąd łatwo indukcyjnie dowieść, że:
2^{4k+1} \equiv 2 \mod 10
więc w szczególności:
2^{2033} \equiv 2 \mod 10
i po pomnożeniu przez dwa:
2^{2034} \equiv 4 \mod 10

Q.
Góra
Kobieta Offline
PostNapisane: 22 gru 2010, o 19:56 
Użytkownik

Posty: 85
Lokalizacja: podkarpackie
Poczekaj, czyli w myśl Twojej podpowiedzi, dla innych liczb, no np. niech wymyślę:
3^{3035} (mod 10)
to by było tak?:

3^4 \equiv 1 (mod 10)
a zatem:
3^{3k+1} \equiv 1 (mod 10)
czyli wykorzystam to do rozkładu mojej potęgi:
3035 = 3*1011+1 +1
zatem:
3^{3034} \equiv 1 (mod 10)
mnożę razy 3^{1}
i mam:
3^{3035} \equiv 3

Czy dobrze zrozumiałam?
Góra
Mężczyzna Offline
PostNapisane: 26 gru 2010, o 15:15 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Fatina napisał(a):
3^4 \equiv 1 (mod 10)
a zatem:
3^{3k+1} \equiv 1 (mod 10)
Nie, z pierwszego przystawania wynika:
3^{4k} \equiv 1 \mod 10

Q.
Góra
Kobieta Offline
PostNapisane: 26 gru 2010, o 16:36 
Użytkownik

Posty: 85
Lokalizacja: podkarpackie
Qń napisał(a):
Zauważ, że:
2^5 \equiv 2 \mod 10
skąd łatwo indukcyjnie dowieść, że:
2^{4k+1} \equiv 2 \mod 10
Q.


Chyba już rozumiem jaki popełniłam błąd:

Tzn. dowodzi się w ten sposób, że dla k=1 i dla k=2 mam dostać to samo przystawanie modulo 10?
dla k=1 mam:
2^{5} \equiv 2 \mod 10
dla k=2:
2^{9} \equiv 2 \mod 10

W moim przypadku to faktycznie nie zadziała, bo 3^{3k+1}
dla k=1:
3^{4}\equiv 1 (mod 10)
ale już dla k=2 :
3^{7}\equiv 7 (mod10)

Jak w takim razie SZYBKO dobrać sobie taką rozpiskę jak Ty: że 2^{5} \equiv 2 (mod10) 2^{4k+1}\equiv 2(mod 10) która będzie pomocna w rozkładzie wysokiej potęgi?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 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
 Reszta z dzielenia liczby...  ptasior  8
 reszta z dzielenia- dowód (jaki?)  youzwiak  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl