a)\(\displaystyle{ 2 ^{999} }\)
b)\(\displaystyle{ 76 ^{57}-57 ^{76} }\)
Jest na to jakiś sposób? Próbowałem znaleźć powtarzalność wśród wyników \(\displaystyle{ 2^{k} mod 100 }\) ale nie widzę żeby jakaś okresowość istniała.
Wyznaczyć dwie ostatnie cyfry liczby
- Janusz Tracz
- Użytkownik
- Posty: 4054
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1389 razy
Re: Wyznaczyć dwie ostatnie cyfry liczby
W pierwszym można zauważyć, że \(\displaystyle{ 2^{20}\equiv 1\bmod 25}\) (Twierdzenie Eulera) więc \(\displaystyle{ 2^{22}\equiv 4\bmod 100}\) a to pozwala już szybko obniżyć potęgę \(\displaystyle{ 999}\) bo
\(\displaystyle{ 2^{999}=\left( 2^{22}\right)^{45} \cdot 2^9 \equiv 4^{45} \cdot 2^9 = 2^{99} = \left( 2^{22}\right)^{4} \cdot 2^{11}\equiv 4^4\cdot 2^{11}=2^{19} \left( \bmod 100\right) }\)
\(\displaystyle{ 2^{999}=\left( 2^{22}\right)^{45} \cdot 2^9 \equiv 4^{45} \cdot 2^9 = 2^{99} = \left( 2^{22}\right)^{4} \cdot 2^{11}\equiv 4^4\cdot 2^{11}=2^{19} \left( \bmod 100\right) }\)
-
- Użytkownik
- Posty: 133
- Rejestracja: 27 lip 2019, o 22:19
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 52 razy
- Pomógł: 15 razy
Re: Wyznaczyć dwie ostatnie cyfry liczby
\(\displaystyle{ 2^{999}}\) jest oczywiście podzielna przez \(\displaystyle{ 4}\), stąd
\(\displaystyle{ 2^{999} = 4k}\), gdzie \(\displaystyle{ k \in \mathbb{Z}}\)
Ponadto \(\displaystyle{ \NWD(2, 25) = 1}\), więc z twierdzenia Eulera zachodzi:
\(\displaystyle{ 2^{\varphi(25)} \equiv 1 \pmod{25}}\) oraz \(\displaystyle{ \varphi(25) = \varphi(5^2) = (5-1) \cdot 5^{2-1} = 4 \cdot 5^1 = 20}\)
Stąd:
\(\displaystyle{ 2^{20} \equiv 1 \pmod{25}}\)
Zachodzi więc
\(\displaystyle{ 2^{999} \equiv 2^{980+19} \equiv 2^{980} \cdot 2^{19} \equiv (2^{20})^{49} \cdot 2^{19} \equiv 1^{49} \cdot 2^{19} \equiv 2^{19} \equiv 2^{18 + 1} \equiv \\ \equiv 2^{18} \cdot 2 \equiv (2^9)^2 \cdot 2 \equiv (512)^2 \cdot 2 \equiv (12)^2 \cdot 2 \equiv 144 \cdot 2 \equiv 19 \cdot 2 \equiv 38 \equiv 13 \pmod{25}}\)
A więc
\(\displaystyle{ 2^{999} = 25l + 13}\), gdzie \(\displaystyle{ l \in \mathbb{Z} \ \ \ (1)}\)
Mamy więc:
\(\displaystyle{ 2^{999} = 4k = 25l + 13}\), a więc \(\displaystyle{ 4|25l+13}\). Musi więc zachodzić:
\(\displaystyle{ 25l + 13 \equiv 0 \pmod{4}}\)
\(\displaystyle{ 25l + 13 \equiv (24+1)l + 13 \equiv l + 13 \equiv l - 3 \pmod{4}}\),
a więc
\(\displaystyle{ l \equiv 3 \pmod{4}}\)
Stąd \(\displaystyle{ l = 4t + 3}\), gdzie \(\displaystyle{ t \in \mathbb{Z}}\)
Podstawiając do (1), mamy:
\(\displaystyle{ 2^{999} = 25l + 13 = 25(4t + 3) + 13 = 100t + 75 + 13 = 100t + 88}\), więc widzimy, że dwie ostatnie cyfry tej liczby to 88
//edit
Sposób Janusza Tracza oczywiście znacznie szybszy, trochę przedłużyłem rozwiązanie zadania.
\(\displaystyle{ 2^{999} = 4k}\), gdzie \(\displaystyle{ k \in \mathbb{Z}}\)
Ponadto \(\displaystyle{ \NWD(2, 25) = 1}\), więc z twierdzenia Eulera zachodzi:
\(\displaystyle{ 2^{\varphi(25)} \equiv 1 \pmod{25}}\) oraz \(\displaystyle{ \varphi(25) = \varphi(5^2) = (5-1) \cdot 5^{2-1} = 4 \cdot 5^1 = 20}\)
Stąd:
\(\displaystyle{ 2^{20} \equiv 1 \pmod{25}}\)
Zachodzi więc
\(\displaystyle{ 2^{999} \equiv 2^{980+19} \equiv 2^{980} \cdot 2^{19} \equiv (2^{20})^{49} \cdot 2^{19} \equiv 1^{49} \cdot 2^{19} \equiv 2^{19} \equiv 2^{18 + 1} \equiv \\ \equiv 2^{18} \cdot 2 \equiv (2^9)^2 \cdot 2 \equiv (512)^2 \cdot 2 \equiv (12)^2 \cdot 2 \equiv 144 \cdot 2 \equiv 19 \cdot 2 \equiv 38 \equiv 13 \pmod{25}}\)
A więc
\(\displaystyle{ 2^{999} = 25l + 13}\), gdzie \(\displaystyle{ l \in \mathbb{Z} \ \ \ (1)}\)
Mamy więc:
\(\displaystyle{ 2^{999} = 4k = 25l + 13}\), a więc \(\displaystyle{ 4|25l+13}\). Musi więc zachodzić:
\(\displaystyle{ 25l + 13 \equiv 0 \pmod{4}}\)
\(\displaystyle{ 25l + 13 \equiv (24+1)l + 13 \equiv l + 13 \equiv l - 3 \pmod{4}}\),
a więc
\(\displaystyle{ l \equiv 3 \pmod{4}}\)
Stąd \(\displaystyle{ l = 4t + 3}\), gdzie \(\displaystyle{ t \in \mathbb{Z}}\)
Podstawiając do (1), mamy:
\(\displaystyle{ 2^{999} = 25l + 13 = 25(4t + 3) + 13 = 100t + 75 + 13 = 100t + 88}\), więc widzimy, że dwie ostatnie cyfry tej liczby to 88
//edit
Sposób Janusza Tracza oczywiście znacznie szybszy, trochę przedłużyłem rozwiązanie zadania.
-
- Użytkownik
- Posty: 22153
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3748 razy
Re: Wyznaczyć dwie ostatnie cyfry liczby
A może tak:
$$2^{22}-2^2=4(2^{20}-1)=4(2^{10}-1)(2^{10}+1)=4\cdot1023\cdot 1025=100\cdot41\cdot1023,$$
zatem $$2^{999}\equiv 2^{979}\equiv\dots\equiv 2^{19}=1024\cdot 512=524288\equiv 88$$
$$2^{22}-2^2=4(2^{20}-1)=4(2^{10}-1)(2^{10}+1)=4\cdot1023\cdot 1025=100\cdot41\cdot1023,$$
zatem $$2^{999}\equiv 2^{979}\equiv\dots\equiv 2^{19}=1024\cdot 512=524288\equiv 88$$
Re: Wyznaczyć dwie ostatnie cyfry liczby
Ja polecam się uczyć jednocześnie programowania, mi zazwyczaj to pomagało zrozumieć jak coś działa, zobacz to
Kod: Zaznacz cały
https://stackoverflow.com/questions/41664806/last-2-digits-of-an-integer-python-3