Dwa (pewnie proste) problemy z potęgami
-
- Użytkownik
- Posty: 2727
- Rejestracja: 14 paź 2004, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: podkarpacie
- Podziękował: 3 razy
- Pomógł: 945 razy
Dwa (pewnie proste) problemy z potęgami
Obydwa mogę zrobić na piechotę (w pierwszym wykorzystując cykliczność ostatnich potęg czwórki, w drugim logarytmując i bawiąc się w szacowanie), ale z tego co pamiętam, to można to zrobić jakoś sprytniej. Zadania są chyba dość banalne, ale od dwudziestu lat nie zajmowałem się teorią liczb.
1. Jaka jest ostatnia cyfra liczby \(\displaystyle{ 4^{44}}\)?
2. Wyznacz \(\displaystyle{ x<7^{25}}\) podzielny przez \(\displaystyle{ 11}\).
1. Jaka jest ostatnia cyfra liczby \(\displaystyle{ 4^{44}}\)?
2. Wyznacz \(\displaystyle{ x<7^{25}}\) podzielny przez \(\displaystyle{ 11}\).
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Dwa (pewnie proste) problemy z potęgami
ad 1 A po co u teoria liczb?? \(\displaystyle{ 4^1=4}\), \(\displaystyle{ 4^2=16}\), \(\displaystyle{ 4^3=64}\) etc/ Widzisz regularnośc na ostatnim miejscu? Prosciutka indukcja
ad 2 chyba cos żle napisałes, ale jak nie, to \(\displaystyle{ x=11}\)
ad 2 chyba cos żle napisałes, ale jak nie, to \(\displaystyle{ x=11}\)
-
- Użytkownik
- Posty: 2727
- Rejestracja: 14 paź 2004, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: podkarpacie
- Podziękował: 3 razy
- Pomógł: 945 razy
Dwa (pewnie proste) problemy z potęgami
To znaczy, że w pierwszym dobrze myślałem, że tu nie trzeba jakiejś wielkiej teorii.
W drugim (taką treść dostałem mailem), ale chyba chodzi o największego takiego \(\displaystyle{ x}\)-a. Tak jak pisałem, zacząłem to na zasadzie
\(\displaystyle{ 11n<7^{25}}\)
\(\displaystyle{ \ln11n<\ln7^25}}\)
\(\displaystyle{ \ln n+\ln11<25\ln7}\)
\(\displaystyle{ \ln n<25\ln7-\ln11}\)
Wyliczam po prawej i znajduję to \(\displaystyle{ n}\), ale myślałem, ze tu jakieś "bardzo sprytne" teorioliczbowe przekształcenie da odpowiedź (jakieś modulo itp.).
W drugim (taką treść dostałem mailem), ale chyba chodzi o największego takiego \(\displaystyle{ x}\)-a. Tak jak pisałem, zacząłem to na zasadzie
\(\displaystyle{ 11n<7^{25}}\)
\(\displaystyle{ \ln11n<\ln7^25}}\)
\(\displaystyle{ \ln n+\ln11<25\ln7}\)
\(\displaystyle{ \ln n<25\ln7-\ln11}\)
Wyliczam po prawej i znajduję to \(\displaystyle{ n}\), ale myślałem, ze tu jakieś "bardzo sprytne" teorioliczbowe przekształcenie da odpowiedź (jakieś modulo itp.).
Ostatnio zmieniony 25 sty 2014, o 17:37 przez chris_f, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
Dwa (pewnie proste) problemy z potęgami
Po krótkiej chwili wyliczeń łatwo zauważyć, że \(\displaystyle{ 7^5 \equiv -1 \pmod{11}}\) stąd \(\displaystyle{ 7^{25}\equiv -1 \pmod{11}}\), zatem szukana liczba to \(\displaystyle{ 7^{25}-12}\)
-
- Użytkownik
- Posty: 2727
- Rejestracja: 14 paź 2004, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: podkarpacie
- Podziękował: 3 razy
- Pomógł: 945 razy
Dwa (pewnie proste) problemy z potęgami
Czyli dla nierówności \(\displaystyle{ x<8^{25}}\) to będzie jakoś tak?
Policzyłem, że \(\displaystyle{ 8^5=32768\equiv-1\pmod{11}}\), tak więc tą liczbą będzie \(\displaystyle{ 8^{25}-12}\)?
Policzyłem, że \(\displaystyle{ 8^5=32768\equiv-1\pmod{11}}\), tak więc tą liczbą będzie \(\displaystyle{ 8^{25}-12}\)?
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Dwa (pewnie proste) problemy z potęgami
Jak \(\displaystyle{ 7^{25}-12}\) jest podzielne przez \(\displaystyle{ 11}\), to \(\displaystyle{ 7^{25}-1}\) też . Powinno być \(\displaystyle{ 7^{25}-10}\)
-
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
Dwa (pewnie proste) problemy z potęgami
Chwila, pomyliłem się. Powinno być \(\displaystyle{ 7^{25}-10}\).
EDIT: Ale idea jest dobra, i to się liczy. A z tą ósemką też będzie \(\displaystyle{ 8^{25}-10}\).
EDIT: Ale idea jest dobra, i to się liczy. A z tą ósemką też będzie \(\displaystyle{ 8^{25}-10}\).
-
- Użytkownik
- Posty: 2727
- Rejestracja: 14 paź 2004, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: podkarpacie
- Podziękował: 3 razy
- Pomógł: 945 razy
Dwa (pewnie proste) problemy z potęgami
Dzięki, do tego też doszedłem rachując w Excelu (dla sprawdzenia). Ale dzięki za podpowiedzi.
PS. A co do tej ostatniej cyfry: z tą czwórką to sprawa była oczywista, wiadomo, że tam będzie się powtarzać \(\displaystyle{ 4}\) i \(\displaystyle{ 6}\).
A co w przypadku, gdy mamy np. \(\displaystyle{ 7^{24}}\). Tu też mamy cyklicznie powtarzającą się cyfry \(\displaystyle{ 7,9,3,1}\) i da się bez problemów wyznaczyć, że to będzie \(\displaystyle{ 1}\), ale tak jakoś prymitywne mi się to wydaje (za proste ). Da się jakoś inaczej?
PS. A co do tej ostatniej cyfry: z tą czwórką to sprawa była oczywista, wiadomo, że tam będzie się powtarzać \(\displaystyle{ 4}\) i \(\displaystyle{ 6}\).
A co w przypadku, gdy mamy np. \(\displaystyle{ 7^{24}}\). Tu też mamy cyklicznie powtarzającą się cyfry \(\displaystyle{ 7,9,3,1}\) i da się bez problemów wyznaczyć, że to będzie \(\displaystyle{ 1}\), ale tak jakoś prymitywne mi się to wydaje (za proste ). Da się jakoś inaczej?
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Dwa (pewnie proste) problemy z potęgami
liczysz \(\displaystyle{ 7^n \mod 10}\) i zobaczysz, kiedy się zapętli. Wtedy wykładnik możesz wziąć modulo długość tego cyklu