Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
kaszlok
Rozkręcam się
Posty: 57 Rejestracja: 04 mar 2013, 11:53
Podziękowania: 34 razy
Post
autor: kaszlok » 31 maja 2013, 11:08
Witam, gdy trzeba policzyc dwie ostatnie cyfry liczby i liczby sa wzglednie pierwsze to wiem jak policzyc
np. z 3^1000 nie mam problemu, ale nie wiem co począć gdy jest np 2^1000 i gdy liczby w takim wypadku 2,100 nie są wzglednie peirwsze. Co trzeba wtedy zrobic ?
kacper218
Expert
Posty: 4077 Rejestracja: 02 paź 2009, 14:33
Lokalizacja: Radzymin
Podziękowania: 5 razy
Otrzymane podziękowania: 1382 razy
Płeć:
Post
autor: kacper218 » 31 maja 2013, 11:13
Badasz resztę z dzielenia tej liczby przez 100.
Pomogłem? Daj plusika
Masz pytania? Napisz priv
Przepisywanie prac do
\(\LaTeX- a\)
Korepetycje Radzymin i okolice.
kaszlok
Rozkręcam się
Posty: 57 Rejestracja: 04 mar 2013, 11:53
Podziękowania: 34 razy
Post
autor: kaszlok » 31 maja 2013, 11:24
W jaki sposób ? Miałem napisane, że 100 = 2^2 * 5^2
a potem gcd(4,25) = 1 i gcd (2,25)=1 nie wiem tylko po co i z czego to wynika
kacper218
Expert
Posty: 4077 Rejestracja: 02 paź 2009, 14:33
Lokalizacja: Radzymin
Podziękowania: 5 razy
Otrzymane podziękowania: 1382 razy
Płeć:
Post
autor: kacper218 » 31 maja 2013, 11:40
Ty mówisz zapewne o algorytmie Euklidesa
Ja mówię o kongruencjach.
Pomogłem? Daj plusika
Masz pytania? Napisz priv
Przepisywanie prac do
\(\LaTeX- a\)
Korepetycje Radzymin i okolice.
kaszlok
Rozkręcam się
Posty: 57 Rejestracja: 04 mar 2013, 11:53
Podziękowania: 34 razy
Post
autor: kaszlok » 31 maja 2013, 11:42
My liczyliśmy na podst. gcd czyli Euklides i tw. Eulera.
Moglbys pokazac na tym przykladzie jak to policzyć
?
Dla 3^1000 to było tak:
\(3^{1000} = ? (mod 100)\)
\(gcd(3,100)=1\)
\(\varphi (100) = 40\)
tw. eulera:
\(3^{40} = 1 (mod 100)\)
\(3^{1000} = 1 (mod 100)\)
czyli ostatnie dwie to "
\(01\) ".
Ostatnio zmieniony 31 maja 2013, 11:47 przez
kaszlok , łącznie zmieniany 3 razy.
patryk00714
Mistrz
Posty: 8799 Rejestracja: 13 mar 2011, 12:28
Lokalizacja: Śmigiel
Podziękowania: 92 razy
Otrzymane podziękowania: 4449 razy
Płeć:
Post
autor: patryk00714 » 31 maja 2013, 11:45
Twierdzenie Eulera jest najlepsze do tego
Otrzymałeś odpowiedź do umieszczonego zadania? Podziękuj autorowi za rozwiązanie!!
\(\exp (i \pi) +1=0\)
kaszlok
Rozkręcam się
Posty: 57 Rejestracja: 04 mar 2013, 11:53
Podziękowania: 34 razy
Post
autor: kaszlok » 31 maja 2013, 11:52
Ale jak to zastosować do 2^1000 to nie mam pojęcia..
kaszlok
Rozkręcam się
Posty: 57 Rejestracja: 04 mar 2013, 11:53
Podziękowania: 34 razy
Post
autor: kaszlok » 31 maja 2013, 12:55
Zrobiłem to kongruencjami i na końcu dostałem x = 100u+ 76 czyli dwie ostatnie cyfry to 7 i 6 ?
kacper218
Expert
Posty: 4077 Rejestracja: 02 paź 2009, 14:33
Lokalizacja: Radzymin
Podziękowania: 5 razy
Otrzymane podziękowania: 1382 razy
Płeć:
Post
autor: kacper218 » 31 maja 2013, 13:42
Tak. To dobrze nie muszę pisać rozwiązania
Pomogłem? Daj plusika
Masz pytania? Napisz priv
Przepisywanie prac do
\(\LaTeX- a\)
Korepetycje Radzymin i okolice.
kacper218
Expert
Posty: 4077 Rejestracja: 02 paź 2009, 14:33
Lokalizacja: Radzymin
Podziękowania: 5 razy
Otrzymane podziękowania: 1382 razy
Płeć:
Post
autor: kacper218 » 31 maja 2013, 13:53
kaszlok pisze: W jaki sposób ? Miałem napisane, że 100 = 2^2 * 5^2
a potem gcd(4,25) = 1 i gcd (2,25)=1 nie wiem tylko po co i z czego to wynika
W tym przypadku korzystamy z chińskiego twierdzenia o resztach i możemy nasze równanie zapisać jako układ równań:
\(\begin{cases}
x\equiv 2^{1000} (mod \ 4)\\
x \equiv 2^{1000} (mod \ 25)
\end{cases}\)
I rozwiązujesz ten układ równań
Pierwsze oczywiste. Drugie z twierdzenia Eulera się liczy
Pomogłem? Daj plusika
Masz pytania? Napisz priv
Przepisywanie prac do
\(\LaTeX- a\)
Korepetycje Radzymin i okolice.
kaszlok
Rozkręcam się
Posty: 57 Rejestracja: 04 mar 2013, 11:53
Podziękowania: 34 razy
Post
autor: kaszlok » 01 cze 2013, 00:04
Dlaczego pierwsze oczywiste ?
patryk00714
Mistrz
Posty: 8799 Rejestracja: 13 mar 2011, 12:28
Lokalizacja: Śmigiel
Podziękowania: 92 razy
Otrzymane podziękowania: 4449 razy
Płeć:
Post
autor: patryk00714 » 01 cze 2013, 00:14
\(2^{1000}=4^{500}\)
Otrzymałeś odpowiedź do umieszczonego zadania? Podziękuj autorowi za rozwiązanie!!
\(\exp (i \pi) +1=0\)
kaszlok
Rozkręcam się
Posty: 57 Rejestracja: 04 mar 2013, 11:53
Podziękowania: 34 razy
Post
autor: kaszlok » 01 cze 2013, 00:27
No tak to wiem, i reszta 0, tyle że my to zapisywaliśmy tak:
\(2^{1000} \equiv ? (mod \ 4)\) .
Zastanawiam się tylko czemu było sprawdzane gcd(4,25)
zamiast gcd(2,4)
bo jest 2^1000 = ? (mod4) a nie 2^1000 = ? (mod 25)
kacper218
Expert
Posty: 4077 Rejestracja: 02 paź 2009, 14:33
Lokalizacja: Radzymin
Podziękowania: 5 razy
Otrzymane podziękowania: 1382 razy
Płeć:
Post
autor: kacper218 » 01 cze 2013, 15:22
to wynika właśnie z założeń twierdzenia z którego skorzystałem. Te liczby na które rozkładamy 100 muszą być względnie pierwsze
Pomogłem? Daj plusika
Masz pytania? Napisz priv
Przepisywanie prac do
\(\LaTeX- a\)
Korepetycje Radzymin i okolice.