Z Twierdzenia Eulera?
-
- Użytkownik
- Posty: 20
- Rejestracja: 22 paź 2016, o 14:49
- Płeć: Mężczyzna
- Lokalizacja: Olszyna
- Podziękował: 2 razy
Z Twierdzenia Eulera?
Mam pewien problem. Rozwiązywałem zadanko mianowicie jakie są trzy ostatnie cyfry liczby \(\displaystyle{ 3^{2005}}\) Bez turbulencji zadanie zostało rozwiązane jednak pojawiło się pytanie: Jak policzyć trzy ostatnie cyfry dużych liczb parzystych np.\(\displaystyle{ 2^{2005}}\) pomijając już piątkę, chyba, że jest coś eleganckiego. Do tego jeszcze zastanawia mnie metoda liczenia trzech ostatnich liczb trochę mniejszych potęg, np. trzy ostanie liczb \(\displaystyle{ 7^{23}}\)
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Z Twierdzenia Eulera?
Generalnie:
\(\displaystyle{ n^{4k+h} \mod 10 = n^h \mod 10}\)
\(\displaystyle{ n^{20k+h} \mod 100 = n^h \mod 100}\), \(\displaystyle{ h \neq 1}\)
\(\displaystyle{ n^{100k+h} \mod 1000 = n^h \mod 1000}\), \(\displaystyle{ h \neq 1 \wedge h \neq 2}\)
Łatwo to udowodnić, więc powiedzmy sobie, że na potrzeby czysto wiedzowe dowód jest zbędny
I generalnie:
\(\displaystyle{ n^{5^l(4k)+h} \mod 10^{l+1} = n^h \mod 10^{l+1}}\), \(\displaystyle{ \forall x \in \left\{0, 1, 2, ..., l\right\}: h \neq x}\)
\(\displaystyle{ n^{4k+h} \mod 10 = n^h \mod 10}\)
\(\displaystyle{ n^{20k+h} \mod 100 = n^h \mod 100}\), \(\displaystyle{ h \neq 1}\)
\(\displaystyle{ n^{100k+h} \mod 1000 = n^h \mod 1000}\), \(\displaystyle{ h \neq 1 \wedge h \neq 2}\)
Łatwo to udowodnić, więc powiedzmy sobie, że na potrzeby czysto wiedzowe dowód jest zbędny
I generalnie:
\(\displaystyle{ n^{5^l(4k)+h} \mod 10^{l+1} = n^h \mod 10^{l+1}}\), \(\displaystyle{ \forall x \in \left\{0, 1, 2, ..., l\right\}: h \neq x}\)
Ostatnio zmieniony 9 gru 2016, o 15:47 przez PoweredDragon, łącznie zmieniany 5 razy.
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Z Twierdzenia Eulera?
PoweredDragon, tylko jeszcze trzeba wspomnieć, że to działa gdy
\(\displaystyle{ \NWD(n,10)=1}\)
W przypadku \(\displaystyle{ 3^{2005}}\) to załatwia sprawę, ale zobacz na dalszą część pytania. Tutaj nie ma to zastosowania, gdyż np. \(\displaystyle{ \NWD(2,10)=2}\), więc nie można tak bezpośrednio sobie skorzystać z twierdzenia Eulera.
\(\displaystyle{ \NWD(n,10)=1}\)
W przypadku \(\displaystyle{ 3^{2005}}\) to załatwia sprawę, ale zobacz na dalszą część pytania. Tutaj nie ma to zastosowania, gdyż np. \(\displaystyle{ \NWD(2,10)=2}\), więc nie można tak bezpośrednio sobie skorzystać z twierdzenia Eulera.
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Z Twierdzenia Eulera?
Huh; jeśli korzystałem z twierdzenia Eulera to przepraszam; skorzystałem z czystych oczywistości na pierwszy rzut oka xDPremislav pisze:PoweredDragon, tylko jeszcze trzeba wspomnieć, że to działa gdy
\(\displaystyle{ \NWD(n,10)=1}\)
W przypadku \(\displaystyle{ 3^{2005}}\) to załatwia sprawę, ale zobacz na dalszą część pytania. Tutaj nie ma to zastosowania, gdyż np. \(\displaystyle{ \NWD(2,10)=2}\), więc nie można tak bezpośrednio sobie skorzystać z twierdzenia Eulera.
Przy czym to co napisałem jest prawdziwe dla każdego n...
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Z Twierdzenia Eulera?
@UP
Zapomniałem o założeniu
\(\displaystyle{ h>0}\) Dzięki!
Akurat w wypadku 7 to jest takie dość złożone, więc generalnie \(\displaystyle{ 7^{23} \mod 1000 = 7^3}\), ale to wynika z osobistych własności siódemki i jej okresów powtarzalności modulo.
Przy okazji nie do końca odpowiedziałem na pytanie (odpowiedziałem na jego pierwszą część), ale generalnie niektóre są unikalne i resztę trzeba wyznaczyć obliczeniowo (tj. np. \(\displaystyle{ 4^{23} \mod 1000 = 664}\) i nijak tego nie zredukujemy)
Zapomniałem o założeniu
\(\displaystyle{ h>0}\) Dzięki!
Akurat w wypadku 7 to jest takie dość złożone, więc generalnie \(\displaystyle{ 7^{23} \mod 1000 = 7^3}\), ale to wynika z osobistych własności siódemki i jej okresów powtarzalności modulo.
Przy okazji nie do końca odpowiedziałem na pytanie (odpowiedziałem na jego pierwszą część), ale generalnie niektóre są unikalne i resztę trzeba wyznaczyć obliczeniowo (tj. np. \(\displaystyle{ 4^{23} \mod 1000 = 664}\) i nijak tego nie zredukujemy)
Ostatnio zmieniony 9 gru 2016, o 15:52 przez PoweredDragon, łącznie zmieniany 6 razy.
-
- Użytkownik
- Posty: 20
- Rejestracja: 22 paź 2016, o 14:49
- Płeć: Mężczyzna
- Lokalizacja: Olszyna
- Podziękował: 2 razy
Z Twierdzenia Eulera?
Hyy... Po przemyśleniu udało zrobić mi się to zadanie w ten sposób.
Zauważyłem, że \(\displaystyle{ 2 ^{10} = 128\pmod{ 1000}}\). Zatem
\(\displaystyle{ 2^{(10)}^{2}= 384 \pmod{1000}\\
2 ^{(20)}^{2}= 384 \pmod{1000}}\)
Teraz wiadomo, że
\(\displaystyle{ 2^{2000}= 384 \pmod{1000}\\
2^{2005}= 288 \pmod{1000}}\)
Co myślicie na temat takiego rozwiazania? Spoko czy trochę łopatologiczne?
Zauważyłem, że \(\displaystyle{ 2 ^{10} = 128\pmod{ 1000}}\). Zatem
\(\displaystyle{ 2^{(10)}^{2}= 384 \pmod{1000}\\
2 ^{(20)}^{2}= 384 \pmod{1000}}\)
Teraz wiadomo, że
\(\displaystyle{ 2^{2000}= 384 \pmod{1000}\\
2^{2005}= 288 \pmod{1000}}\)
Co myślicie na temat takiego rozwiazania? Spoko czy trochę łopatologiczne?
Ostatnio zmieniony 18 gru 2016, o 23:42 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex] .
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Z Twierdzenia Eulera?
Moim zdaniem trochę łopatologiczne, a przede wszystkim niepoprawne.
Z rozwiązania zadania 6. z 63 OM (nie pamiętam cyfr rzymskich) zapamiętałem, że
\(\displaystyle{ 2^{20}=1048576}\), więc na pewno nie daje takiej reszty z dzielenia przez \(\displaystyle{ 1000}\), jak napisałeś.
Z rozwiązania zadania 6. z 63 OM (nie pamiętam cyfr rzymskich) zapamiętałem, że
\(\displaystyle{ 2^{20}=1048576}\), więc na pewno nie daje takiej reszty z dzielenia przez \(\displaystyle{ 1000}\), jak napisałeś.
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Z Twierdzenia Eulera?
@UP
Poza faktem, że masz błędne rozwiązanie...
\(\displaystyle{ 2^{10} \mod 1000 = 24 \\
2^{20} \mod 1000 = 576 \\
2^{40} \mod 1000 = 776 \\
2^{200} \mod 1000 = 376 \\
2^{2000} \mod 1000 = 376 \\
2^{2005} \mod 1000 = 376 \cdot 2^5 \mod 1000 = 32}\)
A z mojego wzoru:
\(\displaystyle{ 2^{2005} \mod 1000 = 2^{5^2(4 \cdot 20)+5} \mod 1000 = 2^5 \mod 1000 = 32}\)
A tak btw. sposób na liczenie mniejszych reszt:
\(\displaystyle{ 7^{23} \mod 1000 = 7^{10} \cdot 7^{10} \cdot 7^3 \mod 1000 = 7^{10} \mod 1000 \cdot 7^{10} \mod 100 \cdot 7^3 \mod 1000 = 249 \cdot 249 \cdot 343 \mod 1000 = 343}\)
Poza faktem, że masz błędne rozwiązanie...
\(\displaystyle{ 2^{10} \mod 1000 = 24 \\
2^{20} \mod 1000 = 576 \\
2^{40} \mod 1000 = 776 \\
2^{200} \mod 1000 = 376 \\
2^{2000} \mod 1000 = 376 \\
2^{2005} \mod 1000 = 376 \cdot 2^5 \mod 1000 = 32}\)
A z mojego wzoru:
\(\displaystyle{ 2^{2005} \mod 1000 = 2^{5^2(4 \cdot 20)+5} \mod 1000 = 2^5 \mod 1000 = 32}\)
A tak btw. sposób na liczenie mniejszych reszt:
\(\displaystyle{ 7^{23} \mod 1000 = 7^{10} \cdot 7^{10} \cdot 7^3 \mod 1000 = 7^{10} \mod 1000 \cdot 7^{10} \mod 100 \cdot 7^3 \mod 1000 = 249 \cdot 249 \cdot 343 \mod 1000 = 343}\)
Ostatnio zmieniony 18 gru 2016, o 23:43 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 20
- Rejestracja: 22 paź 2016, o 14:49
- Płeć: Mężczyzna
- Lokalizacja: Olszyna
- Podziękował: 2 razy
Z Twierdzenia Eulera?
Heh . Jak to się stało, że wymyśliłem dla \(\displaystyle{ 2^{10}}\) końcówkę 128 . Czyli pomysł, który przedstawiłem nie najlepszy na te większe liczby, ale dla mniejszych jedyny?
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Z Twierdzenia Eulera?
Dla mniejszych myślę jest fajny i łatwy, dla większych po prostu moje wzory i redukcja
-
- Użytkownik
- Posty: 15
- Rejestracja: 11 gru 2016, o 00:55
- Płeć: Mężczyzna
- Lokalizacja: Pisarzowice
- Podziękował: 1 raz
Z Twierdzenia Eulera?
Czy mógłbyś wyprowadzić ten dowód?PoweredDragon pisze:Generalnie:
\(\displaystyle{ n^{4k+h} \mod 10 = n^h \mod 10}\)
\(\displaystyle{ n^{20k+h} \mod 100 = n^h \mod 100}\), \(\displaystyle{ h \neq 1}\)
\(\displaystyle{ n^{100k+h} \mod 1000 = n^h \mod 1000}\), \(\displaystyle{ h \neq 1 \wedge h \neq 2}\)
Łatwo to udowodnić, więc powiedzmy sobie, że na potrzeby czysto wiedzowe dowód jest zbędny
I generalnie:
\(\displaystyle{ n^{5^l(4k)+h} \mod 10^{l+1} = n^h \mod 10^{l+1}}\), \(\displaystyle{ \forall x \in \left\{0, 1, 2, ..., l\right\}: h \neq x}\)