Podaj dwie ostatnie cyfry liczby:
\(\displaystyle{ 9^{9^{9}}}}\)
Macie jakieś podpowiedzi, albo wskazówki. Jeżeli chodzi o zagadnienia z teorii liczb to jestem całkowicie zielony. Jak ugryźć taki przykład?
Kongrurencja - wyznacz dwie ostatnie cyfry
-
veldrim
- Użytkownik
- Posty: 72
- Rejestracja: 29 sie 2008, o 20:05
- Płeć: Mężczyzna
- Lokalizacja: Zielona Góra
- Podziękował: 9 razy
- Pomógł: 4 razy
Kongrurencja - wyznacz dwie ostatnie cyfry
Twój link nie działa Ale wydaje mi się, że sobie poradziłem. Mógłbyś powiedzieć mi czy wynik jest dobry? Ostatnie cyfry to 09. Zgadza się?
-
Jan Kraszewski
- Administrator
- Posty: 34244
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
-
veldrim
- Użytkownik
- Posty: 72
- Rejestracja: 29 sie 2008, o 20:05
- Płeć: Mężczyzna
- Lokalizacja: Zielona Góra
- Podziękował: 9 razy
- Pomógł: 4 razy
Kongrurencja - wyznacz dwie ostatnie cyfry
Wielkie dzięki za wszystko. Próbuję to przetrawić, ale coś czarno to widzę. Posiedzę, pomyśle, ale mało we mnie wiary w tym. Czytam i czytam, sam coś próbuję, ale wychodzą z tego potworne rzeczy.-- 16 grudnia 2009, 16:54 --Próbowałem, próbowałem, ale nic mi nie wychodzi...
-
mkb
- Użytkownik
- Posty: 244
- Rejestracja: 5 paź 2009, o 16:54
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 47 razy
Kongrurencja - wyznacz dwie ostatnie cyfry
Jeśli to nie muszą być kongurencje, to w tym szczególnym przypadku można inaczej. Wystarczy zauważyć, że:
\(\displaystyle{ 9^{9^{9}}}=(10-1)^{9^{9}}}}\)
oraz że o ostatnich dwóch cyfrach decydują dwa ostatnie wyrazy rozwinięcia:
\(\displaystyle{ ...+ {9^{9} \choose 1} \cdot 10^{1} \cdot (-1)^{9^{9}-1}+ {9^{9} \choose 0} \cdot 10^{0} \cdot (-1)^{9^{9}}}\)
9 do dowolnej potęgi (całkowitej nieujemnej) jest nieparzyste, symbole Newtona są odpowiednio równe \(\displaystyle{ 9^{9}}\) i \(\displaystyle{ 1}\),
Przedostatni wyraz daje wkład 90 (liczba dziesiątek równa ostatniej cyfrze w \(\displaystyle{ 9^{9}}\)), ostatni wyraz daje wkład (-1), czyli dwie ostatnie cyfry to 89.
\(\displaystyle{ 9^{9^{9}}}=(10-1)^{9^{9}}}}\)
oraz że o ostatnich dwóch cyfrach decydują dwa ostatnie wyrazy rozwinięcia:
\(\displaystyle{ ...+ {9^{9} \choose 1} \cdot 10^{1} \cdot (-1)^{9^{9}-1}+ {9^{9} \choose 0} \cdot 10^{0} \cdot (-1)^{9^{9}}}\)
9 do dowolnej potęgi (całkowitej nieujemnej) jest nieparzyste, symbole Newtona są odpowiednio równe \(\displaystyle{ 9^{9}}\) i \(\displaystyle{ 1}\),
Przedostatni wyraz daje wkład 90 (liczba dziesiątek równa ostatniej cyfrze w \(\displaystyle{ 9^{9}}\)), ostatni wyraz daje wkład (-1), czyli dwie ostatnie cyfry to 89.
-
BettyBoo
- Użytkownik
- Posty: 5356
- Rejestracja: 10 kwie 2009, o 10:22
- Płeć: Kobieta
- Lokalizacja: Gliwice
- Pomógł: 1381 razy
Kongrurencja - wyznacz dwie ostatnie cyfry
No to przepiszę rozumowanie z tego cytowanego wątku dla Twojego przykładu.
Tak naprawdę masz obliczyć \(\displaystyle{ 9^{9^{9}} \mod100}\). Wiadomo (z tw Eulera), że \(\displaystyle{ a^{\varphi(100)}\equiv 1 \mod100}\) o ile \(\displaystyle{ NWD(a,100)=1}\). Ponieważ \(\displaystyle{ NWD(9,100)=1}\) oraz \(\displaystyle{ \varphi(100)=100\frac{1}{2}\frac{4}{5}=40}\), to zachodzi \(\displaystyle{ 9^{40}\equiv 1 \mod100}\).
Wobec tego trzeba teraz obliczyć \(\displaystyle{ 9^{9} \mod40}\) żeby wiedzieć, jak uprościć zadaną potęgę. Tutaj już niestety nic się nie da zastosować poza zwykłym potęgowaniem. Na szczęście niezbyt się napracujemy, ponieważ \(\displaystyle{ 9^2\equiv 1\mod 40}\), a więc\(\displaystyle{ 9^9\equiv 9\mod 40}\).
Mamy wobec tego \(\displaystyle{ 9^{9^{9}}\equiv 9^9\mod100}\). Teraz nie pozostaje znowu nic innego jak to obliczyć. To liczymy najlepiej te potęgi 9, których wykładniki są potęgami 2 (tak jest najszybciej i najłatwiej). Przy okazji można wykorzystać elementy przeciwne (kiedy będzie nam to na rękę, m.in. po to, żeby nie operować na zbyt dużych liczbach).
Obliczamy (wszystkie poniższe przystawania modulo 100)
\(\displaystyle{ 9^2\equiv 81\equiv -19,\quad 9^4\equiv (-19)^2\equiv 61,\quad 9^8\equiv 61^2\equiv 61+60\equiv 21}\).
Zatem
\(\displaystyle{ 9^{9^9}\equiv 9^9\equiv 9^89\equiv 21\cdot 9\equiv 89}\)
Pozdrawiam.
Tak naprawdę masz obliczyć \(\displaystyle{ 9^{9^{9}} \mod100}\). Wiadomo (z tw Eulera), że \(\displaystyle{ a^{\varphi(100)}\equiv 1 \mod100}\) o ile \(\displaystyle{ NWD(a,100)=1}\). Ponieważ \(\displaystyle{ NWD(9,100)=1}\) oraz \(\displaystyle{ \varphi(100)=100\frac{1}{2}\frac{4}{5}=40}\), to zachodzi \(\displaystyle{ 9^{40}\equiv 1 \mod100}\).
Wobec tego trzeba teraz obliczyć \(\displaystyle{ 9^{9} \mod40}\) żeby wiedzieć, jak uprościć zadaną potęgę. Tutaj już niestety nic się nie da zastosować poza zwykłym potęgowaniem. Na szczęście niezbyt się napracujemy, ponieważ \(\displaystyle{ 9^2\equiv 1\mod 40}\), a więc\(\displaystyle{ 9^9\equiv 9\mod 40}\).
Mamy wobec tego \(\displaystyle{ 9^{9^{9}}\equiv 9^9\mod100}\). Teraz nie pozostaje znowu nic innego jak to obliczyć. To liczymy najlepiej te potęgi 9, których wykładniki są potęgami 2 (tak jest najszybciej i najłatwiej). Przy okazji można wykorzystać elementy przeciwne (kiedy będzie nam to na rękę, m.in. po to, żeby nie operować na zbyt dużych liczbach).
Obliczamy (wszystkie poniższe przystawania modulo 100)
\(\displaystyle{ 9^2\equiv 81\equiv -19,\quad 9^4\equiv (-19)^2\equiv 61,\quad 9^8\equiv 61^2\equiv 61+60\equiv 21}\).
Zatem
\(\displaystyle{ 9^{9^9}\equiv 9^9\equiv 9^89\equiv 21\cdot 9\equiv 89}\)
Pozdrawiam.
-
veldrim
- Użytkownik
- Posty: 72
- Rejestracja: 29 sie 2008, o 20:05
- Płeć: Mężczyzna
- Lokalizacja: Zielona Góra
- Podziękował: 9 razy
- Pomógł: 4 razy
Kongrurencja - wyznacz dwie ostatnie cyfry
Wielkie dzięki, teraz już rozumiem, wytłumaczyłeś mi etap, którego nie potrafiłem przeskoczyć.
Sto razy dziękuję i wesołych świąt życzę w przypadku gdybyśmy mieli w tym roku jeszcze nie porozmawiać.
Sto razy dziękuję i wesołych świąt życzę w przypadku gdybyśmy mieli w tym roku jeszcze nie porozmawiać.