Witam was bardzo serdecznie
Wyznacz dwie ostatnie cyfry liczby \(\displaystyle{ 2^{999}}\)
Wyznacz dwie ostatnie cyfry...
-
Artist
- Użytkownik
- Posty: 865
- Rejestracja: 27 sty 2008, o 21:07
- Płeć: Mężczyzna
- Lokalizacja: Brodnica
- Podziękował: 27 razy
- Pomógł: 239 razy
Wyznacz dwie ostatnie cyfry...
Mamy \(\displaystyle{ \phi(25)=20}\)
Jeśli \(\displaystyle{ NWD_{a,p}=1}\) to
\(\displaystyle{ a^{\phi(p)} \equiv 1 \ (mod \ p)}\)
\(\displaystyle{ 2^{20} \equiv 1 \ (mod \ 25)}\)
\(\displaystyle{ 2^{999}=2^{980+19}=2^{20 \cdot 49} \cdot 2^{19} \equiv 1^{49} \cdot 2^{19}=2^{19} \ (mod \ 25)}\)
\(\displaystyle{ 2^{999} \equiv 2^{19} \equiv 13 \ (mod \ 25) \Rightarrow 2^{999}=100k+13 \vee 100k+38 \vee 100k+63\vee
100k+88 \ gdzie \ k \in N}\)
\(\displaystyle{ 2^{999} \equiv 0 \ (mod \ 4)}\), czyli liczba jest podzielna przez 4. Z liczb wymienionych powyżej tylko \(\displaystyle{ 100k+88}\) dzieli się przez 4 (liczba dzieli sie przez 4 jeśli jej ostatnie dwie cyfry dzielą się przez4).
Zatem dwie ostatnie cyfry tej liczby to 8 i 8.
Jeśli \(\displaystyle{ NWD_{a,p}=1}\) to
\(\displaystyle{ a^{\phi(p)} \equiv 1 \ (mod \ p)}\)
\(\displaystyle{ 2^{20} \equiv 1 \ (mod \ 25)}\)
\(\displaystyle{ 2^{999}=2^{980+19}=2^{20 \cdot 49} \cdot 2^{19} \equiv 1^{49} \cdot 2^{19}=2^{19} \ (mod \ 25)}\)
\(\displaystyle{ 2^{999} \equiv 2^{19} \equiv 13 \ (mod \ 25) \Rightarrow 2^{999}=100k+13 \vee 100k+38 \vee 100k+63\vee
100k+88 \ gdzie \ k \in N}\)
\(\displaystyle{ 2^{999} \equiv 0 \ (mod \ 4)}\), czyli liczba jest podzielna przez 4. Z liczb wymienionych powyżej tylko \(\displaystyle{ 100k+88}\) dzieli się przez 4 (liczba dzieli sie przez 4 jeśli jej ostatnie dwie cyfry dzielą się przez4).
Zatem dwie ostatnie cyfry tej liczby to 8 i 8.
Ostatnio zmieniony 3 kwie 2009, o 15:23 przez Artist, łącznie zmieniany 2 razy.
Wyznacz dwie ostatnie cyfry...
A można by dowód na
\(\displaystyle{ a^{ \phi(p)} \equiv 1 \ (mod \ p)}\) ?
\(\displaystyle{ a^{ \phi(p)} \equiv 1 \ (mod \ p)}\) ?
-
frej
Wyznacz dwie ostatnie cyfry...
Moim zdaniem dowód ten nie jest zbyt trudny do zrozumienia, co innego do wymyślenia...
Odnośnie \(\displaystyle{ \LaTeX -a}\), to aby uzyskać
\(\displaystyle{ a^{\varphi(p)} \equiv 1 \pmod{p}}\)
należy wpisać
Odnośnie \(\displaystyle{ \LaTeX -a}\), to aby uzyskać
\(\displaystyle{ a^{\varphi(p)} \equiv 1 \pmod{p}}\)
należy wpisać
Kod: Zaznacz cały
a^{varphi(p)} equiv 1 pmod{p}
Wyznacz dwie ostatnie cyfry...
Zamieszczam nieco inną metodę.
\(\displaystyle{ 2^{7}=128\equiv3\pmod{25}}\)
\(\displaystyle{ 2^{10}=1024\equiv-1\pmod{25}}\)
\(\displaystyle{ 2^{997}=(2^{10})^{99}\cdot2^{7}\equiv(-1)^{99}\cdot3\ \equiv-3\ \equiv22\pmod{25}}\)
Jeśli \(\displaystyle{ d}\) jest dowolną liczbą naturalną, to \(\displaystyle{ ad\equiv bd \pmod{md}}\), wtedy i tylko wtedy, gdy \(\displaystyle{ a\equiv b \pmod{m}}\).
Bo: \(\displaystyle{ m|a-b \Leftrightarrow md|(a-b)d}\).
Zatem:
\(\displaystyle{ 4 \cdot 2^{997}\equiv4 \cdot 22\pmod{4 \cdot 25} \Leftrightarrow 2^{999}\equiv 88\pmod{100}}\)
Dwie ostatnie cyfry liczby \(\displaystyle{ 2^{999}}\) to \(\displaystyle{ 8}\) i \(\displaystyle{ 8}\).
\(\displaystyle{ 2^{7}=128\equiv3\pmod{25}}\)
\(\displaystyle{ 2^{10}=1024\equiv-1\pmod{25}}\)
\(\displaystyle{ 2^{997}=(2^{10})^{99}\cdot2^{7}\equiv(-1)^{99}\cdot3\ \equiv-3\ \equiv22\pmod{25}}\)
Jeśli \(\displaystyle{ d}\) jest dowolną liczbą naturalną, to \(\displaystyle{ ad\equiv bd \pmod{md}}\), wtedy i tylko wtedy, gdy \(\displaystyle{ a\equiv b \pmod{m}}\).
Bo: \(\displaystyle{ m|a-b \Leftrightarrow md|(a-b)d}\).
Zatem:
\(\displaystyle{ 4 \cdot 2^{997}\equiv4 \cdot 22\pmod{4 \cdot 25} \Leftrightarrow 2^{999}\equiv 88\pmod{100}}\)
Dwie ostatnie cyfry liczby \(\displaystyle{ 2^{999}}\) to \(\displaystyle{ 8}\) i \(\displaystyle{ 8}\).