Znajdź trzy ostatnie cyfry liczby

[Miralem]

Mógłby ktoś sprawdzić? Mam kilka wątpliwości, co do tego zadania.

Znajdź trzy ostatnie cyfry liczby \(\displaystyle{ 3^{14404}}\)

\(\displaystyle{ NWD(3,14404)=1}\)

Należy znaleźć resztę z dzielenia liczby \(\displaystyle{ 3^{14404}}\) przez \(\displaystyle{ 1000}\)

\(\displaystyle{ \partial (1000)= \partial(2^{3}5^{3})= \partial (2^{3}) \partial (5^{3})=2^{2}(2-1)5^{2}(5-1)=400}\)

Zatem

\(\displaystyle{ 3^{14404}=3^{400 \cdot 36+4}=(3^{400})^{36}3^{4}\equiv 3^{4}\pmod{1000}}\), bo \(\displaystyle{ 3^{400}\equiv 1\pmod{1000}}\) na podstawie twierdzenia Eulera.

Ponieważ \(\displaystyle{ 3^{4}=81}\), więc trzy ostatnie cyfry liczby \(\displaystyle{ 3^{14404}}\) to \(\displaystyle{ 081}\)

Odp. \(\displaystyle{ 081}\)

[Michalinho]

Dobrze.

[Miralem]

Dziękuję, ale mam jeszcze kilka pytań:

NWD wykładnika i potęgi tej liczby musi być równe jeden?

Używam liczby 1000, bo mam znaleźć 3 ostatnie cyfry? W przypadku 2 ostatnich cyfr mam użyć 100, a w przypadku 5 ostatni cyfr 100000?

[Michalinho]

Twierdzenie Eulera mówi, że jeśli \(\displaystyle{ a\perp m}\), to \(\displaystyle{ a^{\phi(m)}\equiv 1 \text{ mod m}}\).
Odpowiadając na drugie pytanie, tak.

[Miralem]

Jak rozwiązać takie zadanie:

Znajdź trzy ostatnie cyfry liczby \(\displaystyle{ 2^{14404}}\)

Nie mogę go robić tamtym schematem, bo \(\displaystyle{ NWD(2,14404) \neq 1}\)

[Michalinho]

Nie \(\displaystyle{ (2,14404)}\), a \(\displaystyle{ (2,1000)}\).

[Miralem]

Czyli w zadaniu wyżej powinno być na początku

\(\displaystyle{ NWD(3,1000)=1}\)

zamiast

\(\displaystyle{ NWD(3,14404)=1}\)

?

[Michalinho]

Tak.
Wydaje się dobrze:
\(\displaystyle{ 2^{14404}=1000k+r; k,r\in N, 0\le r<1000}\).

Stąd \(\displaystyle{ 8| r\Rightarrow r=8r_2, r_2\in N\wedge 0\le r_2<125}\) oraz:
\(\displaystyle{ 2^{14401}=125k+r_2\Rightarrow 2^{14401}\equiv r_2 \text{ mod 125}}\).

Z twierdzenia Eulera:

\(\displaystyle{ 2^{\phi(125)}\equiv 1 \text{ mod 125}\Rightarrow 2^{100}\equiv 1\text{ mod 125}}\).
\(\displaystyle{ 2^{14401}\equiv 2\cdot 2^{100\cdot 144}\equiv 2\text{ mod 125}}\), a więc \(\displaystyle{ r_2\equiv 2\text{ mod 125}\Rightarrow r_2=2\Rightarrow r=16}\).

Czyli ostatnie trzy cyfry to \(\displaystyle{ 016}\).

EDIT:
Sprawdziłem w Wolframie, że dobrze .

[Miralem]

Dzięki, ale wiele z tego nie rozumiem. Czy nie dałoby się tego zrobić analogicznie do tego, jak ja w pierwszym poście? Jakoś z rozbiciem na dwa przypadki z modulo(?).

[Michalinho]

A czego nie rozumiesz? Od tego jest forum, więc pytaj
Nie da się rozbić na przypadki z modulo, bo tu jest jeden przypadek.

[Miralem]

Robisz innym schematem niż ja w pierwszym poście, a dopiero co go ogarnąłem.

Ale jeśli się nie da Eulerem, to spróbuję zrozumieć twój sposób.

Skąd się nagle wzięły 8 i 125 w drugiej linijce?

Wyżej masz \(\displaystyle{ 0 \le r <1000}\)

Tak więc r może wynosić np. 3 i wtedy to co niżej nie jest prawdą. Skąd się wzięła ta 8, a skąd 125?

[wielkireturner]

Robisz innym schematem niż ja w pierwszym poście, a dopiero co go ogarnąłem.

Ale jeśli się nie da Eulerem, to spróbuję zrozumieć twój sposób.

Skąd się nagle wzięły 8 i 125 w drugiej linijce?

Wyżej masz \(\displaystyle{ 0 \le r <1000}\)

Tak więc r może wynosić np. 3 i wtedy to co niżej nie jest prawdą. Skąd się wzięła ta 8, a skąd 125?

\(\displaystyle{ 8}\), bo \(\displaystyle{ 1000}\) i potęga \(\displaystyle{ 2}\) dzielą się przez \(\displaystyle{ 8}\), a reszta nie, w \(\displaystyle{ 2^{14401}=125k + r_{2}}\) jak podzielić przez \(\displaystyle{ 125}\) to \(\displaystyle{ 125k}\) dzieli się przez \(\displaystyle{ 125}\), a przez to składnik \(\displaystyle{ 125k}\) nie wpływa na to, jaką resztę daje prawa strona przy dzieleniu przez \(\displaystyle{ 125}\), dlatego \(\displaystyle{ r_{2}}\) i potęga \(\displaystyle{ 2}\) dają taką samą resztę przy dzieleniu przez \(\displaystyle{ 125}\).

[Miralem]

Ale to jest jeden przypadek. Gdy będę miał podstawę 3 albo 121, to już wtedy nie będę mógł się do tego stosować. Występujący w pierwszym poście sposób z metodą Eulera jest uniwersalny i można go stosować dla każdej podstawy. Czy nie ma czegoś podobnego ale dla liczb niewzględnie pierwszych?

[Michalinho]

Jak widać, sposób nie jest uniwersalny, bo gdy zamiast \(\displaystyle{ 3}\) pojawi się liczba parzysta lub podzielna przez \(\displaystyle{ 5}\) to już nie można go zastosować.
Tak więc dla wszystkich oprócz dwóch powyższych stosujesz ten schemat, który znasz, a do tych dwóch przypadków swój schemat poprzedzasz podzieleniem przez najwyższe potęgi \(\displaystyle{ 2}\) oraz \(\displaystyle{ 5}\), jakie dzielą jednocześnie \(\displaystyle{ 10^k}\) i twoją podstawę.
Po tej operacji będziesz mógł zastosować twierdzenie Eulera, bo wtedy uzyskane liczby będą względnie pierwsze. Uzyskane ostatnie cyfry mnożysz przez te najwyższe potęgi \(\displaystyle{ 2}\) i \(\displaystyle{ 5}\) z poprzedniego etapu i masz odpowiedź.
Nie widzę innego sposobu, więc radze się nauczyć.

[Miralem]

Ok, a co w przypadku tego przykładu?

Znajdź dwie ostatnie cyfry liczby \(\displaystyle{ 2122^{482}}\)

Nie wiemy ile wynosi \(\displaystyle{ 2122^{482}}\), więc nie możemy sprawdzić czy dzieli się przez tę samą liczbę, co \(\displaystyle{ 100}\). Przecież nie mogę podzielić \(\displaystyle{ 2122^{482}}\) przez np. \(\displaystyle{ 4}\), bo musiałbym najpierw pozbyć się potęgi...