Wyznaczyć dwie ostatnie cyfry liczby

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
F3NRIR
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 27 paź 2019, o 15:36
Płeć: Mężczyzna
wiek: 20

Wyznaczyć dwie ostatnie cyfry liczby

Post autor: F3NRIR »

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.
Awatar użytkownika
Janusz Tracz
Użytkownik
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

Post autor: Janusz Tracz »

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

Post autor: Thingoln »

\(\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. :)
a4karo
Użytkownik
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

Post autor: a4karo »

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$$
Stepyanka
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 4 lut 2020, o 12:06
Płeć: Mężczyzna
wiek: 33

Re: Wyznaczyć dwie ostatnie cyfry liczby

Post autor: Stepyanka »

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
ODPOWIEDZ