Podzielność potęg

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
squared
Użytkownik
Użytkownik
Posty: 1017
Rejestracja: 21 mar 2009, o 11:11
Płeć: Mężczyzna
Podziękował: 167 razy
Pomógł: 152 razy

Podzielność potęg

Post autor: squared »

Chciałem zapytać, jak rozwiązywać tego typu zadania:

\(\displaystyle{ 1)}\) Obliczyć resztę w dzielenia \(\displaystyle{ 7^{7^7}}}\) przez \(\displaystyle{ 777}\).
Nie wiem jaki tu trick zastosować.

\(\displaystyle{ 2)}\) Obliczyć resztę w dzielenia \(\displaystyle{ 7^{8^9}}}\) przez \(\displaystyle{ 1001}\).

\(\displaystyle{ 4)}\) Obliczyć resztę w dzielenia \(\displaystyle{ 543^{12347}}\) przez \(\displaystyle{ 693}\).

\(\displaystyle{ 5)}\) Obliczyć resztę z dzielenia \(\displaystyle{ 123^{1234}}\) przez \(\displaystyle{ 3289}\).
Wiem, że tu powinno się jakoś skorzystać np. z chińskiego twierdzenia o resztach, czy Twierdzenia Fermata.

Najpierw zapisałem, że: \(\displaystyle{ 3289=23\cdot 11 \cdot 13 \\
1234=2 \cdot 617}\)


No nie wiem z Małego Twierdzenia Fermata:
\(\displaystyle{ 123^{23-1} \equiv 1 \mod 23 \\
123^{22} \equiv 1 \mod 23 \\
1234=56 \cdot 22 +2\\
123^{1234}=123^{56 \cdot 22 + 2} = 123^{56 \cdot 22} \cdot 123^{2}}\)


I nie wiem, czy mogę zrobić tak:
\(\displaystyle{ 123^{1234} \equiv \mod 23 \\
123^2 \equiv \mod 23}\)


No i co dalej? Myślę, że są może rozsądniejsze rozwiązania.


\(\displaystyle{ 6)}\) Znaleźć ostatnie trzy cyfry liczby \(\displaystyle{ 23^{23^{23^{23}}}}}\).

No to idę od samej góry i biorę: \(\displaystyle{ 23^{23}}\). Po przejrzeniu można zauważyć, że ostatni cyfra tej potęgi może być: \(\displaystyle{ 3,9,7,1}\). Dokładnie w takiej kolejności one występują cyklicznie. Więc dla \(\displaystyle{ 23^{23}}\) ostatnia cyfra to \(\displaystyle{ 7.}\)

Stąd mam: \(\displaystyle{ 23^{23^{\text{COŚ}7}}}\)

No i generalnie wiadomość, że \(\displaystyle{ 7}\) na końcu jest to dla mnie za mało w tym przypadku. Poza tym mamy i tak znaleźć 3 ostatnie cyfry. Jakieś pomysły?

Myślałem, by pomyśleć tak. Jakbym miał \(\displaystyle{ 23^{23^{\text{COŚ}00}}}\) to była by to wielokrotność \(\displaystyle{ 4}\) wtedy mam ostatnia cyfrę tej liczby \(\displaystyle{ 1}\). Skoro jest na końcu \(\displaystyle{ 7}\) to patrząc na cykliczność znowu otrzymam: \(\displaystyle{ 23^{\text{COŚ}7}}\) i ostatnia cyfra tej liczby to znowu będzie \(\displaystyle{ 7}\). I tak powinno być, tak wychodzi zresztą. No, a co z pozostałymi cyframi od końca? Mam szukać jak zmieniają się dalsze cyfry przy potęgowaniu i próbować tak jak tu wysnuć wniosek?

\(\displaystyle{ 7)}\) Znaleźć czwartą od końca cyfrę liczby \(\displaystyle{ 7^{7^{7^{7}}}}\)
To w sumie podobnie jak wyżej. Mam tak samo na to zadanie spojrzeć?

Przepraszam, że tyle na raz. Nie chodzi mi wprost to rozwiązanie, tylko jak to nich podejść, jak je ugryźć. Wiem, że generalnie warto rozbijać te potęgi, potem jakoś kombinować itd. Ale jak widać nie wychodzi.
ODPOWIEDZ