Z Twierdzenia Eulera?

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
ajlofmath
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 paź 2016, o 14:49
Płeć: Mężczyzna
Lokalizacja: Olszyna
Podziękował: 2 razy

Z Twierdzenia Eulera?

Post autor: ajlofmath »

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}}\)
PoweredDragon
Użytkownik
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?

Post autor: PoweredDragon »

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}\)
Ostatnio zmieniony 9 gru 2016, o 15:47 przez PoweredDragon, łącznie zmieniany 5 razy.
Awatar użytkownika
Premislav
Użytkownik
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?

Post autor: Premislav »

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.
PoweredDragon
Użytkownik
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?

Post autor: PoweredDragon »

Premislav 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.
Huh; jeśli korzystałem z twierdzenia Eulera to przepraszam; skorzystałem z czystych oczywistości na pierwszy rzut oka xD

Przy czym to co napisałem jest prawdziwe dla każdego n...
Awatar użytkownika
Premislav
Użytkownik
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?

Post autor: Premislav »

Nieprawda. Weź sobie \(\displaystyle{ n=2}\) i posprawdzaj kilka przypadków.
Np. \(\displaystyle{ 2^4 \neq 1\pmod{10}}\)
PoweredDragon
Użytkownik
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?

Post autor: PoweredDragon »

@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)
Ostatnio zmieniony 9 gru 2016, o 15:52 przez PoweredDragon, łącznie zmieniany 6 razy.
Awatar użytkownika
Premislav
Użytkownik
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?

Post autor: Premislav »

Faktycznie, przy tym obostrzeniu jest już OK i nie potrzeba żadnego twierdzenia Eulera.
ajlofmath
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 paź 2016, o 14:49
Płeć: Mężczyzna
Lokalizacja: Olszyna
Podziękował: 2 razy

Z Twierdzenia Eulera?

Post autor: ajlofmath »

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?
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].
Awatar użytkownika
Premislav
Użytkownik
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?

Post autor: Premislav »

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ś.
PoweredDragon
Użytkownik
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?

Post autor: PoweredDragon »

@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}\)
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.
ajlofmath
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 paź 2016, o 14:49
Płeć: Mężczyzna
Lokalizacja: Olszyna
Podziękował: 2 razy

Z Twierdzenia Eulera?

Post autor: ajlofmath »

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?
PoweredDragon
Użytkownik
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?

Post autor: PoweredDragon »

Dla mniejszych myślę jest fajny i łatwy, dla większych po prostu moje wzory i redukcja
trzydwaosiem
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 11 gru 2016, o 00:55
Płeć: Mężczyzna
Lokalizacja: Pisarzowice
Podziękował: 1 raz

Z Twierdzenia Eulera?

Post autor: trzydwaosiem »

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}\)
Czy mógłbyś wyprowadzić ten dowód?
ODPOWIEDZ